2

Is the retrieval of entries from HashMap really randomized? Or does it depend on buckets in which the entries are hashed and then these buckets are accessed in some predefined order ? or any other kind of order internally happening?

AdityaKapreShrewsburyBoston
  • 1,143
  • 2
  • 16
  • 37
  • 2
    Your answer is here if you want to read ... http://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html – StackFlowed Sep 24 '14 at 14:50
  • 4
    It's not called `RandomMap`. – Sotirios Delimanolis Sep 24 '14 at 14:50
  • See also: http://stackoverflow.com/questions/2144776/order-of-values-retrieved-from-a-hashmap – assylias Sep 24 '14 at 14:52
  • 1
    The hashcode first defines the bucket, then a linked list is used for each bucket in order to resolve collisions. Hence it would be - as already stated multiple times - answer b: buckets (by hashcode) + predefined order (by linked lists + hashcode) – Thomas Sep 24 '14 at 14:54
  • The java doc says "This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.", but if hash funtion is fixed, the and keys same, why is there no guarantee of alteast some order ? Is it because the table can get re-hashed over time ? – AdityaKapreShrewsburyBoston Sep 24 '14 at 15:02
  • @comeOnGetIt To reduce the frequency of collisions, when there are enough things added to a hash table, the number of buckets may be increased. This will alter the order of iteration. – khelwood Sep 24 '14 at 15:29

2 Answers2

6

Answer b - it depends on buckets in which the entries are hashed and then these buckets are accessed in some predefined order

khelwood
  • 55,782
  • 14
  • 81
  • 108
2

What happens when you call the get method on a HashMap for a non-null key:

  1. The hashCode() method for your key is called.

  2. The hash bucket for that hash is obtained by simply and'ing the hash with the number of buckets - 1 which works because the implementation ensures that the number of buckets is always a power of 2. Because the buckets are simply a java array of HashMap.Entry objects the resulting integer can be used as a plain array index. This is where the O(1) complexity comes from.

  3. The entries in the bucket (a linked list) are iterated until one is found where the hash and the key match the one you want. This is where the O(1) complexity starts to deteriorate towards a worst case of O(n).

So you can see that an efficient use of the HashMap will try to minimise the number of entries that end up together in a bucket. All that matters in that respect is the distribution of the bits in your hashcode from bit 0 to bit N-1 where N is the power of 2 used to calculate the number of buckets. All bits in your hashcode above that limit are masked away and only get used again during the iteration of the bucket list.

Andy Brown
  • 11,766
  • 2
  • 42
  • 61
  • For your third point : I've always thought the `equals` method was called to solve collision, is that the case even if you don't explicitly say it (or maybe it is what you mean by "the key match the one you want") ? – Dici Sep 24 '14 at 15:24
  • @Dici, yes ultimately .equals() will be called on the key but the implementation first tries to avoid that potentially slower call by doing a reference equality check on the keys first and it will only do that if the previously computed hash matches the cached hash of the entry. – Andy Brown Sep 24 '14 at 15:47