Explication détaillée de HashMap dans les collections Java
- 黄舟original
- 2017-03-13 17:42:371489parcourir
HashMap est une table de hachage et le contenu stocké est un mappage clé-valeur. HashMap hérite de AbstractMap et implémente les interfaces Map, Cloneable et Serialisable.
(1) HashMap n'est pas thread-safe et la valeur-clé peut être nulle et n'est pas ordonnée.
(2) La taille initiale de HashMap est de 16, la taille maximale est de 2 à la puissance 30 et le facteur de chargement par défaut est de 0,75.
(3) La capacité initiale est simplement la capacité de la table de hachage lors de sa création, et le facteur de charge est une mesure du degré de remplissage de la table de hachage avant que sa capacité ne soit automatiquement augmentée. Lorsque le nombre d'entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage doit être rehachée (reconstruction de la structure de données interne)
La relation entre HashMap et Map est la suivante :
(1) HashMap hérite de la classe AbstractMap et implémente l'interface Map.
(2) HashMap implémente une table de hachage via la méthode zipper. Plusieurs variables membres importantes sont : table, taille, seuil, loadFactor, modCount.
table est un type de tableau Entry[]. Entry est en fait une liste chaînée unidirectionnelle. Les valeurs-clés de HashMap sont stockées dans ce tableau.
size est la taille de HashMap, qui est le nombre de paires clé-valeur enregistrées par HashMap.
le seuil est le seuil de HashMap, utilisé pour déterminer si la capacité de HashMap doit être ajustée. La valeur du seuil est égale à la capacité multipliée par le facteur de chargement lorsque les données stockées dans le HashMap atteignent le. seuil, la capacité du HashMap doit être doublée. Le
facteur de charge loadFactor
modCount est utilisé pour implémenter le mécanisme de défaillance rapide.
Méthode de traversée HashMap :
(1) Parcourez les paires clé-valeur de HashMap : La première étape consiste à obtenir l'ensemble d'entrées via le jeu d'entrées ( ), La deuxième étape consiste à parcourir la collection d'entrées via l'Iterator pour obtenir les données
Integer Iterator =map.entrySet().iterator()(iterator.hasNext())
{
Map.Entry entry=(Map.Entry)iterator.next()key=(String)enrty.getKey()value=(Integer)entry.getValue()}
(2) Parcourir les clés du HashMap et obtenir la valeur via la clé
=Integer =Inerator =map.keySet().iterator()(iterator.hasNext())
{
key=(String)iterator.next()value=(Integer)map.get(key)}
(3) Parcourez les valeurs de HashMap : la première étape consiste à obtenir l'ensemble de valeurs en fonction de la valeur, et à parcourir de manière itérative l'ensemble de valeurs
=Collection =map.values()Iterator = .iterator()(iterator.hasNext())
{
value=(Integer)iterator.next()}
Fonctions couramment utilisées :
() Object () (Object key) (Object value) Set8817e8d4bd2291481cc1067ca69329e6> () (Object key) () Seta8093152e673feb7aba1828c43532094 () (keyvalue) (Map024902c398a6aa179f04c367da6aee33 map) (Object key) () Collectiona8093152e673feb7aba1828c43532094 ()
Exemple de code HashMap :
public class Hello {
public void testHashMapAPIs()
{
Random r = new Random();
HashMap601754196720ae8e56f6948b6d2ab654 map = new HashMap();
map.put("one", r.nextInt(10));
map.put("two", r.nextInt(10));
map.put("three", r.nextInt(10));
System.out.println("map:"+map );
Iterator iter = map.entrySet().iterator();
while(iter.hasNext())
{
Map.Entry entry = (Map.Entry)iter.next();
System.out.println("key : "+ entry.getKey() +",value:"+entry.getValue());
}
System.out.println("size:"+map.size());
System.out.println("contains key two : "+map.containsKey("two"));
System.out.println("contains key five : "+map.containsKey("five"));
System.out.println("contains value 0 : "+map.containsValue(new Integer(0)));
map.remove("three");
System.out.println("map:"+map );
map.clear();
System.out.println((map.isEmpty()?"map is empty":"map is not empty") );
}
public static void main(String[] args) {
Hello hello=new Hello();
hello.testHashMapAPIs();
}
}
Résultat d'exécution :
map:{one=3, two=9, three=9}
key : one,value:3
key : two,value:9
key : three,value:9
size:3
contains key two : true
contains key five : false
contains value 0 : false
map:{one=3, two=9}
map is emptyAnalyse du code source HashMap dans java8 :
public class HashMapb77a8d9c3c319e50d4b02a976b347910 extends AbstractMapb77a8d9c3c319e50d4b02a976b347910
implements Mapb77a8d9c3c319e50d4b02a976b347910, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始大小为2的4次方
static final int MAXIMUM_CAPACITY = 1 << 30;//最大为2的30次方
static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子是0.75
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
//节点类
static class Nodeb77a8d9c3c319e50d4b02a976b347910 implements Map.Entryb77a8d9c3c319e50d4b02a976b347910 {
final int hash;
final K key;
V value;
Node81079595401ce1162abe0d5a660013d8 next;
Node(int hash, K key, V value, Node81079595401ce1162abe0d5a660013d8 next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return key + "=" + value;
}
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entryd43304c59d62d300b67a59666cfd3cea e = (Map.Entryd43304c59d62d300b67a59666cfd3cea) o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
//计算Hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//返回类
static Class6b3d0130bba23ae47fe2b8e8cddf0195 comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class6b3d0130bba23ae47fe2b8e8cddf0195 c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) 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;
}
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class6b3d0130bba23ae47fe2b8e8cddf0195 kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n 94c7772769a380812d3bd4a3f478d6e2= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
transient Nodeb77a8d9c3c319e50d4b02a976b347910[] table;//数据表
transient Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet;//实体集合
transient int size;//大小
transient int modCount;//用来实现fail-fast
int threshold;//值为capacity * load factor
final float loadFactor;//hashtable的加载因子
//构造函数，初始化容量大小和加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity c925b63a2537a1bf5bc840be8e193103 MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor a085f4808830c8cb599c6b9ec9842867 m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map11df7d36ed146da2cbbceeacbc3a1d74 m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft 2c7e39097ac59e951bf7d1d2ff347367 threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry11df7d36ed146da2cbbceeacbc3a1d74 e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
//返回大小
public int size() {
return size;
}
//判断是否为空
public boolean isEmpty() {
return size == 0;
}
//通过key获得值
public V get(Object key) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//通过hash和key获得节点
final Nodeb77a8d9c3c319e50d4b02a976b347910 getNode(int hash, Object key) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
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 ((TreeNodeb77a8d9c3c319e50d4b02a976b347910)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);
}
}
return null;
}
//是否含有某个key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
//如果之前存在key的value值，则替换掉
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Nodeb77a8d9c3c319e50d4b02a976b347910 e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNodeb77a8d9c3c319e50d4b02a976b347910)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
//改变大小
final Nodeb77a8d9c3c319e50d4b02a976b347910[] resize() {
Nodeb77a8d9c3c319e50d4b02a976b347910[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap 00a870fc5c36d70c274f6e7d254426e1= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr a559973318aed8bfd59cb1ded4361ff5 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Nodeb77a8d9c3c319e50d4b02a976b347910[] newTab = (Nodeb77a8d9c3c319e50d4b02a976b347910[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNodeb77a8d9c3c319e50d4b02a976b347910)e).split(this, newTab, j, oldCap);
else { // preserve order
Nodeb77a8d9c3c319e50d4b02a976b347910 loHead = null, loTail = null;
Nodeb77a8d9c3c319e50d4b02a976b347910 hiHead = null, hiTail = null;
Nodeb77a8d9c3c319e50d4b02a976b347910 next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
final void treeifyBin(Nodeb77a8d9c3c319e50d4b02a976b347910[] tab, int hash) {
int n, index; Nodeb77a8d9c3c319e50d4b02a976b347910 e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 hd = null, tl = null;
do {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
public void putAll(Map11df7d36ed146da2cbbceeacbc3a1d74 m) {
putMapEntries(m, true);
}
public V remove(Object key) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Nodeb77a8d9c3c319e50d4b02a976b347910 removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Nodeb77a8d9c3c319e50d4b02a976b347910 node = null, e; K k; V v;
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 = ((TreeNodeb77a8d9c3c319e50d4b02a976b347910)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNodeb77a8d9c3c319e50d4b02a976b347910)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
public void clear() {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
public boolean containsValue(Object value) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
public Set245c3adc26563b673f7297c0b3777639 keySet() {
Set245c3adc26563b673f7297c0b3777639 ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet245c3adc26563b673f7297c0b3777639 {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator245c3adc26563b673f7297c0b3777639 iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator245c3adc26563b673f7297c0b3777639 spliterator() {
return new KeySpliteratora8093152e673feb7aba1828c43532094(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
public Collectiond94943c0b4933ad8cac500132f64757f values() {
Collectiond94943c0b4933ad8cac500132f64757f vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollectiond94943c0b4933ad8cac500132f64757f {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iteratord94943c0b4933ad8cac500132f64757f iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliteratord94943c0b4933ad8cac500132f64757f spliterator() {
return new ValueSpliteratora8093152e673feb7aba1828c43532094(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer4b7c428692c243aad23ae950d093df01 action) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
public Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> entrySet() {
Set<Map.Entryb77a8d9c3c319e50d4b02a976b347910> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entryc3f2d894ed311a524f031af7191b9ddc e = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object key = e.getKey();
Nodeb77a8d9c3c319e50d4b02a976b347910 candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entryc3f2d894ed311a524f031af7191b9ddc e = (Map.Entryc3f2d894ed311a524f031af7191b9ddc) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> spliterator() {
return new EntrySpliteratora8093152e673feb7aba1828c43532094(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entryb77a8d9c3c319e50d4b02a976b347910> action) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
// Overrides of JDK8 Map extension methods
@Override
public V getOrDefault(Object key, V defaultValue) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
@Override
public boolean replace(K key, V oldValue, V newValue) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e; V v;
if ((e = getNode(hash(key), key)) != null &&
((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
e.value = newValue;
afterNodeAccess(e);
return true;
}
return false;
}
@Override
public V replace(K key, V value) {
Nodeb77a8d9c3c319e50d4b02a976b347910 e;
if ((e = getNode(hash(key), key)) != null) {
V oldValue = e.value;
e.value = value;
afterNodeAccess(e);
return oldValue;
}
return null;
}
@Override
public V computeIfAbsent(K key,
Functionb68c911977e56dedeb85de82f5d80518 mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 first; int n, i;
int binCount = 0;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 t = null;
Nodeb77a8d9c3c319e50d4b02a976b347910 old = null;
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 = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)first).getTreeNode(hash, key);
else {
Nodeb77a8d9c3c319e50d4b02a976b347910 e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
V oldValue;
if (old != null && (oldValue = old.value) != null) {
afterNodeAccess(old);
return oldValue;
}
}
V v = mappingFunction.apply(key);
if (v == null) {
return null;
} else if (old != null) {
old.value = v;
afterNodeAccess(old);
return v;
}
else if (t != null)
t.putTreeVal(this, tab, hash, key, v);
else {
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
return v;
}
public V computeIfPresent(K key,
BiFunction0a1b16d994d218d93e3e331534b14776 remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Nodeb77a8d9c3c319e50d4b02a976b347910 e; V oldValue;
int hash = hash(key);
if ((e = getNode(hash, key)) != null &&
(oldValue = e.value) != null) {
V v = remappingFunction.apply(key, oldValue);
if (v != null) {
e.value = v;
afterNodeAccess(e);
return v;
}
else
removeNode(hash, key, null, false, true);
}
return null;
}
@Override
public V compute(K key,
BiFunction0a1b16d994d218d93e3e331534b14776 remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 first; int n, i;
int binCount = 0;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 t = null;
Nodeb77a8d9c3c319e50d4b02a976b347910 old = null;
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 = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)first).getTreeNode(hash, key);
else {
Nodeb77a8d9c3c319e50d4b02a976b347910 e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
V oldValue = (old == null) ? null : old.value;
V v = remappingFunction.apply(key, oldValue);
if (old != null) {
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
}
else if (v != null) {
if (t != null)
t.putTreeVal(this, tab, hash, key, v);
else {
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return v;
}
@Override
public V merge(K key, V value,
BiFunctiona9451a6954651d01dcb928f097d6d988 remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab; Nodeb77a8d9c3c319e50d4b02a976b347910 first; int n, i;
int binCount = 0;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 t = null;
Nodeb77a8d9c3c319e50d4b02a976b347910 old = null;
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 = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)first).getTreeNode(hash, key);
else {
Nodeb77a8d9c3c319e50d4b02a976b347910 e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
if (old != null) {
V v;
if (old.value != null)
v = remappingFunction.apply(old.value, value);
else
v = value;
if (v != null) {
old.value = v;
afterNodeAccess(old);
}
else
removeNode(hash, key, null, false, true);
return v;
}
if (value != null) {
if (t != null)
t.putTreeVal(this, tab, hash, key, value);
else {
tab[i] = newNode(hash, key, value, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
++modCount;
++size;
afterNodeInsertion(true);
}
return value;
}
@Override
public void forEach(BiConsumer8d7aa65c8046027ea338ee53f830d46e action) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
@Override
public void replaceAll(BiFunction0a1b16d994d218d93e3e331534b14776 function) {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (function == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next) {
e.value = function.apply(e.key, e.value);
}
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
@SuppressWarnings("unchecked")
@Override
public Object clone() {
HashMapb77a8d9c3c319e50d4b02a976b347910 result;
try {
result = (HashMapb77a8d9c3c319e50d4b02a976b347910)super.clone();
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
result.reinitialize();
result.putMapEntries(this, false);
return result;
}
final float loadFactor() { return loadFactor; }
final int capacity() {
return (table != null) ? table.length :
(threshold > 0) ? threshold :
DEFAULT_INITIAL_CAPACITY;
}
private void writeObject(java.io.ObjectOutputStream s)
throws IOException {
int buckets = capacity();
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
s.writeInt(buckets);
s.writeInt(size);
internalWriteEntries(s);
}
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException {
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
reinitialize();
if (loadFactor 1278fa994f6e5e24aa5cbf3831adbac7 0) { // (if zero, use defaults)
// Size the table using given load factor only if within
// range of 0.25...4.0
float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
float fc = (float)mappings / lf + 1.0f;
int cap = ((fc e3a6720a76f135d81b47e76f4e3db69a= MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
(int)ft : Integer.MAX_VALUE);
@SuppressWarnings({"rawtypes","unchecked"})
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = (Nodeb77a8d9c3c319e50d4b02a976b347910[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {
@SuppressWarnings("unchecked")
K key = (K) s.readObject();
@SuppressWarnings("unchecked")
V value = (V) s.readObject();
putVal(hash(key), key, value, false, false);
}
}
}
abstract class HashIterator {
Nodeb77a8d9c3c319e50d4b02a976b347910 next; // next entry to return
Nodeb77a8d9c3c319e50d4b02a976b347910 current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Nodeb77a8d9c3c319e50d4b02a976b347910[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Nodeb77a8d9c3c319e50d4b02a976b347910 nextNode() {
Nodeb77a8d9c3c319e50d4b02a976b347910[] t;
Nodeb77a8d9c3c319e50d4b02a976b347910 e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Nodeb77a8d9c3c319e50d4b02a976b347910 p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
final class KeyIterator extends HashIterator
implements Iterator245c3adc26563b673f7297c0b3777639 {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iteratord94943c0b4933ad8cac500132f64757f {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
public final Map.Entryb77a8d9c3c319e50d4b02a976b347910 next() { return nextNode(); }
}
static class HashMapSpliteratorb77a8d9c3c319e50d4b02a976b347910 {
final HashMapb77a8d9c3c319e50d4b02a976b347910 map;
Nodeb77a8d9c3c319e50d4b02a976b347910 current; // current node
int index; // current index, modified on advance/split
int fence; // one past last index
int est; // size estimate
int expectedModCount; // for comodification checks
HashMapSpliterator(HashMapb77a8d9c3c319e50d4b02a976b347910 m, int origin,
int fence, int est,
int expectedModCount) {
this.map = m;
this.index = origin;
this.fence = fence;
this.est = est;
this.expectedModCount = expectedModCount;
}
final int getFence() { // initialize fence and size on first use
int hi;
if ((hi = fence) < 0) {
HashMapb77a8d9c3c319e50d4b02a976b347910 m = map;
est = m.size;
expectedModCount = m.modCount;
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = m.table;
hi = fence = (tab == null) ? 0 : tab.length;
}
return hi;
}
public final long estimateSize() {
getFence(); // force init
return (long) est;
}
}
static final class KeySpliteratorb77a8d9c3c319e50d4b02a976b347910
extends HashMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliterator245c3adc26563b673f7297c0b3777639 {
KeySpliterator(HashMapb77a8d9c3c319e50d4b02a976b347910 m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public KeySpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new KeySpliteratora8093152e673feb7aba1828c43532094(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMapb77a8d9c3c319e50d4b02a976b347910 m = map;
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = m.table;
if ((hi = fence) 65c2b8f09516a88ae0fd0f139eac95a1= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Nodeb77a8d9c3c319e50d4b02a976b347910 p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.key);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer99be4058f294b5c4a6207ddd3216ce19 action) {
int hi;
if (action == null)
throw new NullPointerException();
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
K k = current.key;
current = current.next;
action.accept(k);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
}
static final class ValueSpliteratorb77a8d9c3c319e50d4b02a976b347910
extends HashMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliteratord94943c0b4933ad8cac500132f64757f {
ValueSpliterator(HashMapb77a8d9c3c319e50d4b02a976b347910 m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public ValueSpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new ValueSpliteratora8093152e673feb7aba1828c43532094(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer4b7c428692c243aad23ae950d093df01 action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMapb77a8d9c3c319e50d4b02a976b347910 m = map;
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = m.table;
if ((hi = fence) 65c2b8f09516a88ae0fd0f139eac95a1= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Nodeb77a8d9c3c319e50d4b02a976b347910 p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.value);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer4b7c428692c243aad23ae950d093df01 action) {
int hi;
if (action == null)
throw new NullPointerException();
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
V v = current.value;
current = current.next;
action.accept(v);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
}
}
static final class EntrySpliteratorb77a8d9c3c319e50d4b02a976b347910
extends HashMapSpliteratorb77a8d9c3c319e50d4b02a976b347910
implements Spliterator<Map.Entryb77a8d9c3c319e50d4b02a976b347910> {
EntrySpliterator(HashMapb77a8d9c3c319e50d4b02a976b347910 m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public EntrySpliteratorb77a8d9c3c319e50d4b02a976b347910 trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new EntrySpliteratora8093152e673feb7aba1828c43532094(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer<? super Map.Entryb77a8d9c3c319e50d4b02a976b347910> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMapb77a8d9c3c319e50d4b02a976b347910 m = map;
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = m.table;
if ((hi = fence) 65c2b8f09516a88ae0fd0f139eac95a1= hi &&
(i = index) >= 0 && (i < (index = hi) || current != null)) {
Nodeb77a8d9c3c319e50d4b02a976b347910 p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p);
p = p.next;
}
} while (p != null || i < hi);
if (m.modCount != mc)
throw new ConcurrentModificationException();
}
}
public boolean tryAdvance(Consumer<? super Map.Entryb77a8d9c3c319e50d4b02a976b347910> action) {
int hi;
if (action == null)
throw new NullPointerException();
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index < hi) {
if (current == null)
current = tab[index++];
else {
Nodeb77a8d9c3c319e50d4b02a976b347910 e = current;
current = current.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
Spliterator.DISTINCT;
}
}
Nodeb77a8d9c3c319e50d4b02a976b347910 newNode(int hash, K key, V value, Nodeb77a8d9c3c319e50d4b02a976b347910 next) {
return new Nodea8093152e673feb7aba1828c43532094(hash, key, value, next);
}
// For conversion from TreeNodes to plain nodes
Nodeb77a8d9c3c319e50d4b02a976b347910 replacementNode(Nodeb77a8d9c3c319e50d4b02a976b347910 p, Nodeb77a8d9c3c319e50d4b02a976b347910 next) {
return new Nodea8093152e673feb7aba1828c43532094(p.hash, p.key, p.value, next);
}
// Create a tree bin node
TreeNodeb77a8d9c3c319e50d4b02a976b347910 newTreeNode(int hash, K key, V value, Nodeb77a8d9c3c319e50d4b02a976b347910 next) {
return new TreeNodea8093152e673feb7aba1828c43532094(hash, key, value, next);
}
// For treeifyBin
TreeNodeb77a8d9c3c319e50d4b02a976b347910 replacementTreeNode(Nodeb77a8d9c3c319e50d4b02a976b347910 p, Nodeb77a8d9c3c319e50d4b02a976b347910 next) {
return new TreeNodea8093152e673feb7aba1828c43532094(p.hash, p.key, p.value, next);
}
void reinitialize() {
table = null;
entrySet = null;
keySet = null;
values = null;
modCount = 0;
threshold = 0;
size = 0;
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Nodeb77a8d9c3c319e50d4b02a976b347910 p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Nodeb77a8d9c3c319e50d4b02a976b347910 p) { }
// Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Nodeb77a8d9c3c319e50d4b02a976b347910[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i < tab.length; ++i) {
for (Nodeb77a8d9c3c319e50d4b02a976b347910 e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
static final class TreeNodeb77a8d9c3c319e50d4b02a976b347910 extends LinkedHashMap.Entryb77a8d9c3c319e50d4b02a976b347910 {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 parent; // red-black tree links
TreeNodeb77a8d9c3c319e50d4b02a976b347910 left;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 right;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Nodeb77a8d9c3c319e50d4b02a976b347910 next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNodeb77a8d9c3c319e50d4b02a976b347910 root() {
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* Ensures that the given root is the first node of its bin.
*/
static b77a8d9c3c319e50d4b02a976b347910 void moveRootToFront(Nodeb77a8d9c3c319e50d4b02a976b347910[] tab, TreeNodeb77a8d9c3c319e50d4b02a976b347910 root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 first = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)tab[index];
if (root != first) {
Nodeb77a8d9c3c319e50d4b02a976b347910 rn;
tab[index] = root;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 rp = root.prev;
if ((rn = root.next) != null)
((TreeNodeb77a8d9c3c319e50d4b02a976b347910)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
final TreeNodeb77a8d9c3c319e50d4b02a976b347910 find(int h, Object k, Class6b3d0130bba23ae47fe2b8e8cddf0195 kc) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 p = this;
do {
int ph, dir; K pk;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
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;
}
final TreeNodeb77a8d9c3c319e50d4b02a976b347910 getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
final void treeify(Nodeb77a8d9c3c319e50d4b02a976b347910[] tab) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 root = null;
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 x = this, next; x != null; x = next) {
next = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class6b3d0130bba23ae47fe2b8e8cddf0195 kc = null;
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 p = root;;) {
int dir, ph;
K pk = p.key;
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);
TreeNodeb77a8d9c3c319e50d4b02a976b347910 xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
final Nodeb77a8d9c3c319e50d4b02a976b347910 untreeify(HashMapb77a8d9c3c319e50d4b02a976b347910 map) {
Nodeb77a8d9c3c319e50d4b02a976b347910 hd = null, tl = null;
for (Nodeb77a8d9c3c319e50d4b02a976b347910 q = this; q != null; q = q.next) {
Nodeb77a8d9c3c319e50d4b02a976b347910 p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
final TreeNodeb77a8d9c3c319e50d4b02a976b347910 putTreeVal(HashMapb77a8d9c3c319e50d4b02a976b347910 map, Nodeb77a8d9c3c319e50d4b02a976b347910[] tab,
int h, K k, V v) {
Class6b3d0130bba23ae47fe2b8e8cddf0195 kc = null;
boolean searched = false;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 root = (parent != null) ? root() : this;
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
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) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 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);
}
TreeNodeb77a8d9c3c319e50d4b02a976b347910 xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Nodeb77a8d9c3c319e50d4b02a976b347910 xpn = xp.next;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNodeb77a8d9c3c319e50d4b02a976b347910)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
final void removeTreeNode(HashMapb77a8d9c3c319e50d4b02a976b347910 map, Nodeb77a8d9c3c319e50d4b02a976b347910[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 first = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)tab[index], root = first, rl;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 succ = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)next, pred = prev;
if (pred == null)
tab[index] = first = succ;
else
pred.next = succ;
if (succ != null)
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNodeb77a8d9c3c319e50d4b02a976b347910 p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNodeb77a8d9c3c319e50d4b02a976b347910 sr = s.right;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
TreeNodeb77a8d9c3c319e50d4b02a976b347910 r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNodeb77a8d9c3c319e50d4b02a976b347910 pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
final void split(HashMapb77a8d9c3c319e50d4b02a976b347910 map, Nodeb77a8d9c3c319e50d4b02a976b347910[] tab, int index, int bit) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 b = this;
// Relink into lo and hi lists, preserving order
TreeNodeb77a8d9c3c319e50d4b02a976b347910 loHead = null, loTail = null;
TreeNodeb77a8d9c3c319e50d4b02a976b347910 hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 e = b, next; e != null; e = next) {
next = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
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);
}
}
}
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
static b77a8d9c3c319e50d4b02a976b347910 TreeNodeb77a8d9c3c319e50d4b02a976b347910 rotateLeft(TreeNodeb77a8d9c3c319e50d4b02a976b347910 root,
TreeNodeb77a8d9c3c319e50d4b02a976b347910 p) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static b77a8d9c3c319e50d4b02a976b347910 TreeNodeb77a8d9c3c319e50d4b02a976b347910 rotateRight(TreeNodeb77a8d9c3c319e50d4b02a976b347910 root,
TreeNodeb77a8d9c3c319e50d4b02a976b347910 p) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}
static b77a8d9c3c319e50d4b02a976b347910 TreeNodeb77a8d9c3c319e50d4b02a976b347910 balanceInsertion(TreeNodeb77a8d9c3c319e50d4b02a976b347910 root,
TreeNodeb77a8d9c3c319e50d4b02a976b347910 x) {
x.red = true;
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
static b77a8d9c3c319e50d4b02a976b347910 TreeNodeb77a8d9c3c319e50d4b02a976b347910 balanceDeletion(TreeNodeb77a8d9c3c319e50d4b02a976b347910 root,
TreeNodeb77a8d9c3c319e50d4b02a976b347910 x) {
for (TreeNodeb77a8d9c3c319e50d4b02a976b347910 xp, xpl, xpr;;) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
else if (x.red) {
x.red = false;
return root;
}
else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
}
else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
/**
* Recursive invariant check
*/
static b77a8d9c3c319e50d4b02a976b347910 boolean checkInvariants(TreeNodeb77a8d9c3c319e50d4b02a976b347910 t) {
TreeNodeb77a8d9c3c319e50d4b02a976b347910 tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNodeb77a8d9c3c319e50d4b02a976b347910)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
}
}Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Déclaration：
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Article précédent：Exemple de code de TreeMap dans la collection JavaArticle suivant：Exemple de code de TreeMap dans la collection Java
Articles Liés
Voir plus- Pourquoi les caractères cyrilliques sont-ils corrompus lors de l'exportation de rapports Jasper au format PDF ?
- Devriez-vous toujours utiliser « final » pour les paramètres de méthode et les variables locales en Java ?
- Comment éviter les exceptions d’analyse de chaîne de date en Java ?
- Quand devriez-vous utiliser finalize() si ce n’est pas fiable ?
- MVC a-t-il sa place dans le développement Android ?