CODEWITHSUNDEEP
javacollections
chaoshangfei
chaoshangfei

Reputation: 205

HashMap with definite searching time?

My understanding on HashMap is that the order in unpredictable, therefore the searching time is unpredictable too. But I was asked this question in a recent interview "Is there a situation where HashMap has a definite searching time?"

Upvotes: 1

Views: 591

Answers (2)

anttix
anttix

Reputation: 7779

HashMap is a probablistic data structure with an average lookup time complexity of O(1) However a lookup can take as long as O(n) under worst case circumstances.

There are a lot of "special" cases where a hash is guaranteed to perform a lookup in O(1) time.

For example:

  1. HashMap is empty
  2. HashMap has only a single element
  3. HashMap has no collisions (no bucket has more than a single element)

If all keys are known in advance, it is possible to generate a "perfect" hashing funcion that guarantees case #3. This is used in practice for generating symbol lookup tables where a set of symbols (Strings) is known in advance.

See:

Upvotes: 2

Dileep
Dileep

Reputation: 5440

The hashMap has a variable retrieval time..!!

The hashMap finds the location by using an hash function.But the hash function takes some time to complete. Its basically an algorithm, so the execution of that algorithm needs some some time..!!

The next thing is that even if the hash function completes, it produce same location to more than one entry(in some cases). So in that case it wants to look deeper. That too takes more time..!!

The only case that the hashMap points to a entries that has common retrieval time is that, the data must always produce a unique hashKey. That is, the time will always be equal to the execution of the Hash Algorithm.

But in the case of an Array The retrieval time is always the same, since it makes direct access to the location of the array the time is always O(1).

Upvotes: 0

Related Questions