1

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?"

chaoshangfei
  • 205
  • 4
  • 12
  • No, unpredictable order has nothing to do with search time. HashMap does `put` and `get` in constant time. Start by reading the API of HashMap: http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html. I assumed by 'search time' you mean time to fetch a random key. – Daniël Knippers Mar 17 '14 at 17:39
  • `LinkedHashMap` stores the elements in insertion order, but the term "searching time" might require a clarification here...ATM, I assume that this refers to a linear search for a certain entry, regardless of the scenario in which this should occur... – Marco13 Mar 17 '14 at 17:39
  • 1
    @DaniëlKnippers It's constant time "assuming the hash function disperses the elements properly among the buckets." That's an assumption you can't always make. See http://stackoverflow.com/questions/8669946, for instance. – yshavit Mar 17 '14 at 17:41

2 Answers2

2

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:

anttix
  • 7,709
  • 1
  • 24
  • 25
  • +1, but afaik, case #2 there isn't particularly special, except insofar as it guarantees case #3. At least, in most hash map implementations (including `java.util.HashMap`). – yshavit Mar 17 '14 at 17:52
  • Thanx. It is indeed, #1 is also a special case of #3. – anttix Mar 17 '14 at 17:53
  • Ha, good catch! I would give that #3 top billing, and then list #1 and #2 as examples. – yshavit Mar 17 '14 at 17:54
0

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).

Dileep
  • 5,362
  • 3
  • 22
  • 38