Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Copyright (c) 2008, Nathan Sweet
   * All rights reserved.
   * 
   * Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
   * conditions are met:
   * 
   * - Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
   * - Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
   * disclaimer in the documentation and/or other materials provided with the distribution.
  * - Neither the name of Esoteric Software nor the names of its contributors may be used to endorse or promote products derived
  * from this software without specific prior written permission.
  * 
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
  * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
 
 package com.esotericsoftware.kryo.util;
 
An unordered map. This implementation is a cuckoo hash map using 3 hashes, random walking, and a small stash for problematic keys. Null keys are not allowed. Null values are allowed. No allocation is done except when growing the table size.

This map performs very fast get, containsKey, and remove (typically O(1), worst case O(log(n))). Put may be a bit slower, depending on hash collisions. Load factors greater than 0.91 greatly increase the chances the map will have to rehash to the next higher POT size.

Author(s):
Nathan Sweet
 
 public class ObjectMap<K, V> {
 	private static final int PRIME1 = 0xbe1f14b1;
 	private static final int PRIME2 = 0xb4b82e39;
 	private static final int PRIME3 = 0xced1c241;
 
 	static Random random = new Random();
 
 	public int size;
 
 	K[] keyTable;
 	V[] valueTable;
 
 	private float loadFactor;
 	private int hashShiftmaskthreshold;
 	private int stashCapacity;
 	private int pushIterations;

Creates a new map with an initial capacity of 32 and a load factor of 0.8. This map will hold 25 items before growing the backing table.
 
 	public ObjectMap () {
 		this(32, 0.8f);
 	}

Creates a new map with a load factor of 0.8. This map will hold initialCapacity * 0.8 items before growing the backing table.
 
 	public ObjectMap (int initialCapacity) {
 		this(initialCapacity, 0.8f);
 	}

Creates a new map with the specified initial capacity and load factor. This map will hold initialCapacity * loadFactor items before growing the backing table.
 
 	public ObjectMap (int initialCapacityfloat loadFactor) {
 		if (initialCapacity < 0) throw new IllegalArgumentException("initialCapacity must be >= 0: " + initialCapacity);
 		if (initialCapacity > 1 << 30) throw new IllegalArgumentException("initialCapacity is too large: " + initialCapacity);
 		 = nextPowerOfTwo(initialCapacity);
 
 		if (loadFactor <= 0) throw new IllegalArgumentException("loadFactor must be > 0: " + loadFactor);
 		this. = loadFactor;
 
 		 = (int)( * loadFactor);
 		 =  - 1;
 		 = Math.max(3, (int)Math.ceil(Math.log()) * 2);
 		 = Math.max(Math.min(, 8), (int)Math.sqrt() / 8);
 
 		 = (K[])new Object[ + ];
 		 = (V[])new Object[.];
 	}

Creates a new map identical to the specified map.
 
 	public ObjectMap (ObjectMap<? extends K, ? extends V> map) {
 		this(map.capacitymap.loadFactor);
 		 = map.stashSize;
 		System.arraycopy(map.keyTable, 0, , 0, map.keyTable.length);
 		System.arraycopy(map.valueTable, 0, , 0, map.valueTable.length);
 		 = map.size;
 	}

Returns the old value associated with the specified key, or null.
 
 	public V put (K key, V value) {
 		if (key == nullthrow new IllegalArgumentException("key cannot be null.");
 		return put_internal(keyvalue);
 	}
 
 	private V put_internal (K key, V value) {
		K[] keyTable = this.;
		// Check for existing keys.
		int hashCode = key.hashCode();
		int index1 = hashCode & ;
key1 = keyTable[index1];
		if (key.equals(key1)) {
oldValue = [index1];
			[index1] = value;
			return oldValue;
		}
		int index2 = hash2(hashCode);
key2 = keyTable[index2];
		if (key.equals(key2)) {
oldValue = [index2];
			[index2] = value;
			return oldValue;
		}
		int index3 = hash3(hashCode);
key3 = keyTable[index3];
		if (key.equals(key3)) {
oldValue = [index3];
			[index3] = value;
			return oldValue;
		}
		// Update key in the stash.
		for (int i = n = i + i < ni++) {
			if (key.equals(keyTable[i])) {
oldValue = [i];
				[i] = value;
				return oldValue;
			}
		}
		// Check for empty buckets.
		if (key1 == null) {
			keyTable[index1] = key;
			[index1] = value;
			if (++ >= resize( << 1);
			return null;
		}
		if (key2 == null) {
			keyTable[index2] = key;
			[index2] = value;
			if (++ >= resize( << 1);
			return null;
		}
		if (key3 == null) {
			keyTable[index3] = key;
			[index3] = value;
			if (++ >= resize( << 1);
			return null;
		}
		push(keyvalueindex1key1index2key2index3key3);
		return null;
	}
	public void putAll (ObjectMap<K, V> map) {
		ensureCapacity(map.size);
		for (Entry<K, V> entry : map.entries())
			put(entry.keyentry.value);
	}

Skips checks for existing keys.
	private void putResize (K key, V value) {
		// Check for empty buckets.
		int hashCode = key.hashCode();
		int index1 = hashCode & ;
key1 = [index1];
		if (key1 == null) {
			[index1] = key;
			[index1] = value;
			if (++ >= resize( << 1);
			return;
		}
		int index2 = hash2(hashCode);
key2 = [index2];
		if (key2 == null) {
			[index2] = key;
			[index2] = value;
			if (++ >= resize( << 1);
			return;
		}
		int index3 = hash3(hashCode);
key3 = [index3];
		if (key3 == null) {
			[index3] = key;
			[index3] = value;
			if (++ >= resize( << 1);
			return;
		}
		push(keyvalueindex1key1index2key2index3key3);
	}
	private void push (K insertKey, V insertValueint index1, K key1int index2, K key2int index3, K key3) {
		K[] keyTable = this.;
		V[] valueTable = this.;
		int mask = this.;
		// Push keys until an empty bucket is found.
evictedKey;
evictedValue;
		int i = 0, pushIterations = this.;
		do {
			// Replace the key and value for one of the hashes.
			switch (.nextInt(3)) {
			case 0:
				evictedKey = key1;
				evictedValue = valueTable[index1];
				keyTable[index1] = insertKey;
				valueTable[index1] = insertValue;
				break;
			case 1:
				evictedKey = key2;
				evictedValue = valueTable[index2];
				keyTable[index2] = insertKey;
				valueTable[index2] = insertValue;
				break;
			default:
				evictedKey = key3;
				evictedValue = valueTable[index3];
				keyTable[index3] = insertKey;
				valueTable[index3] = insertValue;
				break;
			}
			// If the evicted key hashes to an empty bucket, put it there and stop.
			int hashCode = evictedKey.hashCode();
			index1 = hashCode & mask;
			key1 = keyTable[index1];
			if (key1 == null) {
				keyTable[index1] = evictedKey;
				valueTable[index1] = evictedValue;
				if (++ >= resize( << 1);
				return;
			}
			index2 = hash2(hashCode);
			key2 = keyTable[index2];
			if (key2 == null) {
				keyTable[index2] = evictedKey;
				valueTable[index2] = evictedValue;
				if (++ >= resize( << 1);
				return;
			}
			index3 = hash3(hashCode);
			key3 = keyTable[index3];
			if (key3 == null) {
				keyTable[index3] = evictedKey;
				valueTable[index3] = evictedValue;
				if (++ >= resize( << 1);
				return;
			}
			if (++i == pushIterationsbreak;
			insertKey = evictedKey;
			insertValue = evictedValue;
while (true);
		putStash(evictedKeyevictedValue);
	}
	private void putStash (K key, V value) {
			// Too many pushes occurred and the stash is full, increase the table size.
			put_internal(keyvalue);
			return;
		}
		// Store key in the stash.
		int index =  + ;
		[index] = key;
		[index] = value;
	}
	public V get (K key) {
		int hashCode = key.hashCode();
		int index = hashCode & ;
		if (!key.equals([index])) {
			index = hash2(hashCode);
			if (!key.equals([index])) {
				index = hash3(hashCode);
				if (!key.equals([index])) return getStash(key);
			}
		}
		return [index];
	}
	private V getStash (K key) {
		K[] keyTable = this.;
		for (int i = n = i + i < ni++)
			if (key.equals(keyTable[i])) return [i];
		return null;
	}

Returns the value for the specified key, or the default value if the key is not in the map.
	public V get (K key, V defaultValue) {
		int hashCode = key.hashCode();
		int index = hashCode & ;
		if (!key.equals([index])) {
			index = hash2(hashCode);
			if (!key.equals([index])) {
				index = hash3(hashCode);
				if (!key.equals([index])) return getStash(keydefaultValue);
			}
		}
		return [index];
	}
	private V getStash (K key, V defaultValue) {
		K[] keyTable = this.;
		for (int i = n = i + i < ni++)
			if (key.equals(keyTable[i])) return [i];
		return defaultValue;
	}
	public V remove (K key) {
		int hashCode = key.hashCode();
		int index = hashCode & ;
		if (key.equals([index])) {
			[index] = null;
oldValue = [index];
			[index] = null;
			return oldValue;
		}
		index = hash2(hashCode);
		if (key.equals([index])) {
			[index] = null;
oldValue = [index];
			[index] = null;
			return oldValue;
		}
		index = hash3(hashCode);
		if (key.equals([index])) {
			[index] = null;
oldValue = [index];
			[index] = null;
			return oldValue;
		}
		return removeStash(key);
	}
removeStash (K key) {
		K[] keyTable = this.;
		for (int i = n = i + i < ni++) {
			if (key.equals(keyTable[i])) {
oldValue = [i];
				return oldValue;
			}
		}
		return null;
	}
	void removeStashIndex (int index) {
		// If the removed location was not last, move the last tuple to the removed location.
		int lastIndex =  + ;
		if (index < lastIndex) {
			[index] = [lastIndex];
			[index] = [lastIndex];
			[lastIndex] = null;
else
			[index] = null;
	}

Reduces the size of the backing arrays to be the specified capacity or less. If the capacity is already less, nothing is done. If the map contains more items than the specified capacity, the next highest power of two capacity is used instead.
	public void shrink (int maximumCapacity) {
		if (maximumCapacity < 0) throw new IllegalArgumentException("maximumCapacity must be >= 0: " + maximumCapacity);
		if ( > maximumCapacitymaximumCapacity = ;
		if ( <= maximumCapacityreturn;
		maximumCapacity = nextPowerOfTwo(maximumCapacity);
		resize(maximumCapacity);
	}

Clears the map and reduces the size of the backing arrays to be the specified capacity if they are larger.
	public void clear (int maximumCapacity) {
		if ( <= maximumCapacity) {
			return;
		}
		 = 0;
		resize(maximumCapacity);
	}
	public void clear () {
		K[] keyTable = this.;
		V[] valueTable = this.;
		for (int i =  + i-- > 0;) {
			keyTable[i] = null;
			valueTable[i] = null;
		}
		 = 0;
		 = 0;
	}

Returns true if the specified value is in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

Parameters:
identity If true, uses == to compare the specified value with values in the map. If false, uses java.lang.Object.equals(java.lang.Object).
	public boolean containsValue (Object valueboolean identity) {
		V[] valueTable = this.;
		if (value == null) {
			K[] keyTable = this.;
			for (int i =  + i-- > 0;)
				if (keyTable[i] != null && valueTable[i] == nullreturn true;
else if (identity) {
			for (int i =  + i-- > 0;)
				if (valueTable[i] == valuereturn true;
else {
			for (int i =  + i-- > 0;)
				if (value.equals(valueTable[i])) return true;
		}
		return false;
	}
	public boolean containsKey (K key) {
		int hashCode = key.hashCode();
		int index = hashCode & ;
		if (!key.equals([index])) {
			index = hash2(hashCode);
			if (!key.equals([index])) {
				index = hash3(hashCode);
				if (!key.equals([index])) return containsKeyStash(key);
			}
		}
		return true;
	}
	private boolean containsKeyStash (K key) {
		K[] keyTable = this.;
		for (int i = n = i + i < ni++)
			if (key.equals(keyTable[i])) return true;
		return false;
	}

Returns the key for the specified value, or null if it is not in the map. Note this traverses the entire map and compares every value, which may be an expensive operation.

Parameters:
identity If true, uses == to compare the specified value with values in the map. If false, uses java.lang.Object.equals(java.lang.Object).
	public K findKey (Object valueboolean identity) {
		V[] valueTable = this.;
		if (value == null) {
			K[] keyTable = this.;
			for (int i =  + i-- > 0;)
				if (keyTable[i] != null && valueTable[i] == nullreturn keyTable[i];
else if (identity) {
			for (int i =  + i-- > 0;)
				if (valueTable[i] == valuereturn [i];
else {
			for (int i =  + i-- > 0;)
				if (value.equals(valueTable[i])) return [i];
		}
		return null;
	}

Increases the size of the backing array to acommodate the specified number of additional items. Useful before adding many items to avoid multiple backing array resizes.
	public void ensureCapacity (int additionalCapacity) {
		int sizeNeeded =  + additionalCapacity;
		if (sizeNeeded >= resize(nextPowerOfTwo((int)(sizeNeeded / )));
	}
	private void resize (int newSize) {
		int oldEndIndex =  + ;
		 = newSize;
		 = (int)(newSize * );
		 = newSize - 1;
		 = 31 - Integer.numberOfTrailingZeros(newSize);
		 = Math.max(3, (int)Math.ceil(Math.log(newSize)) * 2);
		 = Math.max(Math.min(newSize, 8), (int)Math.sqrt(newSize) / 8);
		K[] oldKeyTable = ;
		V[] oldValueTable = ;
		 = (K[])new Object[newSize + ];
		 = (V[])new Object[newSize + ];
		int oldSize = ;
		 = 0;
		 = 0;
		if (oldSize > 0) {
			for (int i = 0; i < oldEndIndexi++) {
key = oldKeyTable[i];
				if (key != nullputResize(keyoldValueTable[i]);
			}
		}
	}
	private int hash2 (int h) {
		h *= ;
		return (h ^ h >>> ) & ;
	}
	private int hash3 (int h) {
		h *= ;
		return (h ^ h >>> ) & ;
	}
	public String toString () {
		if ( == 0) return "{}";
		StringBuilder buffer = new StringBuilder(32);
		buffer.append('{');
		K[] keyTable = this.;
		V[] valueTable = this.;
		int i = keyTable.length;
		while (i-- > 0) {
key = keyTable[i];
			if (key == nullcontinue;
			buffer.append(key);
			buffer.append('=');
			buffer.append(valueTable[i]);
			break;
		}
		while (i-- > 0) {
key = keyTable[i];
			if (key == nullcontinue;
			buffer.append(", ");
			buffer.append(key);
			buffer.append('=');
			buffer.append(valueTable[i]);
		}
		buffer.append('}');
		return buffer.toString();
	}

Returns an iterator for the entries in the map. Remove is supported.
	public Entries<K, V> entries () {
		return new Entries(this);
	}

Returns an iterator for the values in the map. Remove is supported.
	public Values<V> values () {
		return new Values(this);
	}

Returns an iterator for the keys in the map. Remove is supported.
	public Keys<K> keys () {
		return new Keys(this);
	}
	static public class Entry<K, V> {
		public K key;
		public V value;
		public String toString () {
			return  + "=" + ;
		}
	}
	static private class MapIterator<K, V> {
		public boolean hasNext;
		final ObjectMap<K, V> map;
		public MapIterator (ObjectMap<K, V> map) {
			this. = map;
		}
		public void reset () {
			 = -1;
		}
		void advance () {
			 = false;
			K[] keyTable = .;
			for (int n = . + .; ++ < n;) {
				if (keyTable[] != null) {
					 = true;
					break;
				}
			}
		}
		public void remove () {
			if ( < 0) throw new IllegalStateException("next must be called before remove.");
else {
			}
		}
	}
	static public class Entries<K, V> extends MapIterator<K, V> implements Iterable<Entry<K, V>>, Iterator<Entry<K, V>> {
		Entry<K, V> entry = new Entry();
		public Entries (ObjectMap<K, V> map) {
			super(map);
		}

Note the same entry instance is returned each time this method is called.
		public Entry<K, V> next () {
			if (!throw new NoSuchElementException();
			K[] keyTable = .;
			. = keyTable[];
			return ;
		}
		public boolean hasNext () {
			return ;
		}
		public Iterator<Entry<K, V>> iterator () {
			return this;
		}
	}
	static public class Values<V> extends MapIterator<Object, V> implements Iterable<V>, Iterator<V> {
		public Values (ObjectMap<?, V> map) {
			super((ObjectMap<Object, V>)map);
		}
		public boolean hasNext () {
			return ;
		}
		public V next () {
			if (!throw new NoSuchElementException();
value = .[];
			return value;
		}
		public Iterator<V> iterator () {
			return this;
		}

Returns a new array containing the remaining values.
		public ArrayList<V> toArray () {
			ArrayList array = new ArrayList(.);
			while ()
				array.add(next());
			return array;
		}

Adds the remaining values to the specified array.
		public void toArray (ArrayList<V> array) {
			while ()
				array.add(next());
		}
	}
	static public class Keys<K> extends MapIterator<K, Objectimplements Iterable<K>, Iterator<K> {
		public Keys (ObjectMap<K, ?> map) {
			super((ObjectMap<K, Object>)map);
		}
		public boolean hasNext () {
			return ;
		}
		public K next () {
			if (!throw new NoSuchElementException();
key = .[];
			return key;
		}
		public Iterator<K> iterator () {
			return this;
		}

Returns a new array containing the remaining keys.
		public ArrayList<K> toArray () {
			ArrayList array = new ArrayList(.);
			while ()
				array.add(next());
			return array;
		}
	}
	static public int nextPowerOfTwo (int value) {
		if (value == 0) return 1;
		value--;
		value |= value >> 1;
		value |= value >> 2;
		value |= value >> 4;
		value |= value >> 8;
		value |= value >> 16;
		return value + 1;
	}
New to GrepCode? Check out our FAQ X