This implementation provides constant-time performance for the basic * operations (get and put), assuming the hash function * disperses the elements properly among the buckets. Iteration over * collection views requires time proportional to the "capacity" of the * HashMap instance (the number of buckets) plus its size (the number * of key-value mappings). Thus, it's very important not to set the initial * capacity too high (or the load factor too low) if iteration performance is * important. * *
An instance of HashMap has two parameters that affect its * performance: initial capacity and load factor. The * capacity is the number of buckets in the hash table, and the initial * capacity is simply the capacity at the time the hash table is created. The * load factor is a measure of how full the hash table is allowed to * get before its capacity is automatically increased. When the number of * entries in the hash table exceeds the product of the load factor and the * current capacity, the hash table is rehashed (that is, internal data * structures are rebuilt) so that the hash table has approximately twice the * number of buckets. * *
As a general rule, the default load factor (.75) offers a good tradeoff * between time and space costs. Higher values decrease the space overhead * but increase the lookup cost (reflected in most of the operations of the * HashMap class, including get and put). The * expected number of entries in the map and its load factor should be taken * into account when setting its initial capacity, so as to minimize the * number of rehash operations. If the initial capacity is greater * than the maximum number of entries divided by the load factor, no * rehash operations will ever occur. * *
If many mappings are to be stored in a HashMap instance, * creating it with a sufficiently large capacity will allow the mappings to * be stored more efficiently than letting it perform automatic rehashing as * needed to grow the table. * *
Note that this implementation is not synchronized. * If multiple threads access a hash map concurrently, and at least one of * the threads modifies the map structurally, it must be * synchronized externally. (A structural modification is any operation * that adds or deletes one or more mappings; merely changing the value * associated with a key that an instance already contains is not a * structural modification.) This is typically accomplished by * synchronizing on some object that naturally encapsulates the map. * * If no such object exists, the map should be "wrapped" using the * {@link Collections#synchronizedMap Collections.synchronizedMap} * method. This is best done at creation time, to prevent accidental * unsynchronized access to the map:
* Map m = Collections.synchronizedMap(new HashMap(...));* *
The iterators returned by all of this class's "collection view methods" * are fail-fast: if the map is structurally modified at any time after * the iterator is created, in any way except through the iterator's own * remove method, the iterator will throw a * {@link ConcurrentModificationException}. Thus, in the face of concurrent * modification, the iterator fails quickly and cleanly, rather than risking * arbitrary, non-deterministic behavior at an undetermined time in the * future. * *
Note that the fail-fast behavior of an iterator cannot be guaranteed * as it is, generally speaking, impossible to make any hard guarantees in the * presence of unsynchronized concurrent modification. Fail-fast iterators * throw ConcurrentModificationException on a best-effort basis. * Therefore, it would be wrong to write a program that depended on this * exception for its correctness: the fail-fast behavior of iterators * should be used only to detect bugs. * *
This class is a member of the
*
* Java Collections Framework.
*
* @param More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* A return value of {@code null} does not necessarily
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
int hash = UNIQUE;
if (key != null) {
hash |= hash(key.hashCode());
Object[] kvs = kvTable;
if (kvs != null) {
int[] hs = hashes;
int mask = hs.length - 1;
int h = hash; // unmasked hs index
Object k; // key at kvs[j]
int j; // index of key (Value in j+1, Hash in hs[j>>>1])
int s; // the hash for k, maybe OR'ed with UNIQUE
while ((k = kvs[j = (h & mask) << 1]) != null) {
Object v = kvs[j + 1]; // prefetch value
if (k == key || (((s = hs[j >>> 1]) | UNIQUE) == hash &&
k.equals(key)))
return (V) v;
if (s < 0)
break; // if unique mapping, can stop probing
h = nextProbe(h);
}
}
}
return trie != null? (V) trie.get(hash, key) : null;
}
/**
* Returns true if this map contains a mapping for the
* specified key.
*
* @param key The key whose presence in this map is to be tested
* @return true if this map contains a mapping for the specified
* key.
*/
public boolean containsKey(Object key) {
// Annoyingly nearly cloned from get
int hash = UNIQUE;
if (key != null) {
hash |= hash(key.hashCode());
Object[] kvs = kvTable;
if (kvs != null) {
int[] hs = hashes;
int mask = hs.length - 1;
int h = hash;
Object k;
int j;
int s;
while ((k = kvs[j = (h & mask) << 1]) != null) {
if (k == key || (((s = hs[j >>> 1]) | UNIQUE) == hash &&
k.equals(key)))
return true;
if (s < 0)
break;
h = nextProbe(h);
}
}
}
return trie != null && trie.containsKey(hash, key);
}
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with key, or
* null if there was no mapping for key.
* (A null return can also indicate that the map
* previously associated null with key.)
*/
public V put(K key, V value) {
if (key == null)
return triePut(UNIQUE, null, value); // offload
int hash = hash(key.hashCode()) | UNIQUE;
if (size >= threshold)
resize();
Object[] kvs = kvTable;
int[] hs = hashes;
int mask = hs.length - 1;
int h = hash;
int firstDeleted = -1; // to reuse deleted slot
Object k;
int j;
while ((k = kvs[j = (h & mask) << 1]) != null) {
int s = hs[j >>> 1];
if (k == key || ((s | UNIQUE) == hash && k.equals(key))) {
Object v = kvs[j + 1];
kvs[j + 1] = value;
return (V)v;
}
if (s < 0) // mark index as shared
hs[j >>> 1] = s & ~UNIQUE;
else if (k == ABSENT && firstDeleted < 0)
firstDeleted = j;
h = nextProbe(h);
}
if (trie != null)
return triePut(hash, key, value);
if (firstDeleted >= 0) {
j = firstDeleted;
hash &= ~UNIQUE;
++threshold; // adjust for reusing deleted slot
}
kvs[j] = key;
kvs[j + 1] = value;
hs[j >>> 1] = hash;
++modCount;
++size;
return null;
}
/**
* Version of put for overflow or null key
*/
private V triePut(int hash, K key, V value) {
HashTrie t = trie;
if (t == null)
t = trie = new HashTrie();
Object v = t.put(hash, key, value);
if (v != ABSENT)
return (V) v;
++modCount;
++size;
return null;
}
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
* any of the keys currently in the specified map.
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map m) {
int n = m.size();
if (n == 0)
return;
int t = threshold;
if (n > t) {
if (t < 0) // already holds stored threshold
t = -t;
int nt = (int)(n / loadFactor + 1);
if (nt > t)
threshold = -nt; // force resize on put
}
for (Entry e : m.entrySet())
put(e.getKey(), e.getValue());
}
/**
* Resize the table
*/
private void resize() {
Object[] oldKvs = kvTable;
int[] oldHs = hashes;
int oldCap = oldHs == null? 0 : oldHs.length;
int oldThreshold = threshold;
int cap;
if (oldThreshold < 0) // try to use stashed capacity
cap = -oldThreshold;
else if (size < oldCap >>> 1) // possibly shrink after deletions
cap = (int)((size + (size >>> 1)) / loadFactor + 1);
else
cap = oldCap << 1;
if (cap > CEILING_LENGTH >>> 1) { // overflow
threshold = Integer.MAX_VALUE; // avoid future resizes
if (trie == null)
trie = new HashTrie();
if (oldHs != null)
return;
else // overflow on init -- use minimal arrays
cap = MINIMUM_LENGTH;
}
else {
if (cap < MINIMUM_LENGTH || (cap & (cap - 1)) != 0) {
int c = cap; // force power of two
cap = MINIMUM_LENGTH;
while (cap < c) cap <<= 1;
}
threshold = (int)(cap * loadFactor);
}
int[] newHs = hashes = new int[cap];
Object[] newKvs = kvTable = new Object[cap << 1];
if (oldHs != null && size != 0) {
int mask = cap - 1;
for (int m = 0; m < oldKvs.length; m += 2) {
Object key = oldKvs[m];
if (key != null && key != ABSENT) {
Object value = oldKvs[m + 1];
int hash = oldHs[m >>> 1] | UNIQUE;
int h = hash;
int j;
while (newKvs[j = (h & mask) << 1] != null) {
newHs[j >>> 1] &= ~UNIQUE;
h = nextProbe(h);
}
newKvs[j] = key;
newKvs[j + 1] = value;
newHs[j >>> 1] = hash;
}
}
}
}
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @return the previous value associated with key, or
* null if there was no mapping for key.
* (A null return can also indicate that the map
* previously associated null with key.)
*/
public V remove(Object key) {
int hash = UNIQUE;
if (key != null) {
hash |= hash(key.hashCode());
Object v = tableRemove(hash, key, ABSENT);
if (v != ABSENT)
return (V) v;
}
if (trie != null) {
Object v = trie.remove(hash, key, ABSENT);
if (v != ABSENT) {
++modCount;
--size;
return (V) v;
}
}
return null;
}
/**
* Remove key only if mapped to target value.
* (Needed by EntrySets).
*/
boolean removeMapping(Object key, Object target) {
int hash = UNIQUE;
if (key != null) {
hash |= hash(key.hashCode());
if (tableRemove(hash, key, target) != ABSENT)
return true;
}
if (trie != null && trie.remove(hash, key, target) != ABSENT) {
++modCount;
--size;
return true;
}
return false;
}
/**
* Remove from table if present
* @param hash hash for key
* @param key key
* @param target if not ABSENT, only remove if key maps to it
* @return old value, or ABSENT if not found
*/
final Object tableRemove(int hash, Object key, Object target) {
Object[] kvs = kvTable;
if (kvs != null) {
int[] hs = hashes;
int mask = hs.length - 1;
int j;
Object k;
int h = hash;
while ((k = kvs[j = (h & mask) << 1]) != null) {
int s = hs[j >>> 1];
if (k == key || ((s | UNIQUE) == hash && k.equals(key))) {
Object v = kvs[j + 1];
if (target != ABSENT &&
(target != v && (target != null || !target.equals(v))))
break;
++modCount;
if (--size > 0 || !maybeClearOnRemove()) {
kvs[j + 1] = null;
if (s < 0) { // unique
kvs[j] = null;
hs[j >>> 1] = 0;
}
else {
kvs[j] = ABSENT;
hs[j >>> 1] = ABSENT_HASH_CODE;
--threshold; // to trigger cleaning
}
}
return v;
}
if (s < 0)
break;
h = nextProbe(h);
}
}
return ABSENT;
}
/**
* Possibly clear table upon removing last element
*/
private boolean maybeClearOnRemove() {
int[] hs = hashes;
if (hs == null)
return true; // already clear
int cap = hs.length;
if (threshold >= (int)(cap * loadFactor))
return false; // no ABSENT items
threshold = -cap; // record to recreate on put
hashes = null;
kvTable = null;
return true;
}
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
int[] hs = hashes;
if (hs != null) { // drop tables
threshold = -hs.length; // record to recreate on put
hashes = null;
kvTable = null;
}
trie = null;
modCount++;
size = 0;
}
/**
* Tests whether the specified object reference is a value in this map.
*
* @param value value whose presence in this map is to be tested
* @return true if this map maps one or more keys to the
* specified object reference
* @see #containsKey(Object)
*/
public boolean containsValue(Object value) {
Object[] kvs = kvTable;
if (kvs != null) {
for (int j = 0; j < kvs.length; j += 2) {
Object k = kvs[j];
Object v = kvs[j + 1];
if (k != null && k != ABSENT &&
(value == v || (value != null && value.equals(v))))
return true;
}
}
return trie != null && trie.containsValue(value);
}
/**
* Returns a shallow copy of this HashMap instance: the keys and
* values themselves are not cloned.
*
* @return a shallow copy of this map
*/
public Object clone() {
try {
XHashMapV2 This implementation iterates over entrySet(), calling
* {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
* set, and adding up the results.
*
* @return the hash code value for this map
* @see Map.Entry#hashCode()
* @see Object#equals(Object)
* @see Set#equals(Object)
*/
public int hashCode() {
int sum = 0;
Object[] kvs = kvTable;
if (kvs != null) {
Object k;
for (int j = 0; j < kvs.length; j += 2) {
if ((k = kvs[j]) != null && k != ABSENT)
sum += pairHash(k, kvs[j + 1]);
}
}
if (trie != null) {
for (TrieNode t = trie.first; t != null; t = t.next)
sum += pairHash(t.key, t.value);
}
return sum;
}
/**
* Utility for entrySets and Map.equals
* Static to allow calls from other map in equals
*/
static boolean containsMapping(Map m, Object key, Object value) {
Object v = m.get(key);
if (value == null)
return v == null && m.containsKey(key);
else
return value == v || (value != null && value.equals(v));
}
/**
* Compares the specified object with this map for equality. Returns
* true if the given object is also a map and the two maps
* represent the same mappings. More formally, two maps m1 and
* m2 represent the same mappings if
* m1.entrySet().equals(m2.entrySet()). This ensures that the
* equals method works properly across different implementations
* of the Map interface.
*
* This implementation first checks if the specified object is this map;
* if so it returns true. Then, it checks if the specified
* object is a map whose size is identical to the size of this map; if
* not, it returns false. If so, it iterates over this map's
* entrySet collection, and checks that the specified map
* contains each mapping that this map contains. If the specified map
* fails to contain such a mapping, false is returned. If the
* iteration completes, true is returned.
*
* @param o object to be compared for equality with this map
* @return true if the specified object is equal to this map
*/
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map