Clever Geek Handbook

How to implement a hash function for a HashSet / HashMap

If I needed to hash integers HashSet<T>

or HashMap<T, U>

where T

the hashing algorithm is already implemented, how would I do it? Note that I am not asking about hash table hashing elements, I am talking about hashing the entire data structure. It is not as difficult with an ordered set as a TreeSet

, but since the order of the elements of the hash table is not defined, it is more difficult. Sorting elements is generally impossible, since the algorithm should take no more than O (n) time.

I'm looking for a generic, language independent example, but you can provide code or code links from any language.

+3


source to share


2 answers


Your options:

  • Force order to generate hash
  • Apply a hashing algorithm that is commutative (regardless of order)


The first option may be viable if the number of elements is relatively small. You can sort hash items for example. by the hash value (of each element), then well-known hash combining techniques are applied, such as multiplying each subsequent element's contribution to the hash by (SomePrime) ^ n.

For the second option, simply adding the hash of each item to the hash together can provide a suitable distribution, since the hash of each item itself must be very well distributed.

+3


source


Introduce a new field for the data structure where you can store the hashbase. Every time we add an element to hashmap / hahset, we do something like hashbase + = element.hash if the element doesn't exist yet. Use this hashbase to compute the hash.



0


source






More articles:


All Articles