0
$\begingroup$

I would like to select an appropriate number of buckets in my hash table for this scenario:

A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed by the 2-character initials of the customer's name, transformed into integers using the mapping: A=01, B=02,..., Z=26. It is expected that on average no more than 8 comparisons is made every time a search is requested.

How would you select an appropriate number of buckets for a division hash function, and a multiplication hash function, based on this scenario?

$\endgroup$
  • 1
    $\begingroup$ Sorry, what's an "m-value"? $\endgroup$ – David Richerby Nov 14 '18 at 17:05
  • $\begingroup$ The number of slots. For example, h(k) = k mod m (division method). $\endgroup$ – sortedquick Nov 14 '18 at 18:10
  • $\begingroup$ OK. Don't assume that everybody uses the same variable names as you do -- they probably don't. $\endgroup$ – David Richerby Nov 14 '18 at 18:27
1
$\begingroup$

The number of buckets in a hash structure will almost always be on the order of the number of items in the hash structure.

The phrase "on the order of" is intentionally imprecise. That means you could have twice as many buckets as items. Or two times as many items as buckets. But the two values (bucket count and item count) are generally correlated in a linear (not exponential) manner, within a factor of 10.

If the hash function is fairly good, and the number of buckets is prime, then anywhere up to one item per one bucket will result in a median search depth of one and an average search depth just over one. Generally, because the relative cost of a bucket is small, it makes sense to maintain a ratio of buckets to items that is greater than 1, but only minimally so.

Your description of your solution is confusing, because you have 10,000 records identified by initials, but only 676 combinations of initials (26 x 26). It is likely that you are layering complexity onto complexity in a vain attempt to save clock cycles and RAM, both of which you are likely to waste as a result of the inherent complexity of your solution. A smart guy named Donald Knuth once said: "Premature optimization is the root of all evil (or at least most of it) in programming." I'm almost certain you are well down that path already, and I suggest that you back out of that choice.

$\endgroup$
1
$\begingroup$

Two letters from a name are an extraordinarily bad hash code. There are only 576 possibilities, but letters are not random (you will find very few names with initials Z. Z.). With 10,000 records, I'd expect easily 100 records with the same hash code. There is no way on earth you can get the expected number of comparisons below 20 with this hash code.

Take a decent hash code, calculated from all characters in the name. Then you want something like 15,000 to 20,000 slots. 8 comparisons on average is something I would consider extremely high / unacceptably high.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.