5

I read that HashMap has a backing array, where entries are stored (marked with bucket number, initial size 16). Arrays are ordered, and I can call get(n) to get the element at nth position. Then why is HashMap unordered and has no get(n) method?

Dev S
  • 125
  • 6
  • "and has no get(n) method" how exactly do you expect `get(n)` to work/return? Bucket can hold many elements with *similar* hash property (here lets say that keys with same result of `key.hashcode%16` will go to same bucket). Anyway map are ordered but not in a way which we can rely on, since it can change based on amount of elements (to better balance elements in buckets). – Pshemo Aug 02 '17 at 15:33
  • Just as a comment, if you like to maintain **insertion-order** and also use a `HashSet` than you might find the class `LinkedHashSet` useful which does exactly that by adding two pointers **prev** and **next** to each element (a technique called *linked list*). – Zabuzard Aug 02 '17 at 15:48
  • The same also holds for `HashMap`, their is a class called `LinkedHashMap` that does the same. – Zabuzard Aug 02 '17 at 15:55

2 Answers2

6

It depends on your view of what ordered means.

Indeed HashMapss internally use an array or another collection that has a fixed ordering. However the order has nothing to do with insertion order or something like that. The elements are ordered, for example, in increasing size of their hash-values and they have nothing to do with some actual ordering on the elements themselves.

So HashMaps indeed have something like a get(n) method if you think of n being the hash-value of the key-element. The method is called get(*key*) and it first computes the hash-value of the given key-element and then looks the value up on the internal structure by using get(*hash-value*) on it.

Here is an image a quick search yield that shows the structure of HashSets:

HashSet structure

Note that HashSets are kinda the same than HashMaps, they use the same technique and the same image applies. But instead of just inserting an element a map inserts a container that is identified by the key and additionally holds a value.

Just as a small overview. A hash-function is a function that given an object computes a small value, the hash-value out of it, using its properties. The computation usually can be done fast and a lookup on the internal array at the position given by the hash-value is thus also fast.

To your specific question, as an user of a HashMap you generally are not interested in what elements specifically hide behind hash-value 1 or 2 and so on, that is why they did not include such a method. However if you truly need to do that for a special application or so than you can always try to use Reflection to access the internals of your HashMap or you could also just write a small wrapper around the class that provides such a method.

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
  • Oh, thanks for mentioning that, totally missed it! However the technique itself remains the same. – Zabuzard Aug 02 '17 at 15:49
  • Indeed. I have edited the answer. Otherwise it could confuse OP. However the only difference between them is that `HashSet` just stores elements and `HashMap` stores containers, not a big difference. – Zabuzard Aug 02 '17 at 15:54
  • There is no difference at all. `HashSet` is fundamentally just a `HashMap` – Michael Aug 02 '17 at 15:56
2

A HashMap is divided into individual buckets. Buckets are initially backed by an array, however if the buckets get too large then they are converted to tree structures which are sorted based on hash codes. That fact alone destroys any guarantee it could make about preserving insertion order.

If you'd like to know more about how it's implemented, you can look at my answer to this question: HashMap Java 8 implementation

Michael
  • 41,989
  • 11
  • 82
  • 128