HashMap is a hash table, and the stored content is a key-value mapping. HashMap inherits from AbstractMap and implements the Map, Cloneable, and Serializable interfaces.
(1) HashMap is not thread-safe, and the key-value can be null and is unordered.
(2) The initial size of HashMap is 16, the maximum size is 2 to the 30th power, and the default loading factor is 0.75.
(3) The initial capacity is just the capacity of the hash table when it is created, and the load factor is a measure of how full the hash table can be before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table needs to be rehashed (rebuilding the internal data structure)
Integer Iterator =map.entrySet().iterator()(iterator.hasNext())
{
Map.Entry entry=(Map.Entry)iterator.next()key=(String)enrty.getKey()value=(Integer)entry.getValue()}
=Integer =Inerator =map.keySet().iterator()(iterator.hasNext())
{
key=(String)iterator.next()value=(Integer)map.get(key)} (3 ) Traverse the values of HashMap: The first step is to obtain the value set based on value, and iteratively traverse the value set
=Collection =map.values()Iterator = .iterator()(iterator.hasNext())
{
value=(Integer)iterator.next()}
() Object () (Object key) (Object value) Set<entry>> () (Object key) () Set () (keyvalue) (Map ? > map) (Object key) () Collection ()</entry>HashMap sample code:
public class Hello {
public void testHashMapAPIs()
{
Random r = new Random();
HashMap<string> 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();
}
}</string>
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 empty
public class HashMap<k> extends AbstractMap<k>
implements Map<k>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
static final int DEFAULT_INITIAL_CAPACITY = 1 implements Map.Entry<k> {
final int hash;
final K key;
V value;
Node<k> next;
Node(int hash, K key, V value, Node<k> 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.Entry, ?> e = (Map.Entry, ?>) 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 Class> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class> 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 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 = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
transient Node<k>[] table;//数据表
transient Set<map.entry>> 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 MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map extends K, ? extends V> 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 threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry extends K, ? extends V> 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) {
Node<k> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//通过hash和key获得节点
final Node<k> getNode(int hash, Object key) {
Node<k>[] tab; Node<k> 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 ((TreeNode<k>)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) {
Node<k>[] tab; Node<k> 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 {
Node<k> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<k>)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 Node<k>[] resize() {
Node<k>[] 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 = DEFAULT_INITIAL_CAPACITY)
newThr = oldThr 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 [] newTab = (Node<k>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<k>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<k> loHead = null, loTail = null;
Node<k> hiHead = null, hiTail = null;
Node<k> 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(Node<k>[] tab, int hash) {
int n, index; Node<k> e;
if (tab == null || (n = tab.length) hd = null, tl = null;
do {
TreeNode<k> 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(Map extends K, ? extends V> m) {
putMapEntries(m, true);
}
public V remove(Object key) {
Node<k> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<k> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<k>[] tab; Node<k> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<k> 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 = ((TreeNode<k>)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)
((TreeNode<k>)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() {
Node<k>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i [] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
public Set<k> keySet() {
Set<k> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet<k> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<k> 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 Spliterator<k> spliterator() {
return new KeySpliterator(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer super K> action) {
Node<k>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
public Collection<v> values() {
Collection<v> vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollection<v> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<v> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<v> spliterator() {
return new ValueSpliterator(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer super V> action) {
Node<k>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
public Set<map.entry>> entrySet() {
Set<map.entry>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<map.entry>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<map.entry>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry,?> e = (Map.Entry,?>) o;
Object key = e.getKey();
Node<k> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry,?> e = (Map.Entry,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<map.entry>> spliterator() {
return new EntrySpliterator(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer super Map.Entry<k>> action) {
Node<k>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i 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) {
Node<k> 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) {
Node<k> 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) {
Node<k> 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,
Function super K, ? extends V> mappingFunction) {
if (mappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<k>[] tab; Node<k> first; int n, i;
int binCount = 0;
TreeNode<k> t = null;
Node<k> 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 = (TreeNode<k>)first).getTreeNode(hash, key);
else {
Node<k> 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,
BiFunction super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
Node<k> 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,
BiFunction super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<k>[] tab; Node<k> first; int n, i;
int binCount = 0;
TreeNode<k> t = null;
Node<k> 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 = (TreeNode<k>)first).getTreeNode(hash, key);
else {
Node<k> 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,
BiFunction super V, ? super V, ? extends V> remappingFunction) {
if (value == null)
throw new NullPointerException();
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<k>[] tab; Node<k> first; int n, i;
int binCount = 0;
TreeNode<k> t = null;
Node<k> 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 = (TreeNode<k>)first).getTreeNode(hash, key);
else {
Node<k> 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(BiConsumer super K, ? super V> action) {
Node<k>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
@Override
public void replaceAll(BiFunction super K, ? super V, ? extends V> function) {
Node<k>[] tab;
if (function == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i 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() {
HashMap<k> result;
try {
result = (HashMap<k>)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 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 = MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY :
tableSizeFor((int)fc));
float ft = (float)cap * lf;
threshold = ((cap [] tab = (Node<k>[])new Node[cap];
table = tab;
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i next; // next entry to return
Node<k> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<k>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index nextNode() {
Node<k>[] t;
Node<k> 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 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 Iterator<k> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<v> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<map.entry>> {
public final Map.Entry<k> next() { return nextNode(); }
}
static class HashMapSpliterator<k> {
final HashMap<k> map;
Node<k> 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(HashMap<k> 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) m = map;
est = m.size;
expectedModCount = m.modCount;
Node<k>[] 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 KeySpliterator<k>
extends HashMapSpliterator<k>
implements Spliterator<k> {
KeySpliterator(HashMap<k> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public KeySpliterator<k> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new KeySpliterator(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer super K> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<k> m = map;
Node<k>[] tab = m.table;
if ((hi = fence) = hi &&
(i = index) >= 0 && (i p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.key);
p = p.next;
}
} while (p != null || i action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<k>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index
extends HashMapSpliterator<k>
implements Spliterator<v> {
ValueSpliterator(HashMap<k> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public ValueSpliterator<k> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new ValueSpliterator(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer super V> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<k> m = map;
Node<k>[] tab = m.table;
if ((hi = fence) = hi &&
(i = index) >= 0 && (i p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p.value);
p = p.next;
}
} while (p != null || i action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<k>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index
extends HashMapSpliterator<k>
implements Spliterator<map.entry>> {
EntrySpliterator(HashMap<k> m, int origin, int fence, int est,
int expectedModCount) {
super(m, origin, fence, est, expectedModCount);
}
public EntrySpliterator<k> trySplit() {
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid || current != null) ? null :
new EntrySpliterator(map, lo, index = mid, est >>>= 1,
expectedModCount);
}
public void forEachRemaining(Consumer super Map.Entry<k>> action) {
int i, hi, mc;
if (action == null)
throw new NullPointerException();
HashMap<k> m = map;
Node<k>[] tab = m.table;
if ((hi = fence) = hi &&
(i = index) >= 0 && (i p = current;
current = null;
do {
if (p == null)
p = tab[i++];
else {
action.accept(p);
p = p.next;
}
} while (p != null || i > action) {
int hi;
if (action == null)
throw new NullPointerException();
Node<k>[] tab = map.table;
if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
while (current != null || index e = current;
current = current.next;
action.accept(e);
if (map.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
}
}
return false;
}
public int characteristics() {
return (fence newNode(int hash, K key, V value, Node<k> next) {
return new Node(hash, key, value, next);
}
// For conversion from TreeNodes to plain nodes
Node<k> replacementNode(Node<k> p, Node<k> next) {
return new Node(p.hash, p.key, p.value, next);
}
// Create a tree bin node
TreeNode<k> newTreeNode(int hash, K key, V value, Node<k> next) {
return new TreeNode(hash, key, value, next);
}
// For treeifyBin
TreeNode<k> replacementTreeNode(Node<k> p, Node<k> next) {
return new TreeNode(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(Node<k> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<k> p) { }
// Called only from writeObject, to ensure compatible ordering.
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
Node<k>[] tab;
if (size > 0 && (tab = table) != null) {
for (int i = 0; i e = tab[i]; e != null; e = e.next) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
}
}
static final class TreeNode<k> extends LinkedHashMap.Entry<k> {
TreeNode<k> parent; // red-black tree links
TreeNode<k> left;
TreeNode<k> right;
TreeNode<k> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<k> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<k> root() {
for (TreeNode<k> 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 <k> void moveRootToFront(Node<k>[] tab, TreeNode<k> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<k> first = (TreeNode<k>)tab[index];
if (root != first) {
Node<k> rn;
tab[index] = root;
TreeNode<k> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<k>)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 TreeNode<k> find(int h, Object k, Class> kc) {
TreeNode<k> p = this;
do {
int ph, dir; K pk;
TreeNode<k> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph 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) [] tab) {
TreeNode<k> root = null;
for (TreeNode<k> x = this, next; x != null; x = next) {
next = (TreeNode<k>)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;
Class> kc = null;
for (TreeNode<k> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph xp = p;
if ((p = (dir untreeify(HashMap<k> map) {
Node<k> hd = null, tl = null;
for (Node<k> q = this; q != null; q = q.next) {
Node<k> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
final TreeNode<k> putTreeVal(HashMap<k> map, Node<k>[] tab,
int h, K k, V v) {
Class> kc = null;
boolean searched = false;
TreeNode<k> root = (parent != null) ? root() : this;
for (TreeNode<k> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph 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);
}
TreeNode<k> xp = p;
if ((p = (dir xpn = xp.next;
TreeNode<k> x = map.newTreeNode(h, k, v, xpn);
if (dir )xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
final void removeTreeNode(HashMap<k> map, Node<k>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<k> first = (TreeNode<k>)tab[index], root = first, rl;
TreeNode<k> succ = (TreeNode<k>)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;
}
TreeNode<k> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<k> 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
TreeNode<k> sr = s.right;
TreeNode<k> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<k> 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) {
TreeNode<k> 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;
}
TreeNode<k> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<k> 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(HashMap<k> map, Node<k>[] tab, int index, int bit) {
TreeNode<k> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<k> loHead = null, loTail = null;
TreeNode<k> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<k> e = b, next; e != null; e = next) {
next = (TreeNode<k>)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 TreeNode<k> rotateLeft(TreeNode<k> root,
TreeNode<k> p) {
TreeNode<k> 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 <k> TreeNode<k> rotateRight(TreeNode<k> root,
TreeNode<k> p) {
TreeNode<k> 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 <k> TreeNode<k> balanceInsertion(TreeNode<k> root,
TreeNode<k> x) {
x.red = true;
for (TreeNode<k> 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 <k> TreeNode<k> balanceDeletion(TreeNode<k> root,
TreeNode<k> x) {
for (TreeNode<k> 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 {
TreeNode<k> 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 {
TreeNode<k> 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 <k> boolean checkInvariants(TreeNode<k> t) {
TreeNode<k> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<k>)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 </k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></map.entry></k></k></k></k></k></k></v></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></map.entry></v></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></map.entry></k></map.entry></map.entry></map.entry></map.entry></k></v></v></v></v></v></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></k></map.entry></k></k></k></k></k></k></k>The above is the detailed content of Detailed explanation of HashMap in Java collections. For more information, please follow other related articles on the PHP Chinese website!
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于结构化数据处理开源库SPL的相关问题，下面就一起来看一下java下理想的结构化数据处理类库，希望对大家有帮助。
Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于PriorityQueue优先级队列的相关知识，Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，下面一起来看一下，希望对大家有帮助。
完全掌握Java锁（图文解析）Jun 14, 2022 am 11:47 AM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于java锁的相关问题，包括了独占锁、悲观锁、乐观锁、共享锁等等内容，下面一起来看一下，希望对大家有帮助。
一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于多线程的相关问题，包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容，希望对大家有帮助。
Java基础归纳之枚举May 26, 2022 am 11:50 AM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于枚举的相关问题，包括了枚举的基本操作、集合类对枚举的支持等等内容，下面一起来看一下，希望对大家有帮助。
详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM本篇文章给大家带来了关于Java的相关知识，其中主要介绍了关于关键字中this和super的相关问题，以及他们的一些区别，下面一起来看一下，希望对大家有帮助。
java中封装是什么May 16, 2019 pm 06:08 PM封装是一种信息隐藏技术，是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法；封装可以被认为是一个保护屏障，防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private，protected和public实现。
Java数据结构之AVL树详解Jun 01, 2022 am 11:39 AM本篇文章给大家带来了关于java的相关知识，其中主要介绍了关于平衡二叉树（AVL树）的相关知识，AVL树本质上是带了平衡功能的二叉查找树，下面一起来看一下，希望对大家有帮助。
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
How Long Does It Take To Beat Split Fiction?
1 months agoByDDD
R.E.P.O. Save File Location: Where Is It & How to Protect It?
1 months agoByDDD
R.E.P.O. Best Graphic Settings
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Assassin's Creed Shadows: Seashell Riddle Solution
1 weeks agoByDDD
Hot Tools
SublimeText3 English version
Recommended: Win version, supports code prompts!
SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.
WebStorm Mac version
Useful JavaScript development tools
SublimeText3 Linux new version
SublimeText3 Linux latest version
MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.
