目录
一、什么是散列表?
散列表也叫做哈希表（Hash Table），是一种提供的键（Key）和值（Value）的映射关系的数据结构。只要我们给出一个key值就可以快速高效的查找到她所匹配的Value，时间复杂度趋近于 O(1)。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
这就是一个散列表，我们可以通过学号快速找到对应的同学。
二、散列表的解刨
首先我们要开始研究散列表的操作我们必须弄清楚哈希函数是什么。
1、哈希函数是什么？
散列表的底层是一个数组，但是数组的访问都是根据下标来访问的，但是我们的散列表的Key大多数都不是一个int类型，因此这时候就需要我们的利用哈希函数来当做一个“中转站”，通过某种方式进行Key值和数组下标之间的转换。
在Java语言中以及大多数面向对象编程的语言中，每个对象都有一个属于自己的hashcode，这个hashcode就是区别不同对象的一个重要标识，他们的hashcode都是一个整型变量。因此转换下标来也显得很简单了，就是按照数组的长度进行取模运算。
Index = HashCode(Key) % Array.length
我们通过代码调试不难发现，我们的字符串key 就是通过hashCode的方式插入到了我们数组str的4下标 。
到了这里我们需要思考一个问题也就是
1.1hashcode和equals的区别？
hashcode就是查找一个大概 但是equals就很具体。就比如我们想在字典中查询一个词语名字叫做元素，首先我们hashcode就相当于查到了一个元，但是第一个字为元的有很多比如元宵，元旦等等，因此我们的equals就继续查找查到一个具体的。
所以我们的出结论 ：
1、当两个对象的hashcode一样时，他们两个的equals不一定一样。
2、当两个对象的equals一样时，他们的hashcode一定一样。
2、哈希冲突
在我们在散列表进行插入操作是我们会有一种情况（底层数组长度为10）
当我们在插入一个Key为5的元素时，插入成功。但是第二次我们想插入Key为15的值通过计算我们应该插入到下标为5的位置，但是我们下标5已经有Key了，这时候就会变得很麻烦，我们吧这种情况称为哈希冲突。
哈希冲突是无法避免的，既然不能避免。所以我们就要想办法来解决。
避免哈希冲突的方法有很多种，但是我们今天就着重来研究两种方法 ：开放寻址发和哈希桶 。
3、开放寻址法
开发寻址法的原理很简单，就是当Key相同时，我们可以另想办法，直接寻找下一个空位置即可。
在Java中，ThreadLocal所使用的就是开放寻址法
4、HashMap（哈希桶）
哈希桶这个方法很重要，在Java集合中HashMap就是实现了哈希桶。因此接下来大多数为源码的解读和解刨。
哈希桶又叫链表存储，顾名思义也就是当Key相同时我们只需以链表形式在数组对应的下标地下存储即可。
（1）、HashMap的特点
1、他是存储 key – value 类型结构。
2、数据类型不限制通过哈希函数 key 的 hashcode 值进行存储数据。
3、可以存储null值。
4、他存储是无序的。
5、因为是链式存储外加数组存储因此存储起来很慢，但是查询很快。
6、它是线程不安全的。
（2）、HashMap的内部属性
因为hashMap存储特点具有链式结构因此每一个结点都具有一个Key值，一个Val值，一个next值来存储下一个结点 。
在JDK8中HashMap的存储是有数组 + 链表 + 红黑树组成。
基本属性：
结点构造方法：
（3）、HashMap的构造方法
HashMap具有一个有参的构造方法和一个无参的构造方法。
a、无参的构造方法
因此我们可以得出一个结论： 无参构造时我们HashMap容量为16，并且负载因子为0.75。
b、有参构造方法 
因此我们可以得出一个结论：当我们传入一个参数时，HashMap内部方法会经过加工吧我们传入的参数变成里的最近的二次幂数。就比如我们传入一个25，实际上我们的HashMap大小为32（1<< 5）。我们传入一个1000 ,实际上我们的HashMap的大小为1024（1 << 11）。
（4）、Hash（）方法的解析
准备工作做好了之后我们就要开始实现写操作了，写操作在JDK称为Entry。
可以发现我们写操作需要 在putVal的方法中实现，我们不难发现我们还需要传入key的hash，因此我们来看看hash方法：
hash方法解析：
首先我们会发现，
第一、为什么我们不利用hashcode直接求出key对应的index呢？
第二、为什么我们的key求出了hashcode还要异或无符号右移十六位？
我们不难发现当h ^ h >>> 16 之后我们可以吧高区与低区的二进制特征混合到低区。
然后接下来我们计算出来的hashcode的值要放在hashmap中的数组槽位计算，其计算公式为
（n – 1） & hash
假设我们数组的槽位为16的话那么槽位的计算过程为
因此我们不难发现，假如刚刚我们不做移位异或运算，那么我们的槽位将会丢失对应高区特征，也许我们丢失了对饮的高区特征，我们的hashcode依旧可以计算出不同的槽位来，但是当两个数字的hashcode很接近时，高区只要一点点差异就可能导致一次哈希碰撞。
因此也更好解释了为什么要用异或运算，正是因为异或运算才使得我们更好的找到了对饮的高低区特征，我们使用 & 运算 或者 | 运算反而体现不出来这些东西。
通过上面的解析也恰好说明了为什么我们每次一次槽位必须是 2 ^ n。
因为只有2 ^ n时 在当他 – 1之后他后面的位都会从零变成了1，也正因此方便了 hashmap数组槽中的 & 运算，但是要是是一个奇数的话 hashcode 参加 & 运算将会被很多位的 0 屏蔽，这对于hashmap来讲简直是一种灾难。
HashMap当中运用了很多精巧的位运算操作，这对于提高性能有很大帮助，更多的，很多的优化点，最终目的还是为了让哈希后的结果更均匀的分部，减少哈希碰撞，提升 hashmap 的运行效率。
注 ：参考至博客 ： HashMap位运算你可知一二 – 知乎 (zhihu.com)
（5）、putVal（）方法解析
（6）、resize（）方法解析
resize（）也就是所谓的扩容函数，在putVal操作中我们可以看出当初始化哈希桶的时候我们用到了resize()，在结点个数超过临界值的时候我们也会利用resize()进行扩容。
这一步只是扩容机制，值得注意的是当我们扩容完成之后我们还需要吧所有元素放到对应的新扩容的cap中，然后返回cap即可。
三、HashBuck个人代码实现
我自己也实现了一个比较简单的HashBuck，我的HashBuck的底层也为数组，只不过我水平有些，有些局限性，只能存储数字元素，也没有利用到Hashcode。
也就仅供参考吧！
public class Buck {
//哈希桶的底层为一个数组
static class Node{
public int key;
public int val;
public Node next;//假如有相同的key 那么就链式存储
public Node(int key,int val){
this.key = key;
this.val = val;
}
}//构建结点
public Node []arr;
public int usedSize;//记录当前存储的元素
public static final float DEFAULT_LOAD_FACTOR = 0.75F;//默认的负载因子为0.75
public Buck(){
arr = new Node[10];
usedSize = 0;
}
/**
* 存储key val
* @param key
* @param val
*/
public void put(int key,int val){
Node node = new Node(key,val);
int index = key % arr.length;
Node cur = arr[index];//去遍历链表直到找到key值
while(cur != null){
if(cur.key == key){
//找到相同的话替换相应的val值即可
cur.val = val;
return;
}
cur = cur.next;
}
//利用头插法插入
cur.next = arr[index];
arr[index] = cur;
usedSize++;
if(loadFactor() >= DEFAULT_LOAD_FACTOR){
//假如大于负载因子 扩容
}
}
private float loadFactor() {
return usedSize*1.0f / arr.length;
}//计算负载因子
/**
* 哈希表的扩容需要重新哈希
* 1.我们需要遍历数组的每一个元素上面的每一个链表
* 2.然后将链表重新哈希 也就是key % newArr.length
* 3.进行头插法
*/
private void grow(){
Node[] newArr = new Node[arr.length * 2];
for(int i = 0 ; i < arr.length; i++){
Node cur = arr[i];
while(cur != null){
//这边需要存储cur.next
Node curNext = cur.next;
int index = cur.key % newArr.length;
cur.next = newArr[index];
newArr[index] = cur;
cur = curNext;
}
}
this.arr = newArr;
}
/**
* 通过key值 获取val 值
* @param key
* @return
*/
public int get(int key){
int index = key % arr.length;
Node cur = arr[index];
while(cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}
}
四、总结
本篇文章主要重点解释了关于HashMap的部分实现源码，就如Hash()，putVal()，resize()。对于HashMap还具有很多源码，感兴趣的读者可以去JDK8中直接阅读Hashmap类的源码。
散列表是一个很神奇的东西，可以说是数组 + 链表 + 树的一种大杂烩 ，他因为自身查找速度快，在算法中应用很普遍，是一种非常重要的数据结构。
也感谢大家阅读此文章，本篇文章也借鉴了《漫画算法》一些内容，假如此文章有哪个地方有错，也希望大家在评论区指出。谢谢！