At many places, I read that we can use HashMap here for O(1) search. Actually, I want to ask how I can implement easy hashmaps which can satisfy this property. Can anyone tell few hashmaps including collision thing into consideration.
I don’t want complete codes. I want just pseudo code or algorithm for this. I am curious to know thing thing because I read this hashmaps use a lot and at many places. Thanks a lot in advance.
4
To keep collisions at a minimum, there are two big things you definitely need to get right:
-
The hashmap’s size must be sufficient to fit most or all of the data without collisions. Of course, you can have a hashmap that dynamically resizes itself after seeing a lot of collisions; you should still get O(1) amortized as long as this doesn’t happen too often.
-
The hash function must be good enough to make collisions a rare occurrence on your data set. The properties of your data are very important here, but for a detailed list of general options, see this existing PSE question. The short answer seems to be “use FNV-1a”.
Also, here are some dead-simple code samples to help get you started.
1