1 # Prototype implementations of HashMaps using inline classes for the table entries.
 2 
 3    **NOTE: The implementations have NOT been optimized or tuned.**
 4 
 5 ## HashMap uses Open Addressing to store all entries in a table of inline classes
 6 The hash of the key is used as the first index into the table. 
 7 If there is a collision, double hashing (with a static offset) is used to probe subsequent locations for available storage.
 8 The Robin Hood hashing variation on insertion is used to reduce worst case lookup times.
 9 On key removal, the subsequent double-hashed entries are compressed into the entry being removed.
10 
11 ### HashMap Storage requirements
12 Typical storage usage for a table near its load factor is 22 bytes per entry.
13 
14 Inserting entries into the HashMap may resize the table but otherwise does
15 not use any additional memory on each get or put.
16 
17 ## XHashMap stores the initial entry in a table of inline classes
18 The hash of the key is used as the first index into the table. 
19 If there is a collision, subsequent entries add the familiar link list of Nodes.
20 On key removal, direct entries in the table are replaced by the first linked node;
21 for Nodes in the link list, the Node is unlinked.
22 
23 ### XHashMap Storage requirements:
24 Typical storage usage for a table near its load factor is 32 bytes per entry.
25 
26 ## java.util.HashMap (the original)
27 HashMap uses a table of references to the initial Node entries, collisions are handled by 
28 linked Nodes.
29 
30 ### HashMap Storage requirements:
31 Typical storage usage for a table near its load factor is 37 bytes per entry.