HashMap学习，只说重点

HashMap底层：

HashMap

jdk1.8之前为数组+链表，链表主要解决哈希冲突；
jdk1.8及之后为数组+链表+红黑树
- 当某一链表长度大于8并且数组长度大于64时，该链表上所有数据转为红黑树结构进行存储；
- 当红黑树结点小于6时，转为链表结构。

注意：数组长度比较小，尽量避开红黑树结构，红黑树结构需要进行旋转来保存平衡，进行插入删除时会降低效率。

HashMap主要成员变量：
Node<K,V>[] table(数组)
final float loadFactor:(负载因子):默认为0.75
int threshold(边界值):数组容量×负载因子
int modCount(操作除数)
int size(元素数量)

HashMap特点：

数据存储无序；
key和value可以为null，但key为null只能存在一个；
key是唯一的，是底层数据结构决定的。

HashMap实例化：

当不指定HashMap数组初始值时：
- jdk1.8之前则直接在构造器中创建一个长度为16的Entry[] table的数组来进行存储；
- jdk1.8及之后则需要在第一次put元素的时候进行判断后创建一个长度为16的Node[] table的数组来进行存储。
当指定HashMap数组初始值时：
- 并不直接创建指定值大小的数组，而是创建大于指定值的最小2的倍数。
  例如：当初始值为7时，7→8；初始值为10时，10→16。

HashMap添加/更新元素：
索引计算：index=hashcode & （length-1）
先计算key的索引index，当table[index]不会空时，会比较两个key的hash值，如果hash值不相等，则直接采用链表添加（大于8时红黑树）；当hash值相等时，则会比较两个key是否在逻辑上(key1==key2 || key1.equals(key2)相等；相等时，则替换结点的value进行更新操作；不相等时，进行添加。
注意：jdk1.8之前链表进行头插，jdk1.8及之后进行尾插。

jdk1.7尾插

jdk1.8尾插

HashMap扩容：

当存放元素数量（size）大于边界值（threshold）时，进行扩容；
当数组大小小于64，且链表长度大于8时，进行扩容。

调用resize()方法进行扩容，扩容为原来的2倍。

newCap = oldCap << 1     //左移一位

jdk1.8之前对所有元素进行遍历，然后重新进行计算hash值在进行添加到新数组中；
jdk1.8及之后对所有元素进行遍历，计算元素的rehash(e.hash & oldCap)值，当等于0时，存入原来index位置上，等于1时，存放到index+oldCap的索引上

HashMap常见面试题：

问题：Hash值计算？为什么要进行无符号右移与运算？

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

底层采用key的hashCode()的方法的值结合数组长度进行无符号位右移（>>>）、按位异或（∧）、按位与（&）计算出索引。（位运算效率较高）
当当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

问题：当两个对象的hashCode相等时会怎么样？如何解决？
当两个对象的hashCode相等时，即产生哈希碰撞。
产生哈希碰撞后，比较两个对象的key值，若key值相同，则替换value值，否则，链接到链表。
jdk8之前使用链表解决哈希冲突，jdk8后使用链表+红黑树解决哈希冲突。

问题：为什么负载因子0.75不建议修改？
表示HashMap的疏密程度。
loadFactor太大导致查找效率低，太小导致数组利用率低。

注意：根据阿里巴巴手册指导，建议在创建对象时给HashMap添加容量大小，以减少HashMap的扩容。
size=（已知存储的元素/负载因子）+1.0F；
加1向上取整，以保证更大容量，减少扩容次数。

看到这了，就留下个赞再走吧。

最后编辑于：2020.08.25 23:13:36