什么是HashMap？
- HashMap是一个散列表，它是通过键值对(key-value)的形式来存储数据
继承关系
- 位于java.util包中，继承AbstractMap抽象类，实现了map、Cloneable、java.io.Serializable 接口
优缺点
-
优点
- 可快速进行访问
- 可允许空key/空value
- 无序，不会记录插入的顺序
-
缺点
- 线程不安全。在多线程环境下哈希桶中的链表容易形成环，导致cpu占用率变高(https://coolshell.cn/articles/9606.html)
底层实现数据结构
JDK1.8以前：数组+链表
JDK1.8以后：数组+链表+红黑树
JDK1.8源码解析
1.Map
public interface Map<K, V> {
//有效元素的个数
int size();
//集合是否为空
boolean isEmpty();
//集合中是否包含key值
boolean containsKey(Object key);
//集合中是否包含value值
boolean containsValue(Object value);
//根据key值从集合中获取对应的value
V get(Object key);
//将key value存储到集合中
V put(K key, V value);
//将一个集合的数据添加到这个集合中
void putAll(Map<? extends K, ? extends V> m);
//根据key从集合中移除对应的数据
V remove(Object key);
//将集合中的元素全部清除
void clear();
//返回所有key的集合 key值不允许重复
Set<K> keySet();
//返回所有value的集合
Collection<V> values();
//所有键值对的集合，不允许重复
Set<Entry<K, V>> entrySet();
//元素是否相等
boolean equals(Object o);
//返回map的hash值
int hashCode();
// Defaultable methods @since 1.8 外部不能调用
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
}
//内部集合遍历 并将每个元素的key value返回
@RequiresApi(api = Build.VERSION_CODES.KITKAT)
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map. 这通常意味着entry不再在映射中
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
//内部接口类
interface Entry<K, V> {
//获取一个元素的key值
K getKey();
//获取一个元素的value值
V getValue();
//修改这个元素的value值
V setValue(V value);
//元素是否相等
boolean equals(Object o);
//返回元素的hash值
int hashCode();
//根据key值比较两个是否相等
public static <K extends Comparable<? super K>, V> Comparator<java.util.Map.Entry<K, V>> comparingByKey() {
return (Comparator<java.util.Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
//根据value值比较两个是否相等
public static <K, V extends Comparable<? super V>> Comparator<java.util.Map.Entry<K, V>> comparingByValue() {
return (Comparator<java.util.Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
//根据key值比较两个是否相等 可自定义比较器
public static <K, V> Comparator<java.util.Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<java.util.Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
//根据value值比较两个是否相等 可自定义比较器
public static <K, V> Comparator<java.util.Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<java.util.Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
........
}
说明
-
1.上述是Map接口类的部分源码
-
2.Map是一个接口泛型类，其中K代表key，V代表value
-
3.Map定义了集合的一些操作
int size():返回集合的有效元素的个数 boolean isEmpty()：判断集合中是否含有有效元素 boolean containsKey(Object key)：判断集合中是否包含对应的key值 boolean containsValue(Object value):判断集合中是否包含对应的value值 V get(Object key)：根据key值从集合中获取对应的value V put(K key, V value)：将key value存储到集合中 void putAll(Map<? extends K, ? extends V> m)：将一个集合的数据添加到这个集合中 V remove(Object key)：根据key从集合中移除对应的元素 void clear()：将集合中的元素全部清除 Set<K> keySet()：返回所有key的集合 Collection<V> values()：返回所有value的集合 Set<Entry<K, V>> entrySet()：所有键值对的集合 boolean equals(Object o)：元素是否相等 -
4.Entry是Map的内部类，它用来表示一个元素
K getKey()：获取元素的key值 V getValue()：获取元素的value值 V setValue(V value)：修改这个元素的value值 boolean equals(Object o)：元素是否相等 int hashCode()：返回元素的hash值
AbstractMap
public abstract class AbstractMap<K,V> implements Map<K,V> {
//获取集合元素个数
public int size() {
return entrySet().size();
}
//元素的个数是否为空
public boolean isEmpty() {
return size()==0;
}
public boolean containsKey(Object key) {
//将Set<Entry<K,V>>变成 Iterator<Entry<K,V>>
Iterator<Entry<K,V>> i = entrySet().iterator();
//若传入的key为空
if (key==null) {
//循环遍历元素的key 若元素的key相同 则返回true 否则返回false
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
//循环遍历key 若key和传入的key相同 则返回true 否则返回false
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}
public V get(Object key) {
//
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
//将key/value存入到集合中
public V put(K key, V value) {
throw new UnsupportedOperationException();
}
public void putAll(Map<? extends K, ? extends V> m) {
for (Entry<? extends K, ? extends V> e : m.entrySet()) {
put(e.getKey(), e.getValue());
}
}
//移除数据
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
//若参数key为空时，遍历集合，当集合中的某个元素的key为空时给correctEntry赋值，停止遍历
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
//若参数key不为空时，遍历集合，当集合中的某个元素的key等于参数时给correctEntry赋值，停止遍历
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
//找到了key对应的entry，获取对应的value 用于返回
//在返回value时，先调用的iterator的remove方法
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
public void clear() {
entrySet().clear();
}
//不能被序列化的属性
transient Set<K> keySet;
transient Collection<V> values;
//
public Set<K> keySet() {
//1.默认为空
Set<K> ks = keySet;
if (ks == null) {
//构建AbstractSet对象 是set的子类
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
//获取key
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}
//entrySet抽象方法
public abstract Set<Entry<K,V>> entrySet();
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator< Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}
protected Object clone() throws CloneNotSupportedException {
AbstractMap<?,?> result = (AbstractMap<?,?>)super.clone();
result.keySet = null;
result.values = null;
return result;
}
public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable {
private static final long serialVersionUID = -8499721149061103585L;
private final K key;
private V value;
/**
* Creates an entry representing a mapping from the specified
* key to the specified value.
*
* @param key the key represented by this entry
* @param value the value represented by this entry
*/
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
/**
* Creates an entry representing the same mapping as the
* specified entry.
*
* @param entry the entry to copy
*/
public SimpleEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
/**
* Returns the key corresponding to this entry.
*
* @return the key corresponding to this entry
*/
public K getKey() {
return key;
}
/**
* Returns the value corresponding to this entry.
*
* @return the value corresponding to this entry
*/
public V getValue() {
return value;
}
/**
* Replaces the value corresponding to this entry with the specified
* value.
*
* @param value new value to be stored in this entry
* @return the old value corresponding to the entry
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
/**
* Compares the specified object with this entry for equality.
* Returns {@code true} if the given object is also a map entry and
* the two entries represent the same mapping. More formally, two
* entries {@code e1} and {@code e2} represent the same mapping
* if<pre>
* (e1.getKey()==null ?
* e2.getKey()==null :
* e1.getKey().equals(e2.getKey()))
* &&
* (e1.getValue()==null ?
* e2.getValue()==null :
* e1.getValue().equals(e2.getValue()))</pre>
* This ensures that the {@code equals} method works properly across
* different implementations of the {@code Map.Entry} interface.
*
* @param o object to be compared for equality with this map entry
* @return {@code true} if the specified object is equal to this map
* entry
* @see #hashCode
*/
public boolean equals(Object o) {
if (!(o instanceof java.util.Map.Entry))
return false;
java.util.Map.Entry<?,?> e = (java.util.Map.Entry<?,?>)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
/**
* Returns the hash code value for this map entry. The hash code
* of a map entry {@code e} is defined to be: <pre>
* (e.getKey()==null ? 0 : e.getKey().hashCode()) ^
* (e.getValue()==null ? 0 : e.getValue().hashCode())</pre>
* This ensures that {@code e1.equals(e2)} implies that
* {@code e1.hashCode()==e2.hashCode()} for any two Entries
* {@code e1} and {@code e2}, as required by the general
* contract of {@link Object#hashCode}.
*
* @return the hash code value for this map entry
* @see #equals
*/
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
/**
* Returns a String representation of this map entry. This
* implementation returns the string representation of this
* entry's key followed by the equals character ("<tt>=</tt>")
* followed by the string representation of this entry's value.
*
* @return a String representation of this map entry
*/
public String toString() {
return key + "=" + value;
}
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
}
boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
}
说明
-
1.上述是AbstractMap的部分源码
-
2.AbstarctMap是一个泛型抽象类，并实现了Map接口
-
3.抽象方法，需要子类自己去实现。用于返回一个Set对象，可用于遍历集合的元素，从而获取元素的key/value。
public abstract Set<Entry<K,V>> entrySet(); -
4.返回一个Set对象，可用于遍历集合中所有元素的key值。keySet不能被序列化
transient Set<K> keySet; public Set<K> keySet() { //1.默认为空 Set<K> ks = keySet; if (ks == null) { //构建AbstractSet对象 是set的子类 ks = new AbstractSet<K>() { public Iterator<K> iterator() { return new Iterator<K>() { private Iterator<Entry<K,V>> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public K next() { //获取key return i.next().getKey(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains(Object k) { return AbstractMap.this.containsKey(k); } }; keySet = ks; } return ks; } -
5.返回一个Collection对象，可用于遍历集合中所有元素的value值，values不可以被序列化
transient Collection<V> values; public Collection<V> values() { Collection<V> vals = values; if (vals == null) { vals = new AbstractCollection<V>() { public Iterator<V> iterator() { return new Iterator<V>() { private Iterator< Entry<K,V>> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public V next() { return i.next().getValue(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains(Object v) { return AbstractMap.this.containsValue(v); } }; values = vals; } return vals; } -
6.返回集合的有效元素的个数
public int size() { return entrySet().size(); } -
7.判断集合中的元素个数是否为0
public boolean isEmpty() { return size()==0; } -
8.遍历集合中所有的key值，若集合中的key值包含传入的key值则返回true；反之，则返回false
public boolean containsKey(Object key) { //将Set<Entry<K,V>>变成 Iterator<Entry<K,V>> Iterator<Entry<K,V>> i = entrySet().iterator(); //若传入的key为空 if (key==null) { //循环遍历元素的key 若元素的key相同 则返回true 否则返回false while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) return true; } } else { //循环遍历key 若key和传入的key相同 则返回true 否则返回false while (i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) return true; } } return false; } -
9.遍历集合中所有的value值，若集合中的value值包含传入的value值则返回true；反之，则返回false
public boolean containsValue(Object value) { Iterator<Entry<K,V>> i = entrySet().iterator(); if (value==null) { while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getValue()==null) return true; } } else { while (i.hasNext()) { Entry<K,V> e = i.next(); if (value.equals(e.getValue())) return true; } } return false; } -
10.遍历集合中所有的key值，若集合中的key值包含传入的key值则返回对应的value；反之，则返回null
public V get(Object key) { // Iterator<Entry<K,V>> i = entrySet().iterator(); if (key==null) { while (i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) return e.getValue(); } } else { while (i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) return e.getValue(); } } return null; } -
11.将key-value存储到集合中。没有真正的实现，需要子类根据自身规则去实现
public V put(K key, V value) { throw new UnsupportedOperationException(); } -
12.遍历传入的map集合，将单个元素通过put()依次存入到集合中
public void putAll(Map<? extends K, ? extends V> m) { for (Entry<? extends K, ? extends V> e : m.entrySet()) { put(e.getKey(), e.getValue()); } } -
13.根据key从集合中查找，若查找到了，则调用remove(）进行移除
public V remove(Object key) { Iterator<Entry<K,V>> i = entrySet().iterator(); Entry<K,V> correctEntry = null; //若参数key为空时，遍历集合，当集合中的某个元素的key为空时给correctEntry赋值，停止遍历 if (key==null) { while (correctEntry==null && i.hasNext()) { Entry<K,V> e = i.next(); if (e.getKey()==null) correctEntry = e; } } else { //若参数key不为空时，遍历集合，当集合中的某个元素的key等于参数时给correctEntry赋值，停止遍历 while (correctEntry==null && i.hasNext()) { Entry<K,V> e = i.next(); if (key.equals(e.getKey())) correctEntry = e; } } V oldValue = null; //找到了key对应的entry，获取对应的value 用于返回 //在返回value时，先调用的iterator的remove方法 if (correctEntry !=null) { oldValue = correctEntry.getValue(); i.remove(); } return oldValue; } -
14.清除整个集合中所有的元素
public void clear() { entrySet().clear(); }
Iterator
public interface Iterator<E> {
public boolean hasNext();
public E next();
public default void remove() { throw new RuntimeException("Stub!"); }
public default void forEachRemaining(Consumer<? super E> action) { t
}
说明
-
1.迭代器接口，用于迭代遍历集合中的元素
-
2.判断集合中是否还有元素没有被遍历到。若集合中还有元素没有被遍历到，则返回true；若集合中没有可以被遍历的人元素，则返回false
public boolean hasNext(); -
3.从集合中取还没有被遍历到的元素
public E next()
HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//定义一个序列化id
private static final long serialVersionUID = 362498820763181265L;
//初始化容量为16 1左移四位
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量 1左移动30位
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子默认位0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
//桶中结构转化为红黑树对应的数组的最小大小，如果当前容量小于它，就不会将链表转化为红黑树，而是用resize()代替
static final int MIN_TREEIFY_CAPACITY = 64;
//结点 泛型K,V 实现了map的entry接口
static class Node<K,V> implements Map.Entry<K,V> {
//hash值 不可修改
final int hash;
//key 不可修改
final K key;
//value 可修改
V value;
//下一个结点 使用的线性链表
Node<K,V> next;
//初始化的时候传递进来
Node(int hash, K key, V value, Node<K,V> 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 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) {
Entry<?,?> e = ( Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
//object 的hashcode方法调用identityHashCodeNative方法 通过native让系统分配一个
//objects的hashcode方法中判断object是否为空 若为空返回0 若不为空则调用object的hashcode方法
static final int hash(Object key) {
//若key为空 则返回0 若key不为空 将key的hashcode的高16位和低16位异或
//直接使用hashcode很容易产生碰撞 散列值一般有效的是低4位 2/8/32。。。。。。是16的倍数 容易产生碰撞
//考虑速度 质量 作用 使用高16位和低16位异或产生的 之后还产生碰撞的也是使用红黑树优化 O(logn)
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//存储元素的素组 是2的幂
transient Node<K,V>[] table;
//存放具体元素的集合
transient Set<Entry<K,V>> entrySet;
//存放元素的个数，注意这个不等于数组的长度。
transient int size;
//操作计数器 删除 增加都会
transient int modCount;
// 临界值 当实际节点个数超过临界值(容量*填充因子)时，会进行扩容
int threshold;
// 通过tableSizeFor(cap)计算出不小于initialCapacity的最近的2的幂作为初始容量，
// 将其先保存在threshold里，当put时判断数组为空会调用resize分配内存，
// 并重新计算正确的threshold
final float loadFactor;
//默认无参数构造函数
public HashMap() {
//在默认构造函数中只是指定了装载因子的大小 默认0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//有参数构造函数 调用重载
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
//若自定义容量 容量不可以为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//若指定容量的操作是最大值 则使用最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//装载因子不能小于等于0以及无理数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//指定装载因子
this.loadFactor = loadFactor;
//计算扩容临界值
this.threshold = tableSizeFor(initialCapacity);
}
//可以直接传递一个HashMap
public HashMap( Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Returns the number of key-value mappings in this map.
*
* @return the number of key-value mappings in this map
*/
public int size() {
return size;
}
/**
* Returns <tt>true</tt> if this map contains no key-value mappings.
*
* @return <tt>true</tt> if this map contains no key-value mappings
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 返回最近的不小于输入参数的2的整数次幂。比如10，则返回16
*/
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 < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* 将参数map中的数据put到当前集合中
* @param m
* @param evict
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取传入的集合的大小
int s = m.size();
//map中的元素个数大于0
if (s > 0) {
//第一次 node结点数组为空
if (table == null) {
// pre-size， 100个装载因子为0.75 计算出最大容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//若计算出的需要的元素个数超过了阈值 则需要重新计算阈值
if (t > threshold)
threshold = tableSizeFor(t);
//table不为空 且传入的数据元素个数大于阈值的时候 重新计算
} else if (s > threshold) {
//进行扩容
resize();
}
//将map中的元素添加进去
for (Entry<? extends K, ? extends V> e : m.entrySet()) {
//遍历entry 调用put进行存储
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
//put 存入key value 最终也是调用putVal()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//将指定映射的所有映射关系复制到此映射中
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
/**
*
* @param hash hash值 通过hash()进行计算
* @param key 元素的key值
* @param value 元素的value值
* @param onlyIfAbsent 只有在没有
* @param evict 是否驱逐
* 1.第一次添加元素 桶为空 重新计算一次
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[]
tab;
Node<K,V> p;
int n, i;
//若table为空 即桶为空 进行扩容 n为桶的个数
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n-1)&hash：确定元素存在在那个桶中
//若在table对应的位置中没有元素存入，那么在该位置新建结点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//若桶中已存在元素 p就是通过(n-1)&hash计算出的结点
else {
Node<K,V> e; K k;
//比较桶中第一个元素的hash值相同，key相同
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//hash值不相同或key不相同
else if (p instanceof TreeNode)//红黑数
e = ((TreeNode<K,V>)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);
//若结点数量到达阈值，调用treeifbin() 做进一步判断 是否需要转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
//跳出循环
break;
}
//判断链表中结点的key值与插入的元素的key是否相同 表示已经插入
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//用于遍历桶中的链表，与前面的e=p.next()结合
p = e;
}
}
//若在桶中找到key值，hash值与插入的元素相同的结点
if (e != null) { // existing mapping for key
//旧值
V oldValue = e.value;
//false或者旧值为空
if (!onlyIfAbsent || oldValue == null)
//用新值换旧值
e.value = value;
//访问后回调
afterNodeAccess(e);
return oldValue;
}
}
//结构性修改
++modCount;
//进行扩容
if (++size > threshold)
resize();
//插入后回调
afterNodeInsertion(evict);
return null;
}
/**
* 重新分配内存
* 1.当数组没有初始化时 按照之前在threshold中保存的初始化容量分配保存，没有就用缺省值
* 2.当超过限制时，就扩充两倍。当进行扩容时无需重新计算hash，只需要看新增高位bit是1还是0，是0的话索引不变，是1的话原索引+oldCap
* @return
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//
if (oldCap > 0) {
//集合已经在最大容量了 其阈值是Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
//容器的容量是原来的2次幂
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} else if (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 < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> 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,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//若数组容量小于MIN_TREEIFY_CAPACITY，不进行转换而是进行resize操作
//若桶为空或者桶的数量小于64 那么只进行扩容操作
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//若桶不为空或者数量大于64 且tab[index = (n - 1) & hash])对应位置有结点e
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//通过do while取出结点数据 然后将其转换为TreeNode
do {
//将该node转换为TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);//将Node转换为TreeNode
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);//重新排序形成红黑树
}
}
}
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// Callbacks to allow LinkedHashMap post-actions
//访问后回调
void afterNodeAccess(Node<K,V> p) { }
//插入后回调
void afterNodeInsertion(boolean evict) { }
//移除后回调
void afterNodeRemoval(Node<K,V> p) { }
@Override
public Object clone() {
HashMap<K,V> result;
try {
result = (HashMap<K,V>)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;
}
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
LinkedHashMapEntry<K,V> before, after;
}
static final class TreeNode<K,V> extends LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> 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,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
/**
* 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)
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;
}
/**
* 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
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
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;
}
/**
* 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) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> 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);
TreeNode<K,V> 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);
}
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(java.util.HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> 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) {
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);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> 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)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
final void removeTreeNode(java.util.HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)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,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> 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,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> 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,V> 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,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // detach
TreeNode<K,V> 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);
}
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
final void split(java.util.HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)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 <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> 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,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> 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,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true;
for (TreeNode<K,V> 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,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> 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,V> 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,V> 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,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)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;
}
}
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* 根据key以及key的hash值获取对应的结点
* 1.首先判断结点数据为空以及数组对应位置是否含有数据
*
* 若结点数组为空或者对应位置的结点为空 表示没有数据 返回空
*
* 若结点数组不为空且对应位置的结点不为空 表示有数组。那么
* 1.若第一个元素的key和hash相同 表示就是第一个元素 直接返回 时间复杂度：O(1)
* 2.若不是第一个元素，判断是否是红黑树 若是的话直接根据红黑树的规则来判断 时间复杂度：O(logn)
* 不是红黑树 那就是链表 则循环遍历链表进行查找 时间复杂度：O(n) n<8
*
* @param hash hash for key key的hash值
* @param key the key key
* @return the node, or null if none 结点
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//结点数组不为空且通过((n-1)*hash)计算得到对应的位置的数据存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//若桶的第一个结点的key值和hash值相等 那么结点就是第一个 无序做遍历操作
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//若第一个结点后面还有结点 判断是否是红黑树 若是的话调用getTreeNode()根据红黑树的规则获取
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//若是链表的话 遍历链表取得结点数据 然后判断key/hash来判断
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
/**
*
*
* @param hash hash for key key对应的hash
* @param key the key key
* @param value value
* @param matchValue 是否需要匹配value
* @param movable 如果为false，则在移除时不要移动其他节点
* @return the node, or null if none
*/
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//若结点数组不能为空且对应位置的结点有数据
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> 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,V>)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,V>)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,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
/********************************************************************/
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return 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,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> 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 = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return 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,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
public Set<Entry<K,V>> entrySet() {
Set<Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Entry))
return false;
Entry<?,?> e = ( Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Entry) {
Entry<?,?> e = (Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator< Entry<K,V>> spliterator() {
return new EntrySpliterator<>( HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
// Android-changed: Detect changes to modCount early.
for (int i = 0; (i < tab.length && modCount == mc); ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
/* ------------------------------------------------------------ */
// iterators
/**
* 1.hashMap的内部抽象类
* 2.存储了当前结点 下一个结点
*
*/
abstract class HashIterator {
//下一个结点
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
//记录修改的次数 以及整个结点数组 且当前位置为0
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] 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);
}
}
/**
* 判断下一个结点是否为null'
* @return
*/
public final boolean hasNext() {
return next != null;
}
/**
* 获取下一个结点
* @return
*/
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> 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() {
Node<K,V> 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<Entry<K,V>> {
public final Entry<K,V> next() { return nextNode(); }
}
......
}
说明
-
1.在HashMap中默认的容量是16，最大容量为2的30次方，其装载因子为0.75，也就是当集合元素个数超过12（16*0.75)时进行初次扩容，每次扩容为原来的2倍
//初始化容量为16 1左移四位 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量 1左移动30位 static final int MAXIMUM_CAPACITY = 1 << 30; //默认装载因子默认位0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; -
2.通过构造函数我们可以指定容量，内部会对传入的容量值通过tableSizeFor进行返回扩容阈值
-
3.当向散列表对应位置的桶中添加元素时，发现桶中的元素个数超过8个时，将链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8 -
4.当从散列表对应位置的桶中移除元素时，发现桶中的元素少于6个时，将红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6 -
5.当桶中的的元素由链表转换为红黑树时，还需要一个前提条件，那解释散列表中至少有64个桶
static final int MIN_TREEIFY_CAPACITY = 64; -
6.Node表示一个结点，也就是集合中的一个元素，它包含了元素的key，key对应的hash值，元素的value，以及下一个结点。其中hash和key不可修改，value和next可以被修改。可通过get获取对应的key/value
static class Node<K,V> implements Map.Entry<K,V> { //hash值 不可修改 final int hash; //key 不可修改 final K key; //value 可修改 V value; //下一个结点 使用的线性链表 Node<K,V> next; //初始化的时候传递进来 Node(int hash, K key, V value, Node<K,V> 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 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) { Entry<?,?> e = ( Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } } -
7.LinkedHashMapEntry继承了HashMap的Node类，只是在Node的基础上增加了前后结点。TreeNode继承LinkedHashMapEntry，在此基础上增加了左结点/右结点/父节点/下一个结点
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> { LinkedHashMapEntry<K,V> before, after; } static final class TreeNode<K,V> extends LinkedHashMapEntry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } /** * Returns root of tree containing this node. */ final TreeNode<K,V> root() { for (TreeNode<K,V> 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,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { int n; if (root != null && tab != null && (n = tab.length) > 0) { int index = (n - 1) & root.hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; if (root != first) { Node<K,V> rn; tab[index] = root; TreeNode<K,V> rp = root.prev; if ((rn = root.next) != null) ((TreeNode<K,V>)rn).prev = rp; if (rp != null) rp.next = rn; if (first != null) first.prev = root; root.next = first; root.prev = null; } assert checkInvariants(root); } } /** * 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) 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; } /** * 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 * order, just a consistent insertion rule to maintain * equivalence across rebalancings. Tie-breaking further than * necessary simplifies testing a bit. */ 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; } /** * 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) { x.parent = null; x.red = false; root = x; } else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> 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); TreeNode<K,V> 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); } /** * Returns a list of non-TreeNodes replacing those linked from * this node. */ final Node<K,V> untreeify(java.util.HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; } /** * Tree version of putVal. */ final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> 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) { 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); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; TreeNode<K,V> 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) ((TreeNode<K,V>)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null; } } } /** * Removes the given node, that must be present before this call. * This is messier than typical red-black deletion code because we * cannot swap the contents of an interior node with a leaf * successor that is pinned by "next" pointers that are accessible * independently during traversal. So instead we swap the tree * linkages. If the current tree appears to have too few nodes, * the bin is converted back to a plain bin. (The test triggers * somewhere between 2 and 6 nodes, depending on tree structure). */ final void removeTreeNode(java.util.HashMap<K,V> map, Node<K,V>[] tab, boolean movable) { int n; if (tab == null || (n = tab.length) == 0) return; int index = (n - 1) & hash; TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl; TreeNode<K,V> succ = (TreeNode<K,V>)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,V> p = this, pl = left, pr = right, replacement; if (pl != null && pr != null) { TreeNode<K,V> 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,V> sr = s.right; TreeNode<K,V> pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<K,V> 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,V> 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,V> r = p.red ? root : balanceDeletion(root, replacement); if (replacement == p) { // detach TreeNode<K,V> 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); } /** * Splits nodes in a tree bin into lower and upper tree bins, * or untreeifies if now too small. Called only from resize; * see above discussion about split bits and indices. * * @param map the map * @param tab the table for recording bin heads * @param index the index of the table being split * @param bit the bit of hash to split on */ final void split(java.util.HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; // Relink into lo and hi lists, preserving order TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; for (TreeNode<K,V> e = b, next; e != null; e = next) { next = (TreeNode<K,V>)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 <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> 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,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) { TreeNode<K,V> 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,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) { x.red = true; for (TreeNode<K,V> 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,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { for (TreeNode<K,V> 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,V> 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,V> 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,V> boolean checkInvariants(TreeNode<K,V> t) { TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right, tb = t.prev, tn = (TreeNode<K,V>)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; } } -
7.插入元素到集合中。首先会判断数组是否为空,若为空，则调用resize()进行扩容操作；之后根据计算出来的hash值通过(n - 1) & hash的计算，得出它在散列表中的索引位置，然后看索引位置是否有元素，若没有，则直接构建新节点插入该位置，其时间复杂度为O(1)；若该位置有元素了判断是否是红黑树，若是红黑树则通过treeNode.putTreeNode()将结点插入到红黑树中，其时间复杂度为O(logn);若不是红黑树，那么就是链表结构，那么就遍历链表，若查找到其key值和hash值相同，表示已经插入过了，直接修改value即可;若遍历到了末尾还没有查找到，那么表示没有被插入过，那么直接添加到结点的尾部，其时间复杂度为O(k) (k<8),若在链表插入的元素个数超过了8个，那么调用treeifyBin()将链表转换为红黑树。若是插入元素，那么size加1，最后若size大于扩容阈值，那么将调用resize()进行扩容
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,V>[] tab; Node<K,V> p; int n, i; //若table为空 即桶为空 进行扩容 n为桶的个数 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //(n-1)&hash：确定元素存在在那个桶中 //若在table对应的位置中没有元素存入，那么在该位置新建结点 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //若桶中已存在元素 p就是通过(n-1)&hash计算出的结点 else { Node<K,V> e; K k; //比较桶中第一个元素的hash值相同，key相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //hash值不相同或key不相同 else if (p instanceof TreeNode)//红黑数 e = ((TreeNode<K,V>)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); //若结点数量到达阈值，调用treeifbin() 做进一步判断 是否需要转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); //跳出循环 break; } //判断链表中结点的key值与插入的元素的key是否相同 表示已经插入 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //用于遍历桶中的链表，与前面的e=p.next()结合 p = e; } } //若在桶中找到key值，hash值与插入的元素相同的结点 if (e != null) { // existing mapping for key //旧值 V oldValue = e.value; //false或者旧值为空 if (!onlyIfAbsent || oldValue == null) //用新值换旧值 e.value = value; //访问后回调 afterNodeAccess(e); return oldValue; } } //结构性修改 ++modCount; //进行扩容 if (++size > threshold) resize(); //插入后回调 afterNodeInsertion(evict); return null; } Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { return new Node<>(hash, key, value, next); } -
8.当需要将一个map插入到集合中会调用putMapEntries()。若table数组为空，则需要根据tableSizeFor()修正扩容阈值；若table不为空且集合的元素个数超过，则调用resize()j进行扩容；最后循环遍历传入的集合，调用putVal()将元素插入到集合中
//将指定映射的所有映射关系复制到此映射中 public void putAll(Map<? extends K, ? extends V> m) { putMapEntries(m, true); } final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //获取传入的集合的大小 int s = m.size(); //map中的元素个数大于0 if (s > 0) { //第一次 node结点数组为空 if (table == null) { // pre-size， 100个装载因子为0.75 计算出最大容量 float ft = ((float)s / loadFactor) + 1.0F; int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //若计算出的需要的元素个数超过了阈值 则需要重新计算阈值 if (t > threshold) threshold = tableSizeFor(t); //table不为空 且传入的数据元素个数大于阈值的时候 重新计算 } else if (s > threshold) { //进行扩容 resize(); } //将map中的元素添加进去 for (Entry<? extends K, ? extends V> e : m.entrySet()) { //遍历entry 调用put进行存储 K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } } -
9.内部是通过getNode()来获取结点的。首先若table数组为空或者对应索引位置为空，表示没有在该位置插入过数据，直接返回null;若对应索引位置有数据，首先会判断头结点的key值和hash值是否很传入的key值和hash值相等，相等的话直接返回该结点，其时间复杂度为O(1)；若不相等则判断是否是红黑树，若是红黑树，则调用treeNode.getTreeNode()获取元素,其时间复杂度为O(logn)；若不是红黑树，表示当前时链表结构，那么遍历链表，获取元素。其时间复杂度为O(k)(k<8)
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //结点数组不为空且通过((n-1)*hash)计算得到对应的位置的数据存在 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //若桶的第一个结点的key值和hash值相等 那么结点就是第一个 无序做遍历操作 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //若第一个结点后面还有结点 判断是否是红黑树 若是的话调用getTreeNode()根据红黑树的规则获取 if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); //若是链表的话 遍历链表取得结点数据 然后判断key/hash来判断 do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; } -
10.内部是通过removeNode()来移除结点的。首先会根据key值通过hash算法计算出对应的索引位置，然后判断该索引位置是否为空，若为空，表示该位置没有插入过结点，则直接退出；若不为空，首先会判断第一个结点的key值和hash值相同，若相同，表示找到了该元素，让头结点后面的结点移动到头结点位置；若不是第一个元素，则判断是否是红黑树，若是红黑树则通过treeNode.getTreeNode()获取元素，获取到后通过treeNode.removeTreeNode()移除元素；若不是红黑树，那么表示当前时链表结构，则遍历链表获取元素，获取到元素后，然后元素的前结点的next指向元素的后结点。
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; } @Override public boolean remove(Object key, Object value) { return removeNode(hash(key), key, value, true, true) != null; } /** * * * @param hash hash for key key对应的hash * @param key the key key * @param value value * @param matchValue 是否需要匹配value * @param movable 如果为false，则在移除时不要移动其他节点 * @return the node, or null if none */ final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { Node<K,V>[] tab; Node<K,V> p; int n, index; //若结点数组不能为空且对应位置的结点有数据 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { Node<K,V> 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,V>)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,V>)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; } -
11.通过getNode()判断集合中是否包含有对应key的的元素，若有则返回true;若没有则返回false
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; } -
12.遍历整个数组的元素，判断是否有value相等的元素，若有则返回true；若没有则返回false
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; } -
13.返回一个Set对象，可通过 iterator()可以返回一个Iterator，之后可通过hasNext()判断是否还有元素没有被遍历，通过next获取元素的key值
public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return 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,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; // Android-changed: Detect changes to modCount early. for (int i = 0; (i < tab.length && modCount == mc); ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.key); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class KeyIterator extends HashIterator implements Iterator<K> { public final K next() { return nextNode().key; } } abstract class HashIterator { //下一个结点 Node<K,V> next; // next entry to return Node<K,V> current; // current entry int expectedModCount; // for fast-fail int index; // current slot //记录修改的次数 以及整个结点数组 且当前位置为0 HashIterator() { expectedModCount = modCount; Node<K,V>[] 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); } } /** * 判断下一个结点是否为null' * @return */ public final boolean hasNext() { return next != null; } /** * 获取下一个结点 * @return */ final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> 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() { Node<K,V> 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; } } -
14.返回一个Collection对象，可通过 iterator()可以返回一个Iterator，之后可通过hasNext()判断是否还有元素没有被遍历，通过next获取元素的value值
public Collection<V> values() { Collection<V> vs = values; if (vs == null) { vs = new Values(); values = vs; } return 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,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; // Android-changed: Detect changes to modCount early. for (int i = 0; (i < tab.length && modCount == mc); ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e.value); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class ValueIterator extends HashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } -
15.返回一个Collection对象，可通过 iterator()可以返回一个Iterator，之后可通过hasNext()判断是否还有元素没有被遍历，通过next获元素
//存放具体元素的集合 transient Set<Entry<K,V>> entrySet; public Set<Entry<K,V>> entrySet() { Set<Entry<K,V>> es; return (es = entrySet) == null ? (entrySet = new EntrySet()) : es; } final class EntrySet extends AbstractSet<Entry<K,V>> { public final int size() { return size; } public final void clear() { HashMap.this.clear(); } public final Iterator<Entry<K,V>> iterator() { return new EntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Entry)) return false; Entry<?,?> e = ( Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Entry) { Entry<?,?> e = (Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator< Entry<K,V>> spliterator() { return new EntrySpliterator<>( HashMap.this, 0, -1, 0, 0); } public final void forEach(Consumer<? super Entry<K,V>> action) { Node<K,V>[] tab; if (action == null) throw new NullPointerException(); if (size > 0 && (tab = table) != null) { int mc = modCount; // Android-changed: Detect changes to modCount early. for (int i = 0; (i < tab.length && modCount == mc); ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) action.accept(e); } if (modCount != mc) throw new ConcurrentModificationException(); } } } final class EntryIterator extends HashIterator implements Iterator<Entry<K,V>> { public final Entry<K,V> next() { return nextNode(); } } -
16.遍历整个数组，将其置为null
public void clear() { Node<K,V>[] tab; modCount++; if ((tab = table) != null && size > 0) { size = 0; for (int i = 0; i < tab.length; ++i) tab[i] = null; } } -
17.和put()一样是调用putVal()进行元素的插入操作，唯一的区别是，若调用put()插入元素时，若该元素在集合中存在，则覆盖value；若调用putIfAbsent()插入元素时，若元素在集合中存在，直接返回，不会覆盖value
public V putIfAbsent(K key, V value) { return putVal(hash(key), key, value, true, true); } -
18.根据key找到对应的元素，然后修改元素的value
@Override public boolean replace(K key, V oldValue, V newValue) { Node<K,V> e; V v; if ((e = ge不tNode(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,V> e; if ((e = getNode(hash(key), key)) != null) { V oldValue = e.value; e.value = value; afterNodeAccess(e); return oldValue; } return null; } -
19.当数组为空或者数组中元素的个数达到阈值后被调用，其扩容为当前容量的2倍，当扩容后需要将元素复制到新的数组中，这是需要重新计算hash值，那么只需要看新增的高位bit是1还是0，若是0的话，索引不变；若是1的话原索引+oldTap
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // if (oldCap > 0) { //集合已经在最大容量了 其阈值是Integer.MAX_VALUE if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; //容器的容量是原来的2次幂 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (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 < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> 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,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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; } -
20.将链表转换为红黑树.首先判断数组的长度是大于64，若不大于的话将进行扩容操作；若大于的话将进行对应桶中的链表转换为红黑树，并让结点前后相连。最后调用treeify()进行排序
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //若数组容量小于MIN_TREEIFY_CAPACITY，不进行转换而是进行resize操作 //若桶为空或者桶的数量小于64 那么只进行扩容操作 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); //若桶不为空或者数量大于64 且tab[index = (n - 1) & hash])对应位置有结点e else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; //通过do while取出结点数据 然后将其转换为TreeNode do { //将该node转换为TreeNode TreeNode<K,V> p = replacementTreeNode(e, null);//将Node转换为TreeNode 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);//重新排序形成红黑树 } } } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { return new TreeNode<>(p.hash, p.key, p.value, next); }
HashMap的实现思想
-
HashMap采用了数组+链表+红黑树的结构存储数据，首先将数组分为n份，每一份可以把它当作一个桶，然后以key为参数通过散列函数计算出的index，最后将元素插入到数组的index位置，但是散列函数有漏洞，不同的key值计算出的hash值可能会相同，那么这时候将相同位置的元素以链表的形式连接起来，随着链表个数的增多，其插入访问的时间复杂度增高，性能降低。为了解决这个问题引入的红黑树结构，当链表的个数超过8个时，将将链表转换为红黑树；当元素个数小于8个时又将红黑树转换为链表，这样将解决了同一个桶中随着元素的增多，其性能降低的问题。
* 首先当插入一个元素，会通过hash算法计算出一个hash值，然后通过hash&(n-1)计算出在数组table中的一个位置index * 若这个位置为空，表示在位置还没有插入过元素，那么直接构建一个Node放入到数组的table[index]中，其时间复杂度为O(1) * 若这个位置不为空，判断头结点是否就是需要插入的结点，若是的话，直接修改value * 若头结点不是要插入的元素，那么判断是否是红黑树，若是红黑树则直接以红黑树的形式插入元素，其时间复杂度为O(logn) * 若不是红黑树则表示当前时链表结构，则将元素插入链表的尾结点，其时间复杂度为O(k)(k<8)
扫一扫
43万+
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
