< prev index next >
src/java.base/share/classes/java/util/HashMap.java
Print this page
*** 26,35 ****
--- 26,36 ----
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,365 ****
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
! static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
! Class<?> c; Type[] ts, as; ParameterizedType p;
! if ((c = x.getClass()) == String.class) // bypass checks
return c;
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
return c;
}
}
}
return null;
}
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
--- 337,395 ----
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.
*/
! Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
! 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
! 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,580 ****
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);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
--- 600,610 ----
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(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,776 ****
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
! hd.treeify(tab);
}
}
/**
* Copies all of the mappings from the specified map to this map.
--- 796,806 ----
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
! hd.treeify(this, tab);
}
}
/**
* Copies all of the mappings from the specified map to this map.
*** 818,828 ****
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);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
--- 848,858 ----
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(this, hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
*** 1095,1105 ****
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);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
--- 1125,1135 ----
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(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,1179 ****
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);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
--- 1199,1209 ----
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(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,1234 ****
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);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
--- 1254,1264 ----
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(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,1847 ****
/**
* 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) {
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)
--- 1867,1877 ----
/**
* 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(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,1878 ****
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
! (kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
! else if ((q = pr.find(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);
}
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
--- 1883,1908 ----
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
! (kc = map.comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
! 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(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,1902 ****
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
! final void treeify(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) {
--- 1922,1932 ----
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
! 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,1924 ****
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
! (kc = 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) {
--- 1944,1954 ----
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == 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,1986 ****
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) ||
(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) ||
((ch = p.right) != null &&
! (q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
--- 1998,2016 ----
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == 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(map, h, k, kc)) != null) ||
((ch = p.right) != null &&
! (q = ch.find(map, h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
*** 2148,2167 ****
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
! loHead.treeify(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);
}
}
}
/* ------------------------------------------------------------ */
--- 2178,2197 ----
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
! 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(map, tab);
}
}
}
/* ------------------------------------------------------------ */
< prev index next >