-1

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.

Improve this question
4
  • 1
    @gnat I don't think that's what this question is asking; I believe the question here is what to do with the hash value in order to get O(1) lookups even in presence of collisions, rather than how to minimise collisions in the first place, as described.in the answers to that question.
    – Jules
    Jan 11, 2015 at 19:02
  • @gnat Jules is correct.Please help if you can help in this. Tell me some easy hash functions which we can implement which have O(1) time complexity for searching.
    – hellodear
    Jan 11, 2015 at 19:29
  • In many standard libraries there is a perfectly good (sometimes even pretty superb) hash tables. Why do you want to implement your own? (If you want to learn, why focus on the simple ones?)
    – user7043
    Jan 11, 2015 at 19:33
  • @delnan Yup. I want to learn only. I want to start with simpler ones, then gradually will proceed to tougher ones. Libraries are fine, I know but I want to learn. Can you tell me some simple string hashing functions which I implement while interviews etc?
    – hellodear
    Jan 11, 2015 at 19:54

1 Answer 1

Reset to default
1

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.

Improve this answer
1
  • 1
    You also need good a story for collision resolution (linear probing can be pretty awful, separate chaining has pretty bad constant factors unless you get excessively clever), and the hash function depends on your keys (the question you link only considers string hashes).
    – user7043
    Jan 11, 2015 at 19:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.