{"thread":{"id":"20425","subject":"Hash Tables","startedAt":"2009-08-06T04:35:40Z","lastAt":"2009-08-06T08:53:37Z","messageCount":3,"participants":["Philip Herron","Thomas Rast"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"119745","messageId":"4A7A5D9C.7000604@googlemail.com","threadId":"20425","inReplyTo":null,"subject":"Hash Tables","fromName":"Philip Herron","fromEmail":"herron.philip@googlemail.com","sentAt":"2009-08-06T04:35:40Z","receivedAt":"2009-08-06T04:35:40Z","isPatch":false,"sender":{"key":"herron.philip@googlemail.com","avatar":"https://gravatar.com/avatar/d382efcd09309373b6d7e8770518bc92c17dd5852003fad105aaee6b3a5fc53c?d=mp&s=160"},"body":"-----BEGIN PGP SIGNED MESSAGE-----\nHash: SHA1\n\nHey guys\n\nThis is my first time posting to git mailing-list didn't get much\nresponse from irc.\n\nI've been loving git and just been poking at its hash tables in\nhash.{c,h}, which are very nice. I've been implementing my own hash\ntables and i have some questions on how you guys done it.\n\n1 - Are you using the sha1.c as your hashing function? And why did you\nchoose it, I have been playing with a few different ones to see how it\ngoes.\n\n2 -table lookup i see your hash_table has an unsigned int nr, not\nquite sure what that is for num_remaing      or something is what i\nfirst thought.\n    But i see in your table lookup you use hash % size and it returns\nan index to the array. And would love       to  know how that works.\nIs size the current number of hash entries in the table?\n\n3 - what is the initial table size as in when you first insert an\nentry into the table, the array must be                allocated to a\nlength, and you grow when you reach a threshold.\n\nAnyways thanks!\n\n- --Phil\n-----BEGIN PGP SIGNATURE-----\nVersion: GnuPG v1.4.9 (GNU/Linux)\nComment: Using GnuPG with Mozilla - http://enigmail.mozdev.org\n\niEYEARECAAYFAkp6XZsACgkQAhcOgIaQQ2HWGgCfU6l909k7/JK3gf6BB2Cu35xB\njBIAn2Jl6UWp5ZvTXJxUWc91tgn//z25\n=6l91\n-----END PGP SIGNATURE-----\n"},{"id":"119749","messageId":"4A7A6756.4010305@googlemail.com","threadId":"20425","inReplyTo":"4A7A5D9C.7000604@googlemail.com","subject":"Re: Hash Tables","fromName":"Philip Herron","fromEmail":"herron.philip@googlemail.com","sentAt":"2009-08-06T05:17:10Z","receivedAt":"2009-08-06T05:17:10Z","isPatch":false,"sender":{"key":"herron.philip@googlemail.com","avatar":"https://gravatar.com/avatar/d382efcd09309373b6d7e8770518bc92c17dd5852003fad105aaee6b3a5fc53c?d=mp&s=160"},"body":"-----BEGIN PGP SIGNED MESSAGE-----\nHash: SHA1\n\nHey\n\nSorry for the mail i played around with the hash.c and i see how it\nworks now! Feel little bit stupid what threw me off was the  alloc_nr(\n); but its defined to #define alloc_nr(x) (((x)+16)*3/2) which is\nquite nice.\n\nand the nr threw me off but i see how it works now its actually the\nsimilar as what i was doing in my program, but your grow table was\nbetter because of alloc_nr acts like a threshold to grow and scale\nbetter, mine just added on another chunk of 32 elements just because\nit seemed like a good number to get something working.\n\nQuestion still stands is the hashing function one, which one and why?\n\nThanks loads, Sorry for bad posts!\n\n- --Phil\n-----BEGIN PGP SIGNATURE-----\nVersion: GnuPG v1.4.9 (GNU/Linux)\nComment: Using GnuPG with Mozilla - http://enigmail.mozdev.org\n\niEYEARECAAYFAkp6Z1UACgkQAhcOgIaQQ2FvQwCdGAgcuAUNG2/YyyzhXct3J2qc\nazwAninE/8I+Z4T4h294tCzXlLzmyGqW\n=Vahj\n-----END PGP SIGNATURE-----\n"},{"id":"119762","messageId":"200908061053.38739.trast@student.ethz.ch","threadId":"20425","inReplyTo":"4A7A6756.4010305@googlemail.com","subject":"Re: Hash Tables","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2009-08-06T08:53:37Z","receivedAt":"2009-08-06T08:53:37Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Philip Herron wrote:\n> \n> Question still stands is the hashing function [in hash.c], which one and why?\n\nIn the spirit of teaching you to fish...\n\nFirst you'll want to find out where the original users of this code\nwere.  So you run\n\n  git blame -- hash.c\n\nand see that most of the lines come from 9027f53 (Do linear-time/space\nrename logic for exact renames, 2007-10-25).  So you can then look at\nthis commit:\n\n  git show 9027f53c\n\nAha, it says\n\n    In the expectation that we will indeed do the same hashing trick for the\n    general rename case, this code uses a generic hash-table implementation\n    that can be used for other things too.  In fact, we might be able to\n    consolidate some of our existing hash tables with the new generic code\n    in hash.[ch]\n\nand further down in the patch\n\n+       hash = hash_filespec(filespec);\n+       pos = insert_hash(hash, entry, table);\n\nand right above that\n\n+static unsigned int hash_filespec(struct diff_filespec *filespec)\n+{\n+       unsigned int hash;\n+       if (!filespec->sha1_valid) {\n+               if (diff_populate_filespec(filespec, 0))\n+                       return 0;\n+               hash_sha1_file(filespec->data, filespec->size, \"blob\", filespec-\n+       }\n+       memcpy(&hash, filespec->sha1, sizeof(hash));\n+       return hash;\n+}\n\nSee?\n\nAs for the *why*, presumably because all of git assumes two objects\nwith the same SHA1 are indeed the same file; so we can later make the\nsame optimisation again:\n\n+                       if (hashcmp(one->sha1, two->sha1))\n+                               continue;\n\nAnd then, as we've already computed the SHA1, any subset of it is as\ngood a hash as anything else; it'll be uniformly distributed.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}