| 152 |
|
* when overpopulated. However, since the vast majority of bins in |
| 153 |
|
* normal use are not overpopulated, checking for existence of |
| 154 |
|
* tree bins may be delayed in the course of table methods. |
| 155 |
– |
* Statistically, most operations in normal usages access only the |
| 156 |
– |
* first node (if present) of a bin, so most methods check this |
| 157 |
– |
* first, avoiding extra overhead and cache misses in the most |
| 158 |
– |
* common paths. |
| 155 |
|
* |
| 156 |
|
* Tree bins (i.e., bins whose elements are all TreeNodes) are |
| 157 |
|
* ordered primarily by hashCode, but in the case of ties, if two |
| 159 |
|
* type then their compareTo method is used for ordering. (We |
| 160 |
|
* conservatively check generic types via reflection to validate |
| 161 |
|
* this -- see method comparableClassFor). The added complexity |
| 162 |
< |
* of tree bins is worthwhile in providing worst-case O(n) |
| 162 |
> |
* of tree bins is worthwhile in providing worst-case O(log n) |
| 163 |
|
* operations when keys either have distinct hashes or are |
| 164 |
|
* orderable, Thus, performance degrades gracefully under |
| 165 |
|
* accidental or malicious usages in which hashCode() methods |
| 166 |
|
* return values that are poorly distributed, as well as those in |
| 167 |
|
* which many keys share a hashCode, so long as they are also |
| 168 |
< |
* Comparable. |
| 168 |
> |
* Comparable. (If neither of these apply, we may waste about a |
| 169 |
> |
* factor of two in time and space compared to taking no |
| 170 |
> |
* precautions. But the only known cases stem from poor user |
| 171 |
> |
* programming practices that are already so slow that this makes |
| 172 |
> |
* little difference.) |
| 173 |
|
* |
| 174 |
|
* Because TreeNodes are about twice the size of regular nodes, we |
| 175 |
|
* use them only when bins contain enough nodes to warrant use |
| 176 |
|
* (see TREEIFY_THRESHOLD). And when they become too small (due to |
| 177 |
< |
* remove() or resizing) they are converted back to plain bins. |
| 178 |
< |
* In usages with well-distributed user hashCodes, tree bins are |
| 177 |
> |
* removal or resizing) they are converted back to plain bins. In |
| 178 |
> |
* usages with well-distributed user hashCodes, tree bins are |
| 179 |
|
* rarely used. Ideally, under random hashCodes, the frequency of |
| 180 |
|
* nodes in bins follows a Poisson distribution |
| 181 |
|
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a |
| 202 |
|
* (method TreeNode.root()). |
| 203 |
|
* |
| 204 |
|
* All applicable internal methods accept a hash code as an |
| 205 |
< |
* argument (as normally supplied from a public method), allowing |
| 205 |
> |
* argument (as normally supplied from a public methd), allowing |
| 206 |
|
* them to call each other without recomputing user hashCodes. |
| 207 |
+ |
* Most internal methods also accept a "tab" argument, that is |
| 208 |
+ |
* normally the current table, but may be a new or old one when |
| 209 |
+ |
* resizing or converting. |
| 210 |
|
* |
| 211 |
|
* When bin lists are treeified, split, or untreeified, we keep |
| 212 |
|
* them in the same relative access/traversal order (i.e., field |
| 218 |
|
* complicated by the existence of subclass LinkedHashMap. See |
| 219 |
|
* below for hook methods defined to be invoked upon insertion, |
| 220 |
|
* removal and access that allow LinkedHashMap internals to |
| 221 |
< |
* otherwise remain independent of these mechanics. |
| 221 |
> |
* otherwise remain independent of these mechanics. (This also |
| 222 |
> |
* requires that a map instance be passed to some utility methods |
| 223 |
> |
* that may create new nodes.) |
| 224 |
|
* |
| 225 |
|
* Sorry if you don't like the concurrent-programming-like |
| 226 |
|
* SSA-based coding style, that helps avoid aliasing errors |
| 247 |
|
/** |
| 248 |
|
* The bin count threshold for using a tree rather than list for a |
| 249 |
|
* bin. Bins are converted to trees when adding an element to a |
| 250 |
< |
* bin with at least this many nodes. The value should be at least |
| 251 |
< |
* 8 to mesh with assumptions in tree removal about conversion |
| 252 |
< |
* back to plain bins upon shrinkage. |
| 250 |
> |
* bin with at least this many nodes. The value must be greater |
| 251 |
> |
* than 2 and should be at least 8 to mesh with assumptions in |
| 252 |
> |
* tree removal about conversion back to plain bins upon |
| 253 |
> |
* shrinkage. |
| 254 |
|
*/ |
| 255 |
|
static final int TREEIFY_THRESHOLD = 8; |
| 256 |
|
|
| 387 |
|
/** |
| 388 |
|
* The table, initialized on first use, and resized as |
| 389 |
|
* necessary. When allocated, length is always a power of two. |
| 390 |
< |
* (We also tolerate length zero for some read-only operations.) |
| 390 |
> |
* (We also tolerate length zero in some operations to allow |
| 391 |
> |
* bootstrapping mechanics that are currently not needed.) |
| 392 |
|
*/ |
| 393 |
|
transient Node<K,V>[] table; |
| 394 |
|
|
| 685 |
|
oldCap >= DEFAULT_INITIAL_CAPACITY) |
| 686 |
|
newThr = oldThr << 1; // double threshold |
| 687 |
|
} |
| 688 |
< |
else if (oldThr > 0) |
| 688 |
> |
else if (oldThr > 0) // initial capacity was placed in threshold |
| 689 |
|
newCap = oldThr; |
| 690 |
< |
else { |
| 690 |
> |
else { // zero initial threshold signifies using defaults |
| 691 |
|
newCap = DEFAULT_INITIAL_CAPACITY; |
| 692 |
|
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); |
| 693 |
|
} |
| 1304 |
|
} |
| 1305 |
|
|
| 1306 |
|
// These methods are also used when serializing HashSets |
| 1307 |
< |
final float loadFactor() { return loadFactor; } |
| 1307 |
> |
final float loadFactor() { return loadFactor; } |
| 1308 |
|
final int capacity() { |
| 1309 |
< |
return (table != null ? table.length : |
| 1310 |
< |
(threshold > 0 ? threshold : DEFAULT_INITIAL_CAPACITY)); |
| 1309 |
> |
return (table != null) ? table.length : |
| 1310 |
> |
(threshold > 0) ? threshold : |
| 1311 |
> |
DEFAULT_INITIAL_CAPACITY; |
| 1312 |
|
} |
| 1313 |
|
|
| 1314 |
|
/** |
| 1315 |
< |
* Saves the state of the <tt>HashMap</tt> instance to a stream (i.e., |
| 1316 |
< |
* serializes it). |
| 1315 |
> |
* Save the state of the <tt>HashMap</tt> instance to a stream (i.e., |
| 1316 |
> |
* serialize it). |
| 1317 |
|
* |
| 1318 |
|
* @serialData The <i>capacity</i> of the HashMap (the length of the |
| 1319 |
|
* bucket array) is emitted (int), followed by the |
| 1333 |
|
} |
| 1334 |
|
|
| 1335 |
|
/** |
| 1336 |
< |
* Reconstitutes the {@code HashMap} instance from a stream (i.e., |
| 1337 |
< |
* deserializes it). |
| 1336 |
> |
* Reconstitute the {@code HashMap} instance from a stream (i.e., |
| 1337 |
> |
* deserialize it). |
| 1338 |
|
*/ |
| 1339 |
|
private void readObject(java.io.ObjectInputStream s) |
| 1340 |
|
throws IOException, ClassNotFoundException { |
| 1407 |
|
throw new ConcurrentModificationException(); |
| 1408 |
|
if (e == null) |
| 1409 |
|
throw new NoSuchElementException(); |
| 1410 |
< |
current = e; |
| 1403 |
< |
if ((next = e.next) == null && (t = table) != null) { |
| 1410 |
> |
if ((next = (current = e).next) == null && (t = table) != null) { |
| 1411 |
|
do {} while (index < t.length && (next = t[index++]) == null); |
| 1412 |
|
} |
| 1413 |
|
return e; |
| 1424 |
|
removeNode(hash(key), key, null, false, false); |
| 1425 |
|
expectedModCount = modCount; |
| 1426 |
|
} |
| 1420 |
– |
|
| 1427 |
|
} |
| 1428 |
|
|
| 1429 |
|
final class KeyIterator extends HashIterator |
| 1773 |
|
|
| 1774 |
|
/** |
| 1775 |
|
* Entry for Tree bins. Subclasses LinkedNode so can be used as |
| 1776 |
< |
* either extension of regular or linked node. |
| 1776 |
> |
* extension of either regular or linked node. |
| 1777 |
|
*/ |
| 1778 |
|
static final class TreeNode<K,V> extends LinkedNode<K,V> { |
| 1779 |
|
TreeNode<K,V> parent; // red-black tree links |
| 1785 |
|
super(hash, key, val, next); |
| 1786 |
|
} |
| 1787 |
|
|
| 1788 |
+ |
/** |
| 1789 |
+ |
* Returns root of tree containing this node |
| 1790 |
+ |
*/ |
| 1791 |
|
final TreeNode<K,V> root() { |
| 1792 |
|
for (TreeNode<K,V> r = this, p;;) { |
| 1793 |
|
if ((p = r.parent) == null) |
| 1805 |
|
int index = (n - 1) & root.hash; |
| 1806 |
|
TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; |
| 1807 |
|
if (root != first) { |
| 1808 |
+ |
Node<K,V> rn; |
| 1809 |
|
tab[index] = root; |
| 1810 |
|
TreeNode<K,V> rp = root.prev; |
| 1811 |
< |
Node<K,V> rn = root.next; |
| 1802 |
< |
if (rn != null) |
| 1811 |
> |
if ((rn = root.next) != null) |
| 1812 |
|
((TreeNode<K,V>)rn).prev = rp; |
| 1813 |
|
if (rp != null) |
| 1814 |
|
rp.next = rn; |
| 1817 |
|
root.next = first; |
| 1818 |
|
root.prev = null; |
| 1819 |
|
} |
| 1820 |
+ |
assert checkInvariants(root); |
| 1821 |
|
} |
| 1822 |
|
} |
| 1823 |
|
|
| 1902 |
|
} |
| 1903 |
|
} |
| 1904 |
|
moveRootToFront(tab, root); |
| 1895 |
– |
assert checkInvariants(root); |
| 1905 |
|
} |
| 1906 |
|
|
| 1907 |
|
/** |
| 1908 |
< |
* Returns a list on non-TreeNodes replacing those linked from |
| 1908 |
> |
* Returns a list of non-TreeNodes replacing those linked from |
| 1909 |
|
* this node. |
| 1910 |
|
*/ |
| 1911 |
|
final Node<K,V> untreeify(HashMap<K,V> map) { |
| 1958 |
|
x.parent = x.prev = xp; |
| 1959 |
|
if (xpn != null) |
| 1960 |
|
((TreeNode<K,V>)xpn).prev = x; |
| 1961 |
< |
TreeNode<K,V> r = balanceInsertion(root, x); |
| 1953 |
< |
moveRootToFront(tab, r); |
| 1954 |
< |
assert checkInvariants(r); |
| 1961 |
> |
moveRootToFront(tab, balanceInsertion(root, x)); |
| 1962 |
|
return null; |
| 1963 |
|
} |
| 1964 |
|
} |
| 2067 |
|
} |
| 2068 |
|
if (movable) |
| 2069 |
|
moveRootToFront(tab, r); |
| 2063 |
– |
assert checkInvariants(r); |
| 2070 |
|
} |
| 2071 |
|
|
| 2072 |
|
/** |
| 2073 |
|
* Splits nodes in a tree bin into lower and upper tree bins, |
| 2074 |
< |
* or untreeifies if now too small. |
| 2074 |
> |
* or untreeifies if now too small. Called only from resize; |
| 2075 |
> |
* see above discussion about split bits and indices. |
| 2076 |
> |
* |
| 2077 |
> |
* @param map the map |
| 2078 |
> |
* @param tab the table for recording bin heads |
| 2079 |
> |
* @param index the index of the table being split |
| 2080 |
> |
* @param bit the bit of hash to split on |
| 2081 |
|
*/ |
| 2082 |
|
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { |
| 2083 |
|
TreeNode<K,V> b = this; |
| 2131 |
|
|
| 2132 |
|
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, |
| 2133 |
|
TreeNode<K,V> p) { |
| 2134 |
< |
if (p != null) { |
| 2135 |
< |
TreeNode<K,V> r = p.right, pp, rl; |
| 2134 |
> |
TreeNode<K,V> r, pp, rl; |
| 2135 |
> |
if (p != null && (r = p.right) != null) { |
| 2136 |
|
if ((rl = p.right = r.left) != null) |
| 2137 |
|
rl.parent = p; |
| 2138 |
|
if ((pp = r.parent = p.parent) == null) |
| 2149 |
|
|
| 2150 |
|
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, |
| 2151 |
|
TreeNode<K,V> p) { |
| 2152 |
< |
if (p != null) { |
| 2153 |
< |
TreeNode<K,V> l = p.left, pp, lr; |
| 2152 |
> |
TreeNode<K,V> l, pp, lr; |
| 2153 |
> |
if (p != null && (l = p.left) != null) { |
| 2154 |
|
if ((lr = p.left = l.right) != null) |
| 2155 |
|
lr.parent = p; |
| 2156 |
|
if ((pp = l.parent = p.parent) == null) |
