loading...

re: Why I love HashMaps!!! VIEW POST

TOP OF THREAD FULL DISCUSSION
re: What you have pointed out is somewhat very advanced issue But my general focus here was how it can help in tech interviewes
 

Sure, hash is cool, the main cost being the hash function itself. The main variance is whether the bucket is a list to search or if you jump to another bucket on miss with quadratic, linear, double hash. The main control is the initial bucket count. Some hash maps/sets can expand, doubling in bucket count, but cleanup is a challenge, so going big initially is wise. Buckets are often pointers, so 8 bytes each is pretty cheap!

Do you have an opinion about bucket count, like is a prime better than a mod 2 number for randomizing buckets?

The trade off in choosing hash is lookup speed versus lack of ordering. In comparison, a tree or trie allows range search, prefix search, sorted output but a bit slower lookup, tree imbalance vulnerability, a bit more memory cost. Linked list, tree, trie allows no danger of too high a load factor, infinite expansion. All but array have extra overhead to size. Array, vector are fast but expensive to expand, insert, delete, sort. Skip list combines tree and linked list! So many choices!

code of conduct - report abuse