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 |
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. |
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 |
271 |
|
|
272 |
|
/** |
273 |
|
* Basic hash bin node, used for most entries. (See below for |
274 |
< |
* LinkedNode and TreeNode subclasses.) |
274 |
> |
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.) |
275 |
|
*/ |
276 |
|
static class Node<K,V> implements Map.Entry<K,V> { |
277 |
|
final int hash; |
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 |
|
|
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 |
|
/** |
1698 |
|
/* ------------------------------------------------------------ */ |
1699 |
|
// LinkedHashMap support |
1700 |
|
|
1695 |
– |
/** |
1696 |
– |
* Entry for LinkedHashMap entries. Created only from |
1697 |
– |
* LinkedHashMap, but must be defined here. |
1698 |
– |
*/ |
1699 |
– |
static class LinkedNode<K,V> extends Node<K,V> { |
1700 |
– |
LinkedNode<K,V> before, after; |
1701 |
– |
LinkedNode(int hash, K key, V value, Node<K,V> next) { |
1702 |
– |
super(hash, key, value, next); |
1703 |
– |
} |
1704 |
– |
} |
1701 |
|
|
1702 |
|
/* |
1703 |
|
* The following package-protected methods are designed to be |
1762 |
|
// Tree bins |
1763 |
|
|
1764 |
|
/** |
1765 |
< |
* Entry for Tree bins. Subclasses LinkedNode so can be used as |
1766 |
< |
* extension of either regular or linked node. |
1765 |
> |
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn |
1766 |
> |
* extends Node) so can be used as extension of either regular or |
1767 |
> |
* linked node. |
1768 |
|
*/ |
1769 |
< |
static final class TreeNode<K,V> extends LinkedNode<K,V> { |
1769 |
> |
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { |
1770 |
|
TreeNode<K,V> parent; // red-black tree links |
1771 |
|
TreeNode<K,V> left; |
1772 |
|
TreeNode<K,V> right; |
1777 |
|
} |
1778 |
|
|
1779 |
|
/** |
1780 |
< |
* Returns root of tree containing this node |
1780 |
> |
* Returns root of tree containing this node. |
1781 |
|
*/ |
1782 |
|
final TreeNode<K,V> root() { |
1783 |
|
for (TreeNode<K,V> r = this, p;;) { |
1788 |
|
} |
1789 |
|
|
1790 |
|
/** |
1791 |
< |
* Ensures that the given root is the first node of its bin |
1791 |
> |
* Ensures that the given root is the first node of its bin. |
1792 |
|
*/ |
1793 |
|
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { |
1794 |
|
int n; |
2044 |
|
p.left = p.right = p.parent = null; |
2045 |
|
} |
2046 |
|
|
2047 |
< |
TreeNode<K,V> r = (p.red)? root : balanceDeletion(root, replacement); |
2047 |
> |
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement); |
2048 |
|
|
2049 |
|
if (replacement == p) { // detach |
2050 |
|
TreeNode<K,V> pp = p.parent; |