1. 什么是HashMap？
image.png
1.1 map的定义
首先你要知道什么是map，map就是用于存储键值对（<key,value>）的集合类，也可以说是一组键值对的映射。
1.2 Map的特点
1.没有重复的 key（一方面，key用set保存，所以key必须是唯一，无序的；另一方面，map的取值基本上是通过key来获取value，如果有两个相同的key，计算机将不知道到底获取哪个对应值；这时候有可能会问，那为什么我编程时候可以用put（）方法传入两个key值相同的键值对？那是因为源码中，传入key值相同的键值对，将作为覆盖处理）
2.每个 key 只能对应一个 value, 多个 key 可以对应一个 value（这就是映射的概念，最经典的例子就是射箭，一排射手，一排箭靶，一个射手只能射中一个箭靶，而每个箭靶可能被不同射手射中。这里每个射手只有一根箭，不存在三箭齐发还都中靶这种骚操作。将射手和射中的靶子连线，这根线加射手加靶子就是一个映射）
3.key,value 都可以是任何引用类型（包括 null）的数据（只能是引用类型）
1.3 HashMap
HashMap在JDK1.8中是基于（数组+链表）+红黑树的一个Map容器
2. HashMap解读
2.1 静态属性（默认值）
/**
* 如果没有给容量初始化值得话，就用这个作为初始化值，16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* Map容量最大值
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 负载因子，用来判断扩容量的
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当Node的长度达到8的时候就转换成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 当Node的长度被remove到6的时候就从红黑树转成链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 容器可以树化的最小容量。
*（否则，如果bin中的节点太多，则会调整表的大小。）
* 应至少为4 * TREEIFY_THRESHOLD，以避免调整
* 大小和树化阈值之间的冲突。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
2.2 HashMap实例的属性
/**
* HashMap底层数据结构是一个Node数组，可以是红黑树树，也可以是链表，默认是链表
*/
transient Node<K,V>[] table;
/**
* Map中存储元素的数量
*/
transient int size;
/**
* 要调整大小的下一个大小值（容量*加载因子）
* 此外，如果尚未分配表数组，则此字段保存初始数组容量
* put一个元素进Map的时候，都会判断添加后的size和这个
* threshold比较，如果大于了这个值，就扩容。
*/
int threshold;
/**
* 哈希表的加载因子
* 这个就是为了计算出threshold的，下面会说
*/
final float loadFactor;
2.3 HashMap初始化
HashMap总共定义了四个构造函数。
2.3.1 // 传入初始化容量，和负载因子进行初始化
// 传入初始化容量，和负载因子
public HashMap(int initialCapacity, float loadFactor) {
// 如果初始化容量小于0，则抛出异常。
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);
}
刚刚上面看到了第一次计算容量用的是tableSizeFor(); 这个方法，我们现在来看一下这个方法。
/**
* 返回的大小一定是2的幂
* 意思就是，你传的初始化容量大小，取比这个数最大的2的n次方的值
* 打比方：
* 传1那么容量就是2的0次方，那么容量就是1
* 传入的是2那么就是2的1次方，那么容量就是2
* 传入的是3那么就是2的2次方，那么容量就是4
* 传入的是4那么就是2的3次方，那么容量就是8
*/
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;
}
2.3.2 传一个初始化容量大小初始化
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
2.3.3 默认构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2.3.4 传一个Map进行初始化
刚刚介绍的三种构造函数可以看出来，都没有给HashMap进行初始化，但是这个构造函数，会给出初始化。
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
// 将传入的Map的值都添加进目前初始化的HashMap
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
// 传入的Map大小
int s = m.size();
if (s > 0) {
if (table == null) {
// 如果table是空的就计算容量，容量大小就是 (size/loadFactor) + 1.0F
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果容量大于了扩容标准，就计算新的扩容的标准大小。
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
// 如果size大于了扩容标准，调用进行resize()扩容
resize();
// 循环put进去
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);
}
}
}
从上面可以看到主要是两个方法，resize(); 扩容方法，和putVal(); put一个元素到容器的方法，我们继续来看看putVal();方法
JDK1.7是通过hash%cap得出存储数据位置，就是hash值模上数组length得出位置
JDK1.8是通过容量大小与key值进行hash的算法在开始的时候只会对低位进行计算，虽然容量的2进制高位一开始都是0，但是key的2进制高位通常是有值的，因此先在hash方法中将key的hashCode右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。先是jdk1.8的图解
image.png
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果tab是空的，初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果该位置没有值，直接new一个节点，存储
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果该位置的有值，并且就是自己的话，就覆盖一下value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果该节点是树的话，就用树的put方法
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 长度到了8就转成红黑树
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)
// 添加完了以后++size大于了阈值就扩容
resize();
afterNodeInsertion(evict);
return null;
}
小小写了一下，发现写这玩意太废头发了，所以还是自己理解一下，借鉴一下网上大佬例子好了。
JDK1.7 https://blog.csdn.net/xiaokang123456kao/article/details/77503784
JDK1.8 https://www.cnblogs.com/xiaoxi/p/7233201.html
网友评论