学习交流群：774338859 （QQ）
宇鹏老师联系方式：1332893423（QQ）

HashMap的特点

存储双值 key value
Map
以key —> value的形式存储数据
并且Key是不重复的，key可以为null，元素的存储位置由key决定。
也就是可以通过key去寻找key-value的位置。
从而得到value的值。
适合做查找工作。

Cloneable 可以使用clone
Serializable 可以被序列化
Map.Entry 可以存储key-value具体数值。
Iterator 迭代器 只能从前往后进行遍历

HashMap 哈希算法

如何计算key-value结构的存储位置

先取出key的hashCode，然后对HashCode进行扰动处理，然后将扰动处理后的HashCode和tablelength -1 进行
按位与 —-》 index 这个index就是key-Value结构存储的下标。
3.哈希冲突
当多个key对应同一个数组下标。
h & (length-1) length 是 2的幂
h % length —》 index
15 % 8 = 7
23 % 8 = 7
31 % 8 = 7 哈希冲突

解决哈希冲突

的方法，HashMap使用哪种方法
1.7 数组+链表的结构 — 链地址法
1.8 数组+链表的结构 当一个链表上节点大于8个时 改用数组+红黑树 — 链地址法
遍历链表的时间复杂度O（n）
红黑树 查找的时间复杂度（log2N）

除了链地址法外，你还了解哪些解决哈希冲突的方法

5.HashMap的时间复杂度
get方法的时间负责度
通过key计算除index 遍历链表
O（1）
答：时间复杂度近似于O（1），由于哈希冲突存在所以不一定能够达到O(1).


扰动处理

为什么hashcode要进行扰动处理
（1）扰动处理 ： 降低hashcode的 重复率，降低index的重复率
h1 & (length-1) = 8
h2 & (length-1) = 8

h1’ & (length-1) =
h2’ & (length-1) =

和下标%的作用

为什么不直接采用经过hashCode（）处理的哈希码 作为 存储数组table的下标位置？
保证index一定时小于数组长度。防止数组下标访问越界。

为什么hashmap的容量要保持2的幂


为了用 & (length-1) 代替 % length 。

为什么用按位与代替取余


因为位运算的计算效率高于 算数运算。

HashMap中如果添加重复key会怎样


新添加进来的key对应的newvalue代替之前老的value。

如何判断添加了重复的key


（1）先判断添加的key是否为空，如果为null在零号下标对应的节点处寻找key为null的节点。
（2）先判断hashcode 在判断 引用地址是否相同 最后判断equals
先比较hashcode 如果hashcode 不同，那么一定key不相同。如果hashcode 相同这两个key有可能是相同的key
然偶我们再去比较引用地址和equals

加载因子

如果自己指定HashMap的初始容量和加载因子，那么容量的大小，和加载因子的大小对HashMap有什么影响
初始容量：如果我们指定不是2的幂，源码中有函数能够保证将最终数组容量改变到2的幂。
向上取整找最近的2的幂。
初始容量越小，越容易发生哈希冲突。
加载因子 :越大 。对扩容时机有影响。
加载因子越大扩容的时机越晚，哈希冲突的几率越大，空间利用率越大。
加载因子越小，越大扩容的时机越早，哈希冲突的几率越小，空间利用率越小。

扩容

为什么HashMap需要扩容
不是因为没有足够存储空间。
扩容之后要重新计算每一个节点对应的index，哈希冲突概率降低。