HashMap的底层原理

参考链接

hashmap的底层原理 https://zhuanlan.zhihu.com/p/79507868
解决hash冲突的理解 https://blog.csdn.net/qq_41864321/article/details/93920730

HashMap的原理

HashMap 其实是一个数组+(链表或红黑树)的数据结构

如果两个不同对象的hashCode相同，这种现象称为hash冲突。
所以本质上hashmap下的链表和红黑树下除了首结点其他就是hash冲突的键值对 也就是hashcode是一样的 hashmap解决hash冲突 使用的方法为**链地址法 ** 具体看下面内容

1、它的结点 里面有 Key Value 还有指向下一个结点的引用

static class Node<K,V> implements Map.Entry<K,V> {
   final int hash;
   final K key;
   V value;
   Node<K,V> next;

2、结构图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

数组用来构成链表或者红黑树的个数 (数组的长度也被称为初始容量大小 默认为16)数组中的每个元素用来存储一个链表或者一棵红黑树

3、插入一个键值对进行的过程

1）首先对这个键值对 的键进行hash函数 获取hashcode值然后hashcode % 数组长度(初始扩容大小) 得到存储该键值对的链表或红黑树在数组中的索引位置

小言：hashcode方法使用native修饰，是一个本地方法 所谓本地方法就是非java代码，这个代码通常用c或c++写成，在java中可以去调用它。
调用这个方法会生成一个int型的整数，我们叫它哈希码，哈希码和调用它的**对象地址 **和 内容有关.

哈希码的特点：
对于同一个对象如果没有被修改（使用equals比较返回true）那么无论何时它的hashcode值都是相同的
对于两个对象如果他们的equals返回false,那么他们的hashcode值也有可能相等

2）
a.如果数组该索引位置为空 则直接放进去
b.如果数组中已有结点元素 调用当前插入键值对和该结点元素的equals方法 默认是比较两个结点对象的地址 可以自定义equals方法进行比较。如果比较相同 则直接修改这个结点元素 如果不相同，则把当前插入键值对 插入 该结点元素下的链表

3）因为链表查询慢 修改快 而 红黑树(平衡二叉树的一种) 在查询速度比链表快
所以当链表的元素个数达到8的时候就用红黑树存储代替链表存储

4、HashMap中的两个重要参数

HashMap中有两个重要的参数：**初始容量大小(默认16)和加载因子(默认0.75) **，初始容量大小是创建时给数组分配的容量大小，默认值为16，用数组容量大小乘以加载因子得到一个值，一旦数组中存储的元素个数超过该值就会调用rehash方法将数组容量增加到原来的两倍，专业术语叫做扩容.在做扩容的时候会生成一个新的数组，原来的所有数据需要重新计算哈希码值重新分配到新的数组，所以扩容的操作非常消耗性能.

创建HashMap时我们可以通过合理的设置初始容量大小来达到尽量少的扩容的目的。加载因子也可以设置，但是除非特殊情况不建议设置.

面试的问题？

1、数组的扩容和缩容操作

扩容

当数组插入元素的个数刚好等于数组的长度 这时候将数组元素扩容成原来的两倍
代码层面上就是新建一样类型并且容量是原来两倍的的数组 ，将老数组的原来长度的元素全部赋值给新数组 然后将老数组的变量 指向 新数组

缩容

如果自己写的栈底层是由数组构成的 pop元素的时候 将元素删除设为NULL防止对象游离
如果删除后的数组太大，就将它的长度减半
检测条件是栈大小是否小于数组的四分之一
所以栈永远不会溢出，使用率也永远不会低于四分之一(除非栈为空，数组大小为1)

2、为什么负载因子为0.75 默认初始容量为16

负载因子与扩容有关系

比如默认初始容量大小为16 如果有元素>= 默认容量大小*负载因子 就扩容为原来的两倍
如果负载因子为1 那么元素要填满16个才扩容 hash冲突多了 红黑树存储的高度高了 复杂了 查询效率低了 也就是牺牲时间换空间
如果负载因子为0.5 当元素填满8个就扩容 hash冲突少了 红黑树存储的高度低了 查询效率高了 牺牲空间换时间 所以负载因子我为0.75 是对空间和时间的中和
**负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。 **

​ 树的高度越低 查询效率越高 如果用递归写的树，每迭代一层 栈的深度就加一 栈的深度是有限的数组元素填的越多 hash冲突就越多

​ 默认初始容量大小为16?由数学公式和试验出来的 可以减少扩容的几率和次数 但具体的数量量设置适当的初始容量大小可以提高时间的效率

3、hash冲突

​ 因为不同的键值对可能会产生相同的hashcode值 所以不同内容的元素结点产生了相同的hashcode如果两个不同对象的hashCode相同，这种现象称为hash冲突。

4、如何解决hash冲突

1、开放定址法

​ 就是一个冲突了就再换一个hashcode 直到不冲突这种方法的意思是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi 将相应元素存入其中

线性探测再散列

当发生冲突的时候，顺序的查看下一个单元

二次(平方)探测再散列

当发生冲突的时候，在表的左右进行跳跃式探测伪随机探测再散列

伪随机探测再散列

建立一个伪随机数发生器，并给一个随机数作为起点

再hash法

这种方式是同时构造多个哈希函数，当产生冲突时，计算另一个哈希函数的值。这种方法不易产生聚集，但增加了计算时间。

2、链地址法(拉链法)

将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

**hashmap就是用此方法解决冲突的。 **

3、建立一个公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

5、解决hash冲突的方法的优缺点

开放散列（open hashing）/ 拉链法（针对桶链结构）
也就是一个数组元素只能存一个结点链表或结点红黑树

优点：在总数频繁变动的时候可以节省开销，避免了动态调整；记录存储在节点里，动态分布，避免了指针的开销删除时候比较方便
缺点：因为存储是动态的，所以在查询的时候跳转需要更多的时间的开销在key-value可以预知，以及没有后续增改操作时候，封闭散列性能优于开放散列不容易序列化

封闭散列（closed hashing）/ 开放定址法
也就是一个数组元素只能存一个结点

优点：容易序列化如果可以预知数据总数，可以创建完美哈希数列
缺点：存储的记录数目不能超过桶组数，在交互时候会非常麻烦使用探测序列，计算时间成本过高删除的时候比较麻烦