2
$\begingroup$

I am trying to implement a hash table for string keys as part of a university project. I was able to make a basic, working implementation without major issues. I am now trying to optimize the thing to go closer to a O(1) expected lookup / insert time.

I was reading up on hash functions and in particular, the MAD method for hashcode compression. From my understanding, the MAD methods needs parameters (namely a multiplier a, a prime p and and offset O): index = ((a * i + o ) % p ) % N , where i is the hashcode and N is the size of the underlying array to store the data. It is noted everywhere that p must be bigger than N, which seems natural if we want to insert the data uniformly.

Now, my misunderstanding comes from hash tables for which we do not know the numbers of keys that will be inserted ahead of time, and have no fixed capacity. Is MAD still a viable technique? From my understanding, the parameters need to be tuned to ensure an even distribution of the keys across the whole array.

A lot of hash map literature I could get my hands on also seems to imply that the maps are of fixed sizes. I am trying to figure out the same things for the table size (a lot of people talk about a prime-sized table, which seems unrealistic for resizable hash tables).

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Hash_table#Dynamic_resizing $\endgroup$ – xskxzr Apr 5 '18 at 5:36
  • 1
    $\begingroup$ I understand how to resize it, but my questions is more about how the MAD technique is adjusted to work with the new table size $\endgroup$ – Samuel Yvon Apr 5 '18 at 12:49
  • 1
    $\begingroup$ I'm not familiar with the MAD method. Can you provide a citation or reference or link to where you ran across it? (Ideally, one that describes the method in a self-contained way?) $\endgroup$ – D.W. Apr 5 '18 at 18:18
  • $\begingroup$ A came across it in a lot of litterature (ISBN-13 : 978-8126562176 and 978-0321573513), but online you can read about it on this page: cpp.edu/~ftang/courses/CS240/lectures/hashing.htm $\endgroup$ – Samuel Yvon Apr 5 '18 at 20:03

Your Answer

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

Browse other questions tagged or ask your own question.