CODEWITHSUNDEEP
javahashmaptreemaplinkedhashmap
Gekal
Gekal

Reputation: 47

How do Hashmaps, Treemaps and LinkedHashmaps work in Java?

I have various questions regarding maps:

  1. When iterating a Hashmap, there will be no guarantee about the iteration order. Now why is that?
  2. Why are Hashmaps faster than Treemaps?
  3. How do LinkedHashMaps work, how do they maintain the order? Is it because they have a doubly-linked list that contains the information about which entry is stored before and after an entry?

I've been reading through the API doc, but since I'm a beginner when it comes to programming I had some trouble understanding it.

Upvotes: 2

Views: 385

Answers (2)

Balmipour
Balmipour

Reputation: 3055

To keep it short : Maps and sets are generally unsorted data structures. If you want "sorted sets", you'd probably better use lists or arrays.

Your question is more about data structures rather than a really specific or java related programming problem, hence, you should start by reading about thoses. (sorry to post as an answer : commenting questions needs 50 rep)

Upvotes: -2

Makoto
Makoto

Reputation: 106430

When iterating a Hashmap, there will be no guarantee about the iteration order. Now why is that?

They're inserted not in order of when they occurred, but what value they hash to.

For example, suppose that we have a hash function h(x) which returns 127 for the string "Hello", and 12 for "Zebra". If we enter those keys into our hash map, the order in which they are read out is "Zebra" -> (whatever value attached), then "Hello" -> (whatever value attached).

This is apparent in the source code for HashMap:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

Mind you, this is a simplified variation on what hashing actually does and represents. It could be the case that there is a collision on a hash value, and that collision needs to be addressed in some fashion. This is meant as primer; the key is inserted in order of its hash, but if your hash function has flaws or you don't have a good value for your object's hash, then you may run into aberrant behavior.

Why are Hashmaps faster than Treemaps?

A hash operation is not dependent on the size of the overall collection. Recall that h(x) only operates based on the single value we're trying to insert. If we're inserting elements into a TreeMap, we have to consider what natural ordering they're in - and this involves traversing the structure to find a spot to insert into, and may also involve rebalancing or reorganizing the structure to ensure that balance is preserved.

There's a lot more to the source for TreeMap's put method.

public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

How do LinkedHashMaps work, how do they maintain the order? Is it because they have a doubly-linked list that contains the information about which entry is stored before and after an entry?

You can read the source for yourself, but the main takeaway here:

  • Keys are still grouped together in a hash structure to ensure their uniqueness.
  • The order in which they are inserted is preserved by a FIFO structure, like a linked list.

Think of it like this: you use the hash function to ensure that the key is unique, and if it is, you then immediately insert it and its value into the list. This way, both the ordering and the uniqueness are preserved.

Upvotes: 5

Related Questions