# Hashing **URL:** \ **Category:** Factual Questions\ **Created:** [March 30, 2004, 7:52pm UTC](https://boards.straightdope.com/t/hashing/237379 "2004-03-30T19:52:34Z")\ **Posts on this page:** 14\ **Page:** 2
**Author:** ![erislover](https://avatars.discourse-cdn.com/v4/letter/e/71e660/32.png) [@erislover](https://boards.straightdope.com/u/erislover)\ **Post date:** [March 31, 2004, 7:57pm UTC](https://boards.straightdope.com/t/hashing/237379/21 "2004-03-31T19:57:54Z")
So is hashing like a substitution cipher? ---
**Author:** ![caphis](https://avatars.discourse-cdn.com/v4/letter/c/e19adc/32.png) [@caphis](https://boards.straightdope.com/u/caphis)\ **Post date:** [March 31, 2004, 8:20pm UTC](https://boards.straightdope.com/t/hashing/237379/22 "2004-03-31T20:20:28Z")
One more question, guys. Thanks for the great responses! Say I had about 50,000 entries. The hash table being used uses Separate Chaining to avoid collisions. What would be a good table size to a) maximize performance on insertions? b) maximize performance on finds? I’m using guess and check, but the best results are coming at a table size of 50,000. Does this make sense? ---
**Author:** ![caphis](https://avatars.discourse-cdn.com/v4/letter/c/e19adc/32.png) [@caphis](https://boards.straightdope.com/u/caphis)\ **Post date:** [March 31, 2004, 8:28pm UTC](https://boards.straightdope.com/t/hashing/237379/23 "2004-03-31T20:28:11Z")
Actually, I think I just realized that this depends largely on the hash function itself. Right? Someone stop me if I’m wrong. 😃 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 31, 2004, 8:33pm UTC](https://boards.straightdope.com/t/hashing/237379/24 "2004-03-31T20:33:23Z")
> [@caphis](#): > > One more question, guys. Thanks for the great responses! > > Say I had about 50,000 entries. The hash table being used uses Separate Chaining to avoid collisions. What would be a good table size to > > a) maximize performance on insertions? > b) maximize performance on finds? > > I’m using guess and check, but the best results are coming at a table size of 50,000. Does this make sense? That should depend on the hash function and the data structure used as a chain. ---
**Author:** ![LordVor](https://avatars.discourse-cdn.com/v4/letter/l/90ced4/32.png) [@LordVor](https://boards.straightdope.com/u/LordVor)\ **Post date:** [March 31, 2004, 9:15pm UTC](https://boards.straightdope.com/t/hashing/237379/25 "2004-03-31T21:15:28Z")
> [@caphis](#): > > One more question, guys. Thanks for the great responses! > > Say I had about 50,000 entries. The hash table being used uses Separate Chaining to avoid collisions. What would be a good table size to > > a) maximize performance on insertions? > b) maximize performance on finds? > > I’m using guess and check, but the best results are coming at a table size of 50,000. Does this make sense? This is a misleading question. Even if you use chaining, you maximize performance on insertions and finds by minimizing collisions. While “it depends” is the proper answer, if you assume that the combination of the hash function and the hash keys used yields a relatively even distribution of data points, the most efficient hash table is usually around twice as big as the number of entries. That said, hash functions usually work best if the table size is a power of 2, so a lot of times you just round the expected number of entries up to the next power of 2. If you’re still using the same assumptions, 50,000 entries, each with a unique key from 1-50,000, then 50,000 would indeed be the most efficient table size. I still think that that’s a bogus scenario, you’re better off just using a big array. BTW, I’m also getting the distinct impression that we’re doing your homework for you. -lv ---
**Author:** ![caphis](https://avatars.discourse-cdn.com/v4/letter/c/e19adc/32.png) [@caphis](https://boards.straightdope.com/u/caphis)\ **Post date:** [March 31, 2004, 9:26pm UTC](https://boards.straightdope.com/t/hashing/237379/26 "2004-03-31T21:26:15Z")
> [@LordVor](#): > > BTW, I’m also getting the distinct impression that we’re doing your homework for you. In fact, you’re not; but, you are helping me learn. karma++. Thanks for the replies, everyone! ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [March 31, 2004, 10:06pm UTC](https://boards.straightdope.com/t/hashing/237379/27 "2004-03-31T22:06:06Z")
When designing a database, if you are stuck using a relatively long string (first and last name for instance) as a key, usually what is done is to define a “seek key” on that string. When you get a representative string key to look-up, insert or delete in the database, you calculate its seek key using a hashing algorithm. The seek key is numeric and is used as the primary key for your database. The space efficiency difference of using a seek key in a database rather than a character string is enormous, the time efficiency difference is even more significant. This is just one good example of how hashing is used in the real world. ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [March 31, 2004, 10:13pm UTC](https://boards.straightdope.com/t/hashing/237379/28 "2004-03-31T22:13:41Z")
> [@ultrafilter](#): > > Any function that maps the universe of keys to the cells in the table is a hash function. > > What you describe is only a hash function IF all the keys are less than the table size. Otherwise, you’ll map a key to somewhere outside the table. Would that be … only if the keys are less than OR EQUAL the table size? I was just wonder if the “equal” case would be technically considered a hash function? Or does a hash function “require” that some collisions have a less than zero probability? Maybe the “equal” case is just an index calculation? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 31, 2004, 10:17pm UTC](https://boards.straightdope.com/t/hashing/237379/29 "2004-03-31T22:17:39Z")
> [@ccwaterback](#): > > Would that be … only if the keys are less than OR EQUAL the table size? I was just wonder if the “equal” case would be technically considered a hash function? Or does a hash function “require” that some collisions have a less than zero probability? Maybe the “equal” case is just an index calculation? “less than zero probability”? I’m working off a 0-based array here. So for a table of n elements, the indices are 0, 1, 2, …, n - 1. If you work off a 1-based array, the indices are 1, 2, 3, …, n. Either way, if you just take the value of the employee ID, you could conceivably run off the end of the array, and that’s bad. At that point, you start overwriting random data, which could be really important. ---
**Author:** ![Newton\_meter](https://avatars.discourse-cdn.com/v4/letter/n/57b2e6/32.png) [@Newton\_meter](https://boards.straightdope.com/u/Newton_meter)\ **Post date:** [March 31, 2004, 10:30pm UTC](https://boards.straightdope.com/t/hashing/237379/30 "2004-03-31T22:30:21Z")
> [@ultrafilter](#): > > At that point, you start overwriting random data, which could be really important. Random data is hardly ever important. And it’s still pretty random after you’ve overwritten it, so what’s the problem? Just kidding. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [March 31, 2004, 10:31pm UTC](https://boards.straightdope.com/t/hashing/237379/31 "2004-03-31T22:31:54Z")
One man’s trash is another man’s list of function pointers. ---
**Author:** ![ccwaterback](https://avatars.discourse-cdn.com/v4/letter/c/df705f/32.png) [@ccwaterback](https://boards.straightdope.com/u/ccwaterback)\ **Post date:** [April 1, 2004, 12:42am UTC](https://boards.straightdope.com/t/hashing/237379/32 "2004-04-01T00:42:02Z")
> [@ultrafilter](#): > > “less than zero probability”? > > I’m working off a 0-based array here. So for a table of n elements, the indices are 0, 1, 2, …, n - 1. If you work off a 1-based array, the indices are 1, 2, 3, …, n. > > Either way, if you just take the value of the employee ID, you could conceivably run off the end of the array, and that’s bad. At that point, you start overwriting random data, which could be really important. Sorry, I wasn’t very clear in that last post. What I meant was, if I have a table that has 1000 entries, and my Emp IDs run from 1 to 1000, would the function that coverts the Emp ID from ascii to binary be considered a hash function? ---
**Author:** ![notquitekarpov](https://avatars.discourse-cdn.com/v4/letter/n/71c47a/32.png) [@notquitekarpov](https://boards.straightdope.com/u/notquitekarpov)\ **Post date:** [April 1, 2004, 4:43pm UTC](https://boards.straightdope.com/t/hashing/237379/33 "2004-04-01T16:43:32Z")
> [@](#): > > Can’t you guys even give the rest of the human race an “in” to what the hell you are talking about > [@Bytegeist](#): > > _Hashing_ to a computer programmer is… Just a quick post of appreciation - so you know I _ **was** _ actually interested in knowing more. Your explanation was very good for an uninitiated MS Office user. I have always felt I should know more about databases and their management/interogation, or at least know enough to ask sensible questions… Carry on. ---
**Author:** ![LordVor](https://avatars.discourse-cdn.com/v4/letter/l/90ced4/32.png) [@LordVor](https://boards.straightdope.com/u/LordVor)\ **Post date:** [April 1, 2004, 5:00pm UTC](https://boards.straightdope.com/t/hashing/237379/34 "2004-04-01T17:00:13Z")
> [@caphis](#): > > In fact, you’re not; but, you are helping me learn. karma++. Well that’s ok then. **ccwaterback** , a hashing function has to be able to take any input of the desired type (string, in your case) and return a number between 0 and the size of the hash table-1. It can’t depend on restrictions to it’s inputs, else, in this case, you’d end up writing past the end of the table as soon as you add another employee. Which is why you have to put in the mod(tablesize) calculation. The mod operator (% in c-style languages) basically gives you the “remainder” from integer division. So 1000 % 1000 would be 0, 1000 & 1001 would be 1, etc. And, since arrays are 0-based in c-style languages, a 1000 you can map employees 1-999 to array entries 1-999 if you want, but that means that employee 1000 has to go in slot 0, not slot 1000. -lv [Previous page](https://boards.straightdope.com/t/hashing/237379.md?page=1)