Created
June 5, 2019 09:46
-
-
Save circlee/37e4a0a72d90bc6e37500a9c352e6c7a to your computer and use it in GitHub Desktop.
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
/** | |
* Initializes or doubles table size. If null, allocates in | |
* accord with initial capacity target held in field threshold. | |
* Otherwise, because we are using power-of-two expansion, the | |
* elements from each bin must either stay at same index, or move | |
* with a power of two offset in the new table. | |
* | |
* @return the table | |
*/ | |
final Node<K,V>[] resize() { | |
Node<K,V>[] oldTab = table; | |
int oldCap = (oldTab == null) ? 0 : oldTab.length; | |
int oldThr = threshold; | |
int newCap, newThr = 0; | |
if (oldCap > 0) { | |
if (oldCap >= MAXIMUM_CAPACITY) { | |
threshold = Integer.MAX_VALUE; | |
return oldTab; | |
} | |
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && | |
oldCap >= DEFAULT_INITIAL_CAPACITY) | |
newThr = oldThr << 1; // double threshold | |
} | |
else if (oldThr > 0) // initial capacity was placed in threshold | |
newCap = oldThr; | |
else { // zero initial threshold signifies using defaults | |
newCap = DEFAULT_INITIAL_CAPACITY; | |
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); | |
} | |
if (newThr == 0) { | |
float ft = (float)newCap * loadFactor; | |
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? | |
(int)ft : Integer.MAX_VALUE); | |
} | |
threshold = newThr; | |
@SuppressWarnings({"rawtypes","unchecked"}) | |
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; | |
table = newTab; | |
if (oldTab != null) { | |
for (int j = 0; j < oldCap; ++j) { | |
Node<K,V> e; | |
if ((e = oldTab[j]) != null) { | |
oldTab[j] = null; | |
if (e.next == null) | |
newTab[e.hash & (newCap - 1)] = e; | |
else if (e instanceof TreeNode) | |
((TreeNode<K,V>)e).split(this, newTab, j, oldCap); | |
else { // preserve order | |
Node<K,V> loHead = null, loTail = null; | |
Node<K,V> hiHead = null, hiTail = null; | |
Node<K,V> next; | |
do { | |
next = e.next; | |
if ((e.hash & oldCap) == 0) { | |
if (loTail == null) | |
loHead = e; | |
else | |
loTail.next = e; | |
loTail = e; | |
} | |
else { | |
if (hiTail == null) | |
hiHead = e; | |
else | |
hiTail.next = e; | |
hiTail = e; | |
} | |
} while ((e = next) != null); | |
if (loTail != null) { | |
loTail.next = null; | |
newTab[j] = loHead; | |
} | |
if (hiTail != null) { | |
hiTail.next = null; | |
newTab[j + oldCap] = hiHead; | |
} | |
} | |
} | |
} | |
} | |
return newTab; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment