< prev index next >
src/java.base/share/classes/java/util/HashMap.java
Print this page
@@ -26,10 +26,11 @@
package java.util;
import java.io.IOException;
import java.io.InvalidObjectException;
import java.io.Serializable;
+import java.lang.ref.WeakReference;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
@@ -336,30 +337,59 @@
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
+ /** Cache of 1st encountered Class implementing Comparable */
+ private static final class ClassRef extends WeakReference<Class<?>> {
+ final boolean selfComparable;
+
+ ClassRef(Class<?> cc, boolean selfComparable) {
+ super(cc);
+ this.selfComparable = selfComparable;
+ }
+ }
+
+ private transient ClassRef comparableClassRef;
+
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
- static Class<?> comparableClassFor(Object x) {
+ Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
- Class<?> c; Type[] ts, as; ParameterizedType p;
- if ((c = x.getClass()) == String.class) // bypass checks
+ Class<?> c, cc = null;
+ Type[] ts, as;
+ ParameterizedType p;
+ ClassRef ccRef;
+ if ((c = x.getClass()) == String.class) { // bypass checks
return c;
+ }
+ if ((ccRef = comparableClassRef) != null &&
+ (cc = ccRef.get()) == c) { // cached
+ return ccRef.selfComparable ? c : null;
+ }
if ((ts = c.getGenericInterfaces()) != null) {
for (Type t : ts) {
if ((t instanceof ParameterizedType) &&
((p = (ParameterizedType) t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
- as.length == 1 && as[0] == c) // type arg is c
+ as.length == 1 && as[0] == c) { // type arg is c
+ if (cc == null) {
+ // not yet cached or already cleared
+ comparableClassRef = new ClassRef(c, true);
+ }
return c;
}
}
}
+ if (cc == null) {
+ // not yet cached or already cleared
+ comparableClassRef = new ClassRef(c, false);
+ }
+ }
return null;
}
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
@@ -570,11 +600,11 @@
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
- return ((TreeNode<K,V>)first).getTreeNode(hash, key);
+ return ((TreeNode<K,V>)first).getTreeNode(this, hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
@@ -766,11 +796,11 @@
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
- hd.treeify(tab);
+ hd.treeify(this, tab);
}
}
/**
* Copies all of the mappings from the specified map to this map.
@@ -818,11 +848,11 @@
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
- node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
+ node = ((TreeNode<K,V>)p).getTreeNode(this, hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
@@ -1095,11 +1125,11 @@
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
- old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
+ old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
@@ -1169,11 +1199,11 @@
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
- old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
+ old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
@@ -1224,11 +1254,11 @@
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
- old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
+ old = (t = (TreeNode<K,V>)first).getTreeNode(this, hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
@@ -1837,11 +1867,11 @@
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
- final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
+ final TreeNode<K,V> find(HashMap<K,V> map, int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
@@ -1853,26 +1883,26 @@
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
- (kc = comparableClassFor(k)) != null) &&
+ (kc = map.comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
- else if ((q = pr.find(h, k, kc)) != null)
+ else if ((q = pr.find(map, h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
/**
* Calls find for root node.
*/
- final TreeNode<K,V> getTreeNode(int h, Object k) {
- return ((parent != null) ? root() : this).find(h, k, null);
+ final TreeNode<K,V> getTreeNode(HashMap<K,V> map, int h, Object k) {
+ return ((parent != null) ? root() : this).find(map, h, k, null);
}
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
@@ -1892,11 +1922,11 @@
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
- final void treeify(Node<K,V>[] tab) {
+ final void treeify(HashMap<K,V> map, Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
@@ -1914,11 +1944,11 @@
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
- (kc = comparableClassFor(k)) == null) ||
+ (kc = map.comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
@@ -1968,19 +1998,19 @@
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
- (kc = comparableClassFor(k)) == null) ||
+ (kc = map.comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
- (q = ch.find(h, k, kc)) != null) ||
+ (q = ch.find(map, h, k, kc)) != null) ||
((ch = p.right) != null &&
- (q = ch.find(h, k, kc)) != null))
+ (q = ch.find(map, h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
@@ -2148,20 +2178,20 @@
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
- loHead.treeify(tab);
+ loHead.treeify(map, tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
- hiHead.treeify(tab);
+ hiHead.treeify(map, tab);
}
}
}
/* ------------------------------------------------------------ */
< prev index next >