面试 百年老陈醋HashMap源码级分析

首先先来理解一下最基础的，数组，链表，步步引出Hashmap

1.数组的优势/劣势

优点：查询速度快，数组都是有下标的，我们可以通过inde快速访问到数据
缺点：内存申请完后，大小固定了，在插入元素的时候，就插不进去了，就需要重新建立一个更大的数组，将原来数据全部复制过去，再插入数据，不太灵活，比较耗费性能。

2.链表的优势/劣势

优势：新插入一个元素，不用管理空间，直接头插或尾插
缺点：查询一个元素，只能从头head元素一个一个查，删除某个元素也是非常费力气的。

3.有没有一种方式整合两种数据结构的优势？

有 散列表
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

4.散列表有什么特点？

1. 访问速度很快

由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找，可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任何操作时，速度都很快。

2. 需要额外的空间

首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。

这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快些。

3. 无序

散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素，散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快，但是对于有序访问却没有办法应对。

4. 可能会产生碰撞

没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决方案不一定一样。

5.什么是哈希？

核心理论：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出。
这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。

Hash的特点：
1.从hash值不可以反向推导出原始的数据
2.输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的值
3.哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
4.hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。
根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。
这一现象就是我们所说的“抽屉原理”

下面是我写的两篇文章，相信读完后你会懂的更多

哈希，哈希函数，散列表，你知多少？

JAVA1.8 HashMap源码,句句注释，如果这样都看不懂HashMap源码，那你就真没救了