HashMap在项目里面经常用到，使用的时候一般都是这样写
HashMap<String,String> hashMap = new HashMap<>();
hashMap.put("name","chen");
得到一个HashMap后往里面存数据，但对没看过HashMap源码的同学对HashMap的数据存储还是不太了解的，下面将从JDK1.7开始讲解HashMap。
JDK1.7 HashMap
讲解源码之前，我们先分析下，HashMap是一个key-value的容器，那在存储的时候，其实可以把key-value组成一个对象，存到一个定义好的数组里面。
但是现在有个问题，假如要存数据，这时候就要遍历数组找到对应的key，当存相同key时，要对value进行覆盖，运气好的话很快就找到，但也有可能遍历完所有才能找到，假设没找到就存入刚才的数据，这样效率就很差。当取数据时候，最差情况也是遍历完数组才取到，有可能还取不到。所以用数组的结构来存储，效率都很差。
优化的方案就是：对key进行hash操作，得到一个Int类型的hash值，并且把这个Int值作为数组小标，把整个对象存入小标为Int的数组里面，提高了效率。但是还有一个问题，就是去到的hash值的大小超过了数组的大小，导致无法存入，所以就要对hash进行取模操作，得到一个在数组大小内的hash值，就解决了超出数组大小问题。
但是又有一个问题，当不同key的hash后取模，得到相同的数组下标，此时按照之前的逻辑是进行覆盖的，但是现在key是不相同的，hash值相同，也就是哈希冲突，怎么解决呢？HashMap采用了链表的结构来存储hash值相同且key值不同的对象，不会导致覆盖。
1.7 HashMap 数据结构
原理基本都讲清楚了，接下来看看HashMap源码是怎么样的
HashMap<String,String> hashMap = new HashMap<>();
一般调用了空参构造，发现空参构造调用了双参构造，分别是
1、DEFAULT_INITIAL_CAPACITY 初始化的容积
2、DEFAULT_LOAD_FACTOR 负载因子
//默认初始化化容量,即16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量，即2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认装载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//HashMap内部的存储结构是一个数组，此处数组为空，即没有初始化之前的状态
static final Entry<?,?>[] EMPTY_TABLE = {};
//空的存储实体
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//实际存储的key-value键值对的个数
transient int size;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold
int threshold;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationException
transient int modCount;
//默认的threshold值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
所以初始化容积为16（二进制1左移四位 【0001 0000】 = 16），负载因子为0.75。
//装载因子取0.75，容量取16，构造HashMap
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//通过初始容量和状态因子构造HashMap
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)//参数有效性检查
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//参数有效性检查
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//参数有效性检查
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}
初始化时先检查参数的有效性，如果都有效得到刚才的负载因子和阈值（初始化容积）。可以看到初始化过程，并没有把数组创建出来，只是得到了一个空的数组。
put操作
初始化完后，来看看put操作。
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);//分配数组空间
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);//调用value的回调函数，其实这个函数也为空实现
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}
分析：
- 1、假如table也就是刚才初始化的数组是否为空，（刚初始化为空）为空则inflate（充气）给数组分配空间，大小为刚才定义好的阈值。
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1
table = new Entry[capacity];//分配空间
initHashSeedAsNeeded(capacity);//选择合适的Hash因子
}
roundUpToPowerOf2这个函数是对数组大小进行2的整数次幂取值，假如size=15，取值为16；假如size=17，取值为32。因为初始值为16，所以取值为16。所以分配给数组的大小为16，并且重新计算得到阈值。当HashMap里面所有元素超过阈值，需要动态扩容，后面会讲到。
- 2、当存入的key为null时
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry( 0, null, value, 0);
return null;
}
取到数组上的元素，也就是一个链表，遍历判断链表上每个元素的key是否为空，如果找到key为空的，则新值覆盖旧值，并把旧值返回；假如找不到链表上key为空的元素，则addEntry插入链表中。addEntry后面会讲到。
- 3、假如key不为空，那么对key进行hash操作，得到一个hash值，因为这个hash值可能过大，无法当做数组下标，所以对hash值进行取模操作，得到一个符合数组下标的索引。
//用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {//这里针对String优化了Hash函数，是否使用新的Hash函数和Hash因子有关
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
hashSeed在JVM初始化时候设定，假如不设定为0，那么h ^= k.hashCode();中0与key的hashCode做或运算还是其本身，现在就得到一个hash值，但是为了让存储位置更均匀的分布，后面继续对这个hash值进行位运算，称为二次哈希（扰动函数），这样不容易产生哈希碰撞。
//返回数组下标
static int indexFor(int h, int length) {
return h & (length-1);
}
得到二次hash值后，接下来要去到数组小标，默认数组大小是16，那么16-1的二进制表示是（0000 1111），与hash值进行与运算，因为0000 1111前面的数值都为0，后四位均为1，所以现在只考虑后面四位，也就是得到hash值后面四位的大小。这样就是对hash值进行取模且得到数组下标。
- 4、获取下标后，取到当前下标的数组元素，遍历当前链表中的所有数据，假如hash值与找到节点的hash值相等，并且key值也相等，那么就把当前的key-value对象替换，返回旧对象的value值；假如都没找到，那么就插入这个数据addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容，新容量为旧容量的2倍
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);//扩容后重新计算插入的位置下标
}
//把元素放入HashMap的桶的对应位置
createEntry(hash, key, value, bucketIndex);
}
//创建元素
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex]; //获取待插入位置元素
table[bucketIndex] = new Entry<>(hash, key, value, e);//这里执行链接操作，使得新插入的元素指向原有元素。
//这保证了新插入的元素总是在链表的头
size++;//元素个数+1
}
插入数据前，要先判断是否扩容。首先判断HashMap中元素的个数超过阈值（默认12）并且找到的当前数组上元素不为空，则需要动态扩容；假如元素个数超过阈值，但是当前数组元素上的为空，则不需要扩容。扩不扩容都会去创建元素。创建元素时，先去到当前数组位置上的元素，再把要插入的元素插到数值这个元素前面，也就是头插法，后插入的数据排在链表的头部。
1.7 HashMap put操作
扩容
//按新的容量扩容Hash表
void resize(int newCapacity) {
Entry[] oldTable = table;//老的数据
int oldCapacity = oldTable.length;//获取老的容量值
if (oldCapacity == MAXIMUM_CAPACITY) {//老的容量值已经到了最大容量值
threshold = Integer.MAX_VALUE;//修改扩容阀值
return;
}
//新的结构
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));//将老的表中的数据拷贝到新的结构中
table = newTable;//修改HashMap的底层数组
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阀值
}
达到扩容条件后，传进2被数组大小的值。首先判断扩容后的数组是否达到最大容量值，如果是则修改扩容阈值，不扩容直接返回；假如正常扩容，先创建一个新的数组，再把旧数组里面的数据全部拷贝到新数组中，并用新数组替换旧数组，最后修改阈值。
//将老的表中的数据拷贝到新的结构中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//容量
for (Entry<K,V> e : table) { //遍历所有桶
while(null != e) { //遍历桶中所有元素（是一个链表）
Entry<K,V> next = e.next;
if (rehash) {//如果是重新Hash，则需要重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//定位Hash桶
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入，总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
}
拷贝的时候，先遍历每一个桶，再遍历桶上的每一个元素，重新计算hash值后，再次取到数组索引的位置并插入。
get操作
//获取key值为key的元素值
public V get(Object key) {
if (key == null)//如果Key值为空，则获取对应的值，这里也可以看到，HashMap允许null的key，其内部针对null的key有特殊的逻辑
return getForNullKey();
Entry<K,V> entry = getEntry(key);//获取实体
return null == entry ? null : entry.getValue();//判断是否为空，不为空，则获取对应的值
}
//获取key为null的实体
private V getForNullKey() {
if (size == 0) {//如果元素个数为0，则直接返回null
return null;
}
//key为null的元素存储在table的第0个位置
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)//判断是否为null
return e.value;//返回其值
}
return null;
}
分析：
- 1、假如搜索的key值为空，则走getForNullKey。先判断元素个数是否为0，为0直接返回null；否则遍历数组中第一个桶的所有元素，找到key为null的元素，如果有则返回，如果没有则返回null。
- 2、如果key不为null，走getEntry(key)
//获取键值为key的元素
final Entry<K,V> getEntry(Object key) {
if (size == 0) {//元素个数为0
return null;//直接返回null
}
int hash = (key == null) ? 0 : hash(key);//获取key的Hash值
for (Entry<K,V> e = table[indexFor(hash, table.length)];//根据key和表的长度，定位到Hash桶
e != null;
e = e.next) {//进行遍历
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))//判断Hash值和对应的key，合适则返回值
return e;
}
return null;
}
同样先判断元素个数是否为0；之后取到hash值再根据hash值取模得到数组的下标索引，找到当前的桶，跟put操作取下标相同。取到桶后，遍历桶上的所有元素，找对应key和对应hash值相同的元素，找到则返回当前元素，找不到则返回null。
- 3、找到元素后，判断value值是否为空，为空则返回null，否则返回本身。
总结
1、JDK1.7 HashMap数据结构的是怎么样的？
答：数组加链表
2、怎么插入数据？
答：头插法，在链表的前面插入
3、HashMap怎么预防和解决哈希冲突？
答：预防采用了二次哈希（扰动函数）；解决采用拉链法（链表结构）
4、HashMap默认容量？可以是15吗？
答：16。不能是15，为了 -1得到二进制位上全是1.
5、数组是什么时候创建的？
答：在第一次put操作的时候
JDK1.8 HashMap
相对于1.7，数据结构发生了变化。在链表达到一定长度的时候，会转化为红黑树。所以JDK1.8 HashMap的数据结构是：数组+链表+树
1.8 HashMap 数据结构
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
当初始化HashMap时候，只是对负载因子赋值，值还是0.75。从注释可以看到，数组的默认容量还是16，和1.7一样。
put操作
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
先得到一个hash值，这里还是和1.7一样，为了扰乱哈希，减少碰撞；之后调用putVal。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //1
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //2
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //3
e = p;
else if (p instanceof TreeNode) //4
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //5
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //6
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)))) //7
break;
p = e;
}
}
//8
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//9
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
分析：
- 1、当数组为空或者数组长度为0的时候，对数组进行初始化，并得到数组的长度。resize代码比较长，耐心看完
final Node<K,V>[] resize() {
//1
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//2
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
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;
//3
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;
//4
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //5
Node<K,V> e;
if ((e = oldTab[j]) != null) { //6
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;
}
1.1 初始化的时候来到第1，oldTab为null数组，oldCap、oldThr、newCap、newThr均为0。
1.2 因为均为0，所以走到了第3，把默认值赋值给新的容积和阈值，并根据容积创建数组，最后把新数组赋值给table，后续扩容可以用到。
1.3 因为是初始化，所以oldTab为null，直接跳过里面的判断，最终返回创建的数组。
所以JDK1.8 HashMap创建数组的时候也是在put操作。
-
2、刚才已经得到了一个数组，n是数组的长度，i = (n - 1) & hash与1.7相同，都是根据hash值取模得到数组下标，得到p桶。并判断是否为null，如果为空，则直接新创建一个节点，插入进去。
-
3、假如桶上数据不为空，p是tab[i]即桶上的第一个节点，判断哈希值是否相同并且key值是否相同，若都相等则取到当前元素进行后续操作。
-
4、刚才有说到当链表达到一定长度后，会转化为红黑树，这里就是判断是不是树类型，如果是则在树中进行查找。假如树种找到了相同的key和hash值，则进行替换，找不到则添加一个树节点。
-
5、既然当前桶上存在元素又不是树类型，则是个链表类型。
-
6、遍历链表，往下一个节点开始找，假如下一个节点为null，则表示到链表尾，在链表尾部新增一个节点并且插入在尾部，之后再判断是否此时链表是否需要树化，之后再跳出循环，去到第8。1.7中采用头插法，而1.8采用尾插法。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//1
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) { //2
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null); //3
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); //4
}
}
6.1 假如达到树化条件，但是如果链表中长度还没达到MIN_TREEIFY_CAPACITY（64），则进行扩容，不树化。
6.2 根据索引去到链表头，第3将一个链表节点转化为树节点，而do-while中其实还没树化，只是讲一个单向链表转化为双向链表。
6.3 得到双向链表后进行树化，链表头作为根节点，之后根据已经存在的hash值跟节点上的hash值比较大小，找到它的方向。
-
7、假如在遍历的过程中找到了相同key和相同hash值的节点，则break后去到第8。
-
8、取到e节点后去判断，onlyIfAbsent默认为false，所以会把旧值直接替换，并返回旧值。
-
9、在1.7中是先扩容在添加元素，而1.8中是先添加完元素在扩容。添加完元素后判断元素个数是否达到阈值来进行扩容。
9.1 当第二次扩容后（resize代码），存在了table并赋值给oldTab，resize代码中第2点，oldCap大于0的，判断数组长度是否超过最大容积，如果是则把阈值调到最大，不进行扩容；否则newCap = oldCap << 1，把老的数组左移以为，也就是扩大两倍，扩大后是否小于最大容积，并且老的数组的长度是不是大于等于初始化长度（16）后，老的阈值oldThr左移一位得到newThr，即是老数组阈值的两倍。
9.2 得到两倍容积后，创建一个新的数组，并把新的数组赋值给table。
9.3 第4点，现在oldTab不为空了，第5点是对数组进行遍历，而第6点是对数组上的链表进行遍历。
9.4 当j = 0时，取到老数组中第一个桶e，加入桶上存在元素，则先把老数组的元素上置空，在判断是不是最后一个节点，如果是则桶上只有一个元素，重新计算出索引，直接在新数组当前索引中存入次节点。
9.5 接下来判断是不是树节点，如果是的话，用树节点专门拆分树的方法进行老数组转移新数组。
9.6 最后只剩一种情况，就是链表的情况，其中do-while是把列表创建出来，一个高位的列表一个地位的列表，并且e.hash & oldCap判断是否等于0，如果是则该元素处于低位，如果不是则处于高位。之后把低位列表赋值到新的数组中，高位列表赋值在新数组低位列表后面。相对于1.7的扩容，1.8少了一次hash的操作。
总结
-
1.7和1.8数据结构有什么不同？
答：1.7只有数组加链表，1.8引入了红黑树 -
往链表上插入数据的方式有什么不同？
答：1.7用了头插法，1.8用了尾插法 -
扩容后存储位置的计算方式？
答：1.7扩容完进行一个hash操作，再得出索引；1.8则元素的hash值是与老数组长度进行与运算，如果等于0的是在低位，如果不等于0则是在高位 -
HashMap什么时候会把链表转化为红黑树？
答：链表长度大于8的时候会去判断是否树化，判断条件是数组元素大小是否达到了64的树化条件。如果链表长度大于8，但是数组中元素个数少于64，则不进行树化
网友评论