I have various questions regarding maps:
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.
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:
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.
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)
