/
CompactStringObjectMap.java
135 lines (121 loc) · 4.03 KB
/
CompactStringObjectMap.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package com.fasterxml.jackson.databind.util;
import java.util.*;
/**
* Specialized lookup class that implements functionality similar to
* {@link java.util.Map}, but for special case of key always being
* {@link java.lang.String} and using more compact (and memory-access
* friendly) hashing scheme. Assumption is also that keys are typically
* intern()ed.
*<p>
* Generics are not used to avoid bridge methods and since these maps
* are not exposed as part of external API.
*
* @since 2.6
*/
public final class CompactStringObjectMap
{
/**
* Shared instance that can be used when there are no contents to Map.
*/
private final static CompactStringObjectMap EMPTY = new CompactStringObjectMap(1, 0,
new Object[4]);
private final int _hashMask, _spillCount;
private final Object[] _hashArea;
private CompactStringObjectMap(int hashMask, int spillCount, Object[] hashArea)
{
_hashMask = hashMask;
_spillCount = spillCount;
_hashArea = hashArea;
}
public static <T> CompactStringObjectMap construct(Map<String,T> all)
{
if (all.isEmpty()) { // can this happen?
return EMPTY;
}
// First: calculate size of primary hash area
final int size = findSize(all.size());
final int mask = size-1;
// and allocate enough to contain primary/secondary, expand for spillovers as need be
int alloc = (size + (size>>1)) * 2;
Object[] hashArea = new Object[alloc];
int spillCount = 0;
for (Map.Entry<String,T> entry : all.entrySet()) {
String key = entry.getKey();
int slot = key.hashCode() & mask;
int ix = slot+slot;
// primary slot not free?
if (hashArea[ix] != null) {
// secondary?
ix = (size + (slot >> 1)) << 1;
if (hashArea[ix] != null) {
// ok, spill over.
ix = ((size + (size >> 1) ) << 1) + spillCount;
spillCount += 2;
if (ix >= hashArea.length) {
hashArea = Arrays.copyOf(hashArea, hashArea.length + 4);
}
}
}
hashArea[ix] = key;
hashArea[ix+1] = entry.getValue();
}
return new CompactStringObjectMap(mask, spillCount, hashArea);
}
private final static int findSize(int size)
{
if (size <= 5) {
return 8;
}
if (size <= 12) {
return 16;
}
int needed = size + (size >> 2); // at most 80% full
int result = 32;
while (result < needed) {
result += result;
}
return result;
}
public Object find(String key) {
int slot = key.hashCode() & _hashMask;
int ix = (slot<<1);
Object match = _hashArea[ix];
if ((match == key) || key.equals(match)) {
return _hashArea[ix+1];
}
return _find2(key, slot, match);
}
private final Object _find2(String key, int slot, Object match)
{
if (match == null) {
return null;
}
int hashSize = _hashMask+1;
int ix = hashSize + (slot>>1) << 1;
match = _hashArea[ix];
if (key.equals(match)) {
return _hashArea[ix+1];
}
if (match != null) { // _findFromSpill(...)
int i = (hashSize + (hashSize>>1)) << 1;
for (int end = i + _spillCount; i < end; i += 2) {
match = _hashArea[i];
if ((match == key) || key.equals(match)) {
return _hashArea[i+1];
}
}
}
return null;
}
public List<String> keys() {
final int end = _hashArea.length;
List<String> keys = new ArrayList<String>(end >> 2);
for (int i = 0; i < end; i += 2) {
Object key = _hashArea[i];
if (key != null) {
keys.add((String) key);
}
}
return keys;
}
}