Hashmap hashcode to internal table index conversion
algorithm, containers, data-structures, hash, hashmap
Solution
Usually, a simple modulo will do the job.
To take a quick example from Wikipedia, it's simple as that :
hash = hashfunc(key)
index = hash % array_size
As you said, the resizing happen dependending on the hashmap filling ratio. The array is reallocated (see realloc()), then the indices are recalculated given the new array size, and the values copied to their new index.
Problem
Hashmaps usually implemented using internal array (table) of buckets. On accessing hashmap by key, we get key's hashcode using key-type specific(logic type specific) hash function. Then we need to map hashcode to actual internal buckets table index. ``` key -> (hash function) -> hashcode -> (???) -> index in internal table ``` Sometimes internal table could shrink and expand, depending on hashmap filling ratio. Then probably hashcode->index conversion method could be changed a bit. For example our hash function returns 32 bit unsigned integer value and moment A: internal table has capacity 10000 moment B: internal table has capacity 100000 What algorithms or approach usually used to perform hashcode->internal table index conversion? How is table resizing isue solved for them?