knowit: Java

Hashtable

is synchronised
Any non-null object can be used as a key or as a value
The keys must implement the hashCode method and the equals method.
Initial Capacity ( default 16 / 11 in 5.0) - Number of buckets (array size) when the hash table is created
Load Factor (.75 default) - How much the table is allowed to get full before its capacity is automatically increased.
rehash() - If size increases threshold (capacity * load factor) rehash() is called. This increases size by two times + 1. All entries are then added into the new Hashtable.Entry[]
Collision - Two entries hash to the same bucket
Implementation

volatile Set< Map.Entry<K,V> > entrySet - this is backed by the map so changes in the map are reflected in the set.
volatile Set<K> keySet;
volatile Collection<V> values;
hash - caches the value of hashcode of the key in the Entry.
size() - stored in instance variable count.
get() -

Find the array index using hashcode of key and mod of array size( capacity )
traverse the Entry (list) till

HashMap

When an element is added to the HashpMap key.hashCode() is used to create the new hashCode to be stored in the Entry using a supplimental hash(int) function. This value effectively truncates the lowerbits (lower 12 for sure) of the original Hashcode.

rehash - the rehash function is called resize() and increment size is twice the current size
keySet() & entrySet() return instances of classes that are inner classes of the HashMap. All Set methods implemented by these classes ( iterator(), contains(), remove(), clear()) directly forward to an existing method in the HashMap class and hence a state change in the Map is reflected in the Set and vice-versa.

LinkedHashMap<>

extends HashMap
Maintains doubly link list through the Entries.
Header node points to the LinkedList<LinkedList.Entry> with before & after pointers.
header.before = most recently added Entry
header.after = oldest Entry added ( candidate to be removed if configured )
Has predictable iteration order - Order of insertion as maintained by the Linked List.
insertion order is not affected if a key is re-inserted into the map.
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) - If accessOrder is true iteration order is from Least Recently accessed to Most Recently accessed. Can be used for LRU cache.
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) - By default returns false. Can be overidden to return true if eldest Entry is to be removed.
eldest - is the Entry which will be removed if the method returns true.

TreeMap

The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
The ordering maintained by a tree map, like any sorted map, and whether or not an explicit comparator is provided, must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.)
This is so because the Map interface is defined in terms of the equals operation, but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal.
The behaviour of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.
This is a Binary Search Tree implementation. Red-Black Tree
put( K, V ) -

Find the ( would be ) parent node (TreeMap.Entry) for the new node starting from root.
Create new TreeMap.Entry (default colour = BLACK) and add as a leaf node.
Rebalance tree based on Red-Black tree algorithm.
return old Value associated with the Key or null if no mapping exist.

Find the smallest TreeMap.Entry in the tree. This is the leftmost node. Start from root and keep moving left till we reach null
Traverse the tree to find the successor (next node)
Compare the value with successor value.
This operation requires time linear in Map size

entrySet() - Is special that it doesn't maintain a state itself but is backed by the Map so the changes in the Map are reflected in the Set and vice-versa.

Map.Entry<K,V> - Interface

IdentityHashMap<K,V>

Violates the general Map contract which mandates use of equals() when comparing two Objects/ Elements.
Uses reference-equality instead of object-equality for both Keys & Values.
Depends on - System.identityHashCode(Object)
No Entry Class/Object. Key is stored at location table[i] and value at table[i+1]
So maximum capacity is fixed which is size/2
containsValue ( Object ) requires traversal of full array.
rehash is costly and creates new array of double size

ConcurrentSkipListMap<K,V>

knowit