| 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 methd), allowing |
| 205 |
> |
* argument (as normally supplied from a public method), 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. |
| 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 |
| 213 |
|
* Node.next) to better preserve locality, and to slightly |
| 214 |
|
* simplify handling of splits and traversals that invoke |
| 215 |
< |
* iterator.remove. |
| 215 |
> |
* iterator.remove. When using comparators on insertion, to keep a |
| 216 |
> |
* total ordering (or as close as is required here) across |
| 217 |
> |
* rebalancings, we compare classes and identityHashCodes as |
| 218 |
> |
* tie-breakers. |
| 219 |
|
* |
| 220 |
|
* The use and transitions among plain vs tree modes is |
| 221 |
|
* complicated by the existence of subclass LinkedHashMap. See |
| 274 |
|
|
| 275 |
|
/** |
| 276 |
|
* Basic hash bin node, used for most entries. (See below for |
| 277 |
< |
* LinkedNode and TreeNode subclasses.) |
| 277 |
> |
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.) |
| 278 |
|
*/ |
| 279 |
|
static class Node<K,V> implements Map.Entry<K,V> { |
| 280 |
|
final int hash; |
| 390 |
|
/** |
| 391 |
|
* The table, initialized on first use, and resized as |
| 392 |
|
* necessary. When allocated, length is always a power of two. |
| 393 |
< |
* (We also tolerate length zero for some read-only operations.) |
| 393 |
> |
* (We also tolerate length zero in some operations to allow |
| 394 |
> |
* bootstrapping mechanics that are currently not needed.) |
| 395 |
|
*/ |
| 396 |
|
transient Node<K,V>[] table; |
| 397 |
|
|
| 1701 |
|
/* ------------------------------------------------------------ */ |
| 1702 |
|
// LinkedHashMap support |
| 1703 |
|
|
| 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 |
– |
} |
| 1704 |
|
|
| 1705 |
|
/* |
| 1706 |
|
* The following package-protected methods are designed to be |
| 1765 |
|
// Tree bins |
| 1766 |
|
|
| 1767 |
|
/** |
| 1768 |
< |
* Entry for Tree bins. Subclasses LinkedNode so can be used as |
| 1769 |
< |
* extension of either regular or linked node. |
| 1768 |
> |
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn |
| 1769 |
> |
* extends Node) so can be used as extension of either regular or |
| 1770 |
> |
* linked node. |
| 1771 |
|
*/ |
| 1772 |
< |
static final class TreeNode<K,V> extends LinkedNode<K,V> { |
| 1772 |
> |
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { |
| 1773 |
|
TreeNode<K,V> parent; // red-black tree links |
| 1774 |
|
TreeNode<K,V> left; |
| 1775 |
|
TreeNode<K,V> right; |
| 1780 |
|
} |
| 1781 |
|
|
| 1782 |
|
/** |
| 1783 |
< |
* Returns root of tree containing this node |
| 1783 |
> |
* Returns root of tree containing this node. |
| 1784 |
|
*/ |
| 1785 |
|
final TreeNode<K,V> root() { |
| 1786 |
|
for (TreeNode<K,V> r = this, p;;) { |
| 1791 |
|
} |
| 1792 |
|
|
| 1793 |
|
/** |
| 1794 |
< |
* Ensures that the given root is the first node of its bin |
| 1794 |
> |
* Ensures that the given root is the first node of its bin. |
| 1795 |
|
*/ |
| 1796 |
|
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { |
| 1797 |
|
int n; |
| 1831 |
|
p = pr; |
| 1832 |
|
else if ((pk = p.key) == k || (k != null && k.equals(pk))) |
| 1833 |
|
return p; |
| 1835 |
– |
else if (pl == null && pr == null) |
| 1836 |
– |
break; |
| 1837 |
– |
else if ((kc != null || (kc = comparableClassFor(k)) != null) && |
| 1838 |
– |
(dir = compareComparables(kc, k, pk)) != 0) |
| 1839 |
– |
p = (dir < 0) ? pl : pr; |
| 1834 |
|
else if (pl == null) |
| 1835 |
|
p = pr; |
| 1836 |
< |
else if (pr == null || (q = pr.find(h, k, kc)) == null) |
| 1836 |
> |
else if (pr == null) |
| 1837 |
|
p = pl; |
| 1838 |
< |
else |
| 1838 |
> |
else if ((kc != null || |
| 1839 |
> |
(kc = comparableClassFor(k)) != null) && |
| 1840 |
> |
(dir = compareComparables(kc, k, pk)) != 0) |
| 1841 |
> |
p = (dir < 0) ? pl : pr; |
| 1842 |
> |
else if ((q = pr.find(h, k, kc)) != null) |
| 1843 |
|
return q; |
| 1844 |
+ |
else |
| 1845 |
+ |
p = pl; |
| 1846 |
|
} while (p != null); |
| 1847 |
|
return null; |
| 1848 |
|
} |
| 1855 |
|
} |
| 1856 |
|
|
| 1857 |
|
/** |
| 1858 |
+ |
* Tie-breaking utility for ordering insertions when equal |
| 1859 |
+ |
* hashCodes and non-comparable. We don't require a total |
| 1860 |
+ |
* order, just a consistent insertion rule to maintain |
| 1861 |
+ |
* equivalence across rebalancings. Tie-breaking further than |
| 1862 |
+ |
* necessary simplifies testing a bit. |
| 1863 |
+ |
*/ |
| 1864 |
+ |
static int tieBreakOrder(Object a, Object b) { |
| 1865 |
+ |
int d; |
| 1866 |
+ |
if (a == null || b == null || |
| 1867 |
+ |
(d = a.getClass().getName(). |
| 1868 |
+ |
compareTo(b.getClass().getName())) == 0) |
| 1869 |
+ |
d = (System.identityHashCode(a) <= System.identityHashCode(b) ? |
| 1870 |
+ |
-1 : 1); |
| 1871 |
+ |
return d; |
| 1872 |
+ |
} |
| 1873 |
+ |
|
| 1874 |
+ |
/** |
| 1875 |
|
* Forms tree of the nodes linked from this node. |
| 1876 |
|
* @return root of tree |
| 1877 |
|
*/ |
| 1891 |
|
Class<?> kc = null; |
| 1892 |
|
for (TreeNode<K,V> p = root;;) { |
| 1893 |
|
int dir, ph; |
| 1894 |
+ |
K pk = p.key; |
| 1895 |
|
if ((ph = p.hash) > h) |
| 1896 |
|
dir = -1; |
| 1897 |
|
else if (ph < h) |
| 1898 |
|
dir = 1; |
| 1899 |
< |
else if ((kc != null || |
| 1900 |
< |
(kc = comparableClassFor(k)) != null)) |
| 1901 |
< |
dir = compareComparables(kc, k, p.key); |
| 1902 |
< |
else |
| 1903 |
< |
dir = 0; |
| 1899 |
> |
else if ((kc == null && |
| 1900 |
> |
(kc = comparableClassFor(k)) == null) || |
| 1901 |
> |
(dir = compareComparables(kc, k, pk)) == 0) |
| 1902 |
> |
dir = tieBreakOrder(k, pk); |
| 1903 |
> |
|
| 1904 |
|
TreeNode<K,V> xp = p; |
| 1905 |
|
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
| 1906 |
|
x.parent = xp; |
| 1940 |
|
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, |
| 1941 |
|
int h, K k, V v) { |
| 1942 |
|
Class<?> kc = null; |
| 1943 |
+ |
boolean searched = false; |
| 1944 |
|
TreeNode<K,V> root = (parent != null) ? root() : this; |
| 1945 |
|
for (TreeNode<K,V> p = root;;) { |
| 1946 |
< |
int ph, dir; K pk; TreeNode<K,V> pr, q; |
| 1946 |
> |
int dir, ph; K pk; |
| 1947 |
|
if ((ph = p.hash) > h) |
| 1948 |
|
dir = -1; |
| 1949 |
|
else if (ph < h) |
| 1950 |
|
dir = 1; |
| 1951 |
< |
else if ((pk = p.key) == k || (k != null && k.equals(pk))) |
| 1951 |
> |
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) |
| 1952 |
|
return p; |
| 1953 |
< |
else if ((kc == null && (kc = comparableClassFor(k)) == null) || |
| 1953 |
> |
else if ((kc == null && |
| 1954 |
> |
(kc = comparableClassFor(k)) == null) || |
| 1955 |
|
(dir = compareComparables(kc, k, pk)) == 0) { |
| 1956 |
< |
if (p.left == null) |
| 1957 |
< |
dir = 1; |
| 1958 |
< |
else if ((pr = p.right) == null || |
| 1959 |
< |
(q = pr.find(h, k, kc)) == null) |
| 1960 |
< |
dir = -1; |
| 1961 |
< |
else |
| 1962 |
< |
return q; |
| 1956 |
> |
if (!searched) { |
| 1957 |
> |
TreeNode<K,V> q, ch; |
| 1958 |
> |
searched = true; |
| 1959 |
> |
if (((ch = p.left) != null && |
| 1960 |
> |
(q = ch.find(h, k, kc)) != null) || |
| 1961 |
> |
((ch = p.right) != null && |
| 1962 |
> |
(q = ch.find(h, k, kc)) != null)) |
| 1963 |
> |
return q; |
| 1964 |
> |
} |
| 1965 |
> |
dir = tieBreakOrder(k, pk); |
| 1966 |
|
} |
| 1967 |
+ |
|
| 1968 |
|
TreeNode<K,V> xp = p; |
| 1969 |
< |
if ((p = (dir < 0) ? p.left : p.right) == null) { |
| 1969 |
> |
if ((p = (dir <= 0) ? p.left : p.right) == null) { |
| 1970 |
|
Node<K,V> xpn = xp.next; |
| 1971 |
|
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); |
| 1972 |
< |
if (dir < 0) |
| 1972 |
> |
if (dir <= 0) |
| 1973 |
|
xp.left = x; |
| 1974 |
|
else |
| 1975 |
|
xp.right = x; |
| 2241 |
|
|
| 2242 |
|
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, |
| 2243 |
|
TreeNode<K,V> x) { |
| 2244 |
< |
for (TreeNode<K,V> xp, xpl, xpr;;) { |
| 2244 |
> |
for (TreeNode<K,V> xp, xpl, xpr;;) { |
| 2245 |
|
if (x == null || x == root) |
| 2246 |
|
return root; |
| 2247 |
|
else if ((xp = x.parent) == null) { |
