| 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 |
|
|
| 1698 |
|
/* ------------------------------------------------------------ */ |
| 1699 |
|
// LinkedHashMap support |
| 1700 |
|
|
| 1696 |
– |
/** |
| 1697 |
– |
* Entry for LinkedHashMap entries. Created only from |
| 1698 |
– |
* LinkedHashMap, but must be defined here. |
| 1699 |
– |
*/ |
| 1700 |
– |
static class LinkedNode<K,V> extends Node<K,V> { |
| 1701 |
– |
LinkedNode<K,V> before, after; |
| 1702 |
– |
LinkedNode(int hash, K key, V value, Node<K,V> next) { |
| 1703 |
– |
super(hash, key, value, next); |
| 1704 |
– |
} |
| 1705 |
– |
} |
| 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; |
