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 ## YHashMap 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 ### YHashMap Storage requirements
12 Typical storage usage for a table near its load factor is 22 bytes per entry.
13
14 Inserting entries into the YHashMap 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.
32
33
34 ## Sample JHM test results for Get, Put, Iteration, and Replacement
35
36 Benchmark (mapType) (seed) (size) Mode Cnt Score Error Units
37 GetX.getHit org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.007 ± 0.001 ms/op
38 GetX.getHit org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.006 ± 0.001 ms/op
39 GetX.getHit java.util.HashMap 42 500 avgt 5 0.004 ± 0.001 ms/op
40 GetX.getHit org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 91.906 ± 3.417 ms/op
41 GetX.getHit org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 77.905 ± 8.267 ms/op
42 GetX.getHit java.util.HashMap 42 1000000 avgt 5 79.900 ± 7.679 ms/op
43
44 GetX.getMix org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.006 ± 0.001 ms/op
45 GetX.getMix org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.004 ± 0.001 ms/op
46 GetX.getMix java.util.HashMap 42 500 avgt 5 0.004 ± 0.001 ms/op
47 GetX.getMix org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 174.739 ± 25.464 ms/op
48 GetX.getMix org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 77.241 ± 4.472 ms/op
49 GetX.getMix java.util.HashMap 42 1000000 avgt 5 122.827 ± 8.779 ms/op
50
51 PutX.put org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.034 ± 0.005 ms/op
52 PutX.put org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.025 ± 0.003 ms/op
53 PutX.put java.util.HashMap 42 500 avgt 5 0.013 ± 0.001 ms/op
54 PutX.put org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 459.951 ± 345.698 ms/op
55 PutX.put org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 409.430 ± 146.610 ms/op
56 PutX.put java.util.HashMap 42 1000000 avgt 5 336.873 ± 122.706 ms/op
57
58 PutX.putSized org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.014 ± 0.002 ms/op
59 PutX.putSized org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.012 ± 0.002 ms/op
60 PutX.putSized java.util.HashMap 42 500 avgt 5 0.010 ± 0.002 ms/op
61 PutX.putSized org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 263.196 ± 68.516 ms/op
62 PutX.putSized org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 292.726 ± 165.881 ms/op
63 PutX.putSized java.util.HashMap 42 1000000 avgt 5 310.345 ± 176.412 ms/op
64
65 ReplX.replace org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.023 ± 0.001 ms/op
66 ReplX.replace org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.011 ± 0.001 ms/op
67 ReplX.replace java.util.HashMap 42 500 avgt 5 0.012 ± 0.001 ms/op
68 ReplX.replace org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 302.525 ± 13.322 ms/op
69 ReplX.replace org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 206.582 ± 33.568 ms/op
70 ReplX.replace java.util.HashMap 42 1000000 avgt 5 231.924 ± 40.715 ms/op
71
72 WalkX.sumIterator org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.003 ± 0.001 ms/op
73 WalkX.sumIterator org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.010 ± 0.001 ms/op
74 WalkX.sumIterator java.util.HashMap 42 500 avgt 5 0.002 ± 0.001 ms/op
75 WalkX.sumIterator org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 43.471 ± 3.634 ms/op
76 WalkX.sumIterator org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 35.960 ± 2.046 ms/op
77 WalkX.sumIterator java.util.HashMap 42 1000000 avgt 5 58.106 ± 3.852 ms/op
78
79 WalkX.sumIteratorHidden org.openjdk.bench.valhalla.corelibs.YHashMap 42 500 avgt 5 0.002 ± 0.001 ms/op
80 WalkX.sumIteratorHidden org.openjdk.bench.valhalla.corelibs.XHashMap 42 500 avgt 5 0.007 ± 0.001 ms/op
81 WalkX.sumIteratorHidden java.util.HashMap 42 500 avgt 5 0.005 ± 0.001 ms/op
82 WalkX.sumIteratorHidden org.openjdk.bench.valhalla.corelibs.YHashMap 42 1000000 avgt 5 33.189 ± 2.212 ms/op
83 WalkX.sumIteratorHidden org.openjdk.bench.valhalla.corelibs.XHashMap 42 1000000 avgt 5 43.003 ± 1.183 ms/op
84 WalkX.sumIteratorHidden java.util.HashMap 42 1000000 avgt 5 102.566 ± 5.276 ms/op