Created
March 20, 2015 01:14
-
-
Save ThomasLau/cf553fb004a004ea29b4 to your computer and use it in GitHub Desktop.
how HashMap returns the proper-size,which is a power of two size,according to the initial input size
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Returns a power of two size for the given target capacity. | |
*/ | |
static final int tableSizeFor(int cap) { | |
int n = cap - 1; | |
n |= n >>> 1; | |
n |= n >>> 2; | |
n |= n >>> 4; | |
n |= n >>> 8; | |
n |= n >>> 16; | |
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; | |
} | |
public HashMap(int initialCapacity, float loadFactor) { | |
if (initialCapacity < 0) | |
throw new IllegalArgumentException("Illegal initial capacity: " + | |
initialCapacity); | |
if (initialCapacity > MAXIMUM_CAPACITY) | |
initialCapacity = MAXIMUM_CAPACITY; | |
if (loadFactor <= 0 || Float.isNaN(loadFactor)) | |
throw new IllegalArgumentException("Illegal load factor: " + | |
loadFactor); | |
this.loadFactor = loadFactor; | |
this.threshold = tableSizeFor(initialCapacity); | |
} | |
/* | |
** above all list,this explains why hashmap's size is always a power-of-two size, | |
** and this is also different from HashTable,which has no tableSizeFor to return a power-of-two size | |
** infact in HashTable: | |
*/ | |
public Hashtable(int initialCapacity, float loadFactor) { | |
if (initialCapacity < 0) | |
throw new IllegalArgumentException("Illegal Capacity: "+ | |
initialCapacity); | |
if (loadFactor <= 0 || Float.isNaN(loadFactor)) | |
throw new IllegalArgumentException("Illegal Load: "+loadFactor); | |
if (initialCapacity==0) | |
initialCapacity = 1; | |
this.loadFactor = loadFactor; | |
table = new Entry<?,?>[initialCapacity]; | |
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); | |
} | |
/** | |
* Constructs a new, empty hashtable with a default initial capacity (11) | |
* and load factor (0.75). | |
*/ | |
public Hashtable() { | |
this(11, 0.75f); | |
} | |
/** | |
* Increases the capacity of and internally reorganizes this | |
* hashtable, in order to accommodate and access its entries more | |
* efficiently. This method is called automatically when the | |
* number of keys in the hashtable exceeds this hashtable's capacity | |
* and load factor. | |
*/ | |
@SuppressWarnings("unchecked") | |
protected void rehash() { | |
int oldCapacity = table.length; | |
Entry<?,?>[] oldMap = table; | |
// overflow-conscious code | |
int newCapacity = (oldCapacity << 1) + 1; | |
if (newCapacity - MAX_ARRAY_SIZE > 0) { | |
if (oldCapacity == MAX_ARRAY_SIZE) | |
// Keep running with MAX_ARRAY_SIZE buckets | |
return; | |
newCapacity = MAX_ARRAY_SIZE; | |
} | |
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity]; | |
modCount++; | |
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); | |
table = newMap; | |
for (int i = oldCapacity ; i-- > 0 ;) { | |
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) { | |
Entry<K,V> e = old; | |
old = old.next; | |
int index = (e.hash & 0x7FFFFFFF) % newCapacity; | |
e.next = (Entry<K,V>)newMap[index]; | |
newMap[index] = e; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment