目录
🌟1、哈希表的相关概念
🌈 1.1 哈希表是怎么产生的？
哈希表来源于数组的随机访问特性。
关于数据的搜索问题，我们知道：如果是链表的查找，需要从头开始向后遍历到结束，复杂度是O(n)；如果是搜索树(平衡搜索树)的查找，则查找效率是O(log(n))；如果是数组，若已知要查找元素的索引，则查找元素为O(1)。因此我们可以发现，在知道待查找元素的索引这一条件下，使用数组这种数据结构来查找元素是十分高效的。因此受这一思想的启发，就产生了哈希表。也就得出了我们文中开头的第一句话：哈希表来源于数组的随机访问特性！
利用上面的
举个栗子🌰：现在有一组数据[9,5,4,6,1,7]，需要判断某个target目标值是否存在。
如果能够将元素的值和数组的索引建立联系，根据索引来查找元素，则事半功倍。数组中的最大值是9，因此我们创建一个最大索引为9的新的布尔数组，也就是新数组长度为10。
通过上述操作：将数组的具体数值转化为了新布尔数组的下标，此时要查找某个元素，在新数组中已经知道了该数组的索引下标，因此查找起来非常快。是典型的用空间换时间的思想。但是这样也有一个问题，就是如果我这个数组中的数据范围很分散，比如[10,100000,1000000000]这种，那我最少要创建一个1000000000+1大小长度的新数组，太不划算了。怎么能解决这个问题呢？哈希函数就出现了。
🌈 1.2 哈希函数的设计？
问题1：哈希函数是什么？
将任意数据类型的值转化为正整数，将转化后的正整数作为数组的下标。一般来说，哈希函数不需要我们自己设计，用已有的方案即可。一般哈希函数的设计遵循以下几个原则（1）一致性：对于两个相同的数字x1和x2，经过一个相同的哈希函数得到的值也一定相同。
（2）稳定性：对于一个数字x，不论什么时候用哈希函数计算得到的哈希值结果都不变。
（3）均匀性：对于不同的数字x和y，经过哈希函数得到的值尽可能分散。
问题2：怎么设计哈希函数呢？
（1）对 整型：取模运算：将原数组的值%n
✅ [10,20,30,40,50] % 7 = [3,6,2,5,1] -> 取n=7
❎ [10,20,30,40,50] % 8 = [2,4,6,0,2] -> 取n=8
对于n = 8这种情况，我们可以看见对于不同的两个数值10,50经过哈希函数计算后得到相同的值2，这种现象我们称为哈希碰撞（哈希碰撞理论上一定存在）。比较好的方式就是n取素数，这样能显著降低哈希碰撞的概率。
（2）对 字符串：业内关于字符串的哈希函数：MD3,MD4,MD5,SHA1,SHA256等。
🌈 1.3 哈希冲突/碰撞怎么解决？
解决哈希碰撞有两种方案。
（1）闭散列（线性探测法）
主要思想：当经过哈希函数计算得到的值发生冲突后，将冲突元素放在旁边空闲位置。 
总结：闭散列方案，好想好放，但是很难查询和删除元素。工程中很少使用。
（2）开散列（链地址法）-> 工程中普遍采用的方案
主要思想：这种方案由数组和链表两种数据结构组成。如果发生了元素重复，就让冲突的位置变为一个链表。
❓ 问题：以上两种方案虽然可以解决哈希碰撞，但是，当元素个数不断变多，哈希冲突的概率也会越来越大。比如在数组中，某个索引下的链表长度特别长，找一个元素相当于又要遍历链表，此时查找效率又从O(1)变为O(n)。此时的哈希碰撞又该怎么解决呢？
（1）针对整个数组扩容：扩容为原来的一倍。此时大概率原先冲突的元素再次哈希计算之后不会再冲突。(C++采用的方法)
（2）将长度过长的链表转化为BST/哈希表（JDK8的方法）也就是下面这张图的形式。
🌈 1.4 关于哈希函数的等概率查找问题
现有一组数据[38,25,74,63,52,48]，哈希函数设计为H(k) = k % 7。分别计算闭散列和开散列方案的平均成功查找长度。
🌈 1.5 怎么判断哈希函数是否冲撞严重？
我们前面说到哈希碰撞，有一个专业的名词叫做“负载因子”(factor)，用来描述哈希碰撞的严重程度的。一般来说，当满足以下条件时，我们认为碰撞严重。
根据上述公式我们可以得到如下结论：负载因子factor 越大，则保存的元素个数会越多，节省空间，但是冲突更严重。与之相反。JDK中的HashMap的factor默认是0.75，而在阿里的实验室论证中，在一般的商用系统中，factor为10是比较合适的设置。
🌟2、开散列哈希表的代码实现
在写代码之前我们要明确：开散列形式的哈希表是由数组和链表组成的。普通的数组中的元素是一个值，哈希表中数组的一个元素是一个链表。同时链表中的每一个节点存储的是一个键值对。
🌈 2.1 增加元素
函数描述：根据key值比较，如果key值已经存在，则更新value值即可；如果key值不存在，则头插到数组的相应索引位置。
/**
* put:新增或者修改元素：在当前哈希表中添加一对新元素，返回添加前的值
* @param key
* @param value
* @return 如果是新元素，则返回-1
*/
public int put(int key,int value){
//1、将该新增的值进行哈希函数计算在当前数组中的索引位置
int index = hashFun(key);
//2、在当前的索引位置判断该位置下的索引链表中是否存在该值:若存在，则只需要更细value即可
//遍历对应索引下的链表
for (Node x = data[index]; x != null; x=x.next) {
//说明该元素已存在
if(x.key == key){
//获取旧键值对中的值
int odValue = x.value;
//更新对应key下的value值即可
x.value = value;
return odValue;
}
}
//3、若不存在该key值，则说明该元素是第一次出现，将该元素头插到当前索引下的子链表中
//产生该节点
Node node = new Node(key,value);
//当前子链表的头部与新节点建立联系：data[index]是子链表的头部
node.next = data[index];
//此时链表的头部就是新节点
data[index] = node;
//更新元素个数
size++;
//判断当前哈希表是否需要扩容
if(size >= data.length * LOAD_FACTOR){
resize();
}
return -1;
} /**
* 返回给定值经过哈希函数计算后的在数组中的索引值
* @param i
* @return
*/
private int hashFun(int i) {
return i % M;
}🌈 2.2 扩容机制
函数描述：当数组中元素个数增大到默认容量时，就要进行扩容。这里我们将数组容量扩大到原来的2倍，将原数组的内容搬移到新数组中。
/**
* 扩容方法：一共三步
*/
private void resize() {
//1、创建一个新数组：大小为原数组的2倍
this.M = data.length << 1;
Node[] newData = new Node[data.length << 1];
//2、计算原数组中的每一个值经过新的哈希函数后得到的在新数组中的新索引值。
// 找数组中每个元素使用双层for循环：外层循环遍历原数组的每一个位置，内层元素则是数组每一个位置上的子链表的遍历
//数组中每一个位置
for (int i = 0; i < data.length; i++) {
//子链表的遍历
for (Node x = data[i]; x!= null;) {
//暂存该节点的下一个节点
Node next = x.next;
//将该节点头插到新数组的新索引处
//计算新索引
int newIndex = hashFun(x.key);
//头插到新数组
x.next = newData[newIndex];
newData[newIndex] = x;
//指向下一个节点
x = next;
}
}
//3、更新数组为新数组
data = newData;
}🌈 2.3 通过key值删除元素
函数描述：由于key的不重复性，所以删除元素都是通过key值删除通过value值删除可能会造成误删。
/**
* 通过key值删除指定值
* 如果通过value值删除，由于value值可能会重复，因此会误删。
* @param key
* @return
*/
public boolean removeByKey(int key){
//1、计算key值经过哈希函数后的索引
int index = hashFun(key);
//边界条件
if(data[index] == null){
return false;
}
//2、此时就是该索引位置上子链表的删除
//(1)如果该链表头结点就是待删除元素
if(data[index].key == key){
//更新子链表的头结点
data[index] = data[index].next;
size--;
return true;
}
//(2)不是头结点的链表删除:通过前驱节点删除
//当前子链表的头部作为前驱
Node prev = data[index];
//如果不到最后一个节点，就一直遍历
while (prev.next != null){
if(prev.next.key == key){
//找到待删除的节点，更改节点的指向
prev.next = prev.next.next;
//更新节点个数
size--;
return true;
}
}
//没有找到被删除的元素
return false;
}
🌈 2.4 判断是否含有key值
/**
* 判断当前hashMap中是否包含给定的key值
* @param key
* @return
*/
public boolean containsKey(int key){
//1、计算给定值的索引位置
int index = hashFun(key);
//2、遍历该位置索引下的子链表，判断该key值是否存在:data[index]表示子链表的头部
for (Node x = data[index]; x != null ; x=x.next) {
if(x.key == key){
return true;
}
}
return false;
}🌈 2.5 判断是否含有value值
/**
* 判断当前数组中是否含有指定的value值 -> 全表扫描
* 因为hash函数是根据key值计算索引的，所以上面判断是否包含key，则只需要在对应的索引位置下的子链表查找
* 但是value则要在整个数组的所有链表都遍历，也叫作全表扫描。
* @param value
* @return
*/
public boolean containsValue(int value){
//外层：数组中的每个元素都是一个链表
for (int i = 0; i < data.length; i++) {
//内层：遍历每个子链表的节点
for (Node x = data[i]; x != null ; x = x.next) {
if(x.value == value){
return true;
}
}
}
return false;
}🌈 完整代码实现
public class HashMapCodes {
/**
* 组成：数组和链表构成。普通的数组是每个位置保存一个值，HashMap则是每个位置保存一个链表
* 注意：这里的链表中的每个节点存储的是一个键值对。
*/
//定义可以存储链表的数组
private Node[] data;
//定义当前哈希表的有效元素个数
private int size;
//定义内部的Node节点
private static class Node{
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
//定义取模数：简单起见，让数组的取模数和数组元素个数一致
private int M;
//定义负载因子
private static final double LOAD_FACTOR = 0.75;
//构造方法
public HashMapCodes() {
this(16);
}
public HashMapCodes(int capacity) {
this.data = new Node[capacity];
this.M = capacity;
}
/**
* put:新增或者修改元素：在当前哈希表中添加一对新元素，返回添加前的值
* @param key
* @param value
* @return 如果是新元素，则返回-1
*/
public int put(int key,int value){
//1、将该新增的值进行哈希函数计算在当前数组中的索引位置
int index = hashFun(key);
//2、在当前的索引位置判断该位置下的索引链表中是否存在该值:若存在，则只需要更细value即可
//遍历对应索引下的链表
for (Node x = data[index]; x != null; x=x.next) {
//说明该元素已存在
if(x.key == key){
//获取旧键值对中的值
int odValue = x.value;
//更新对应key下的value值即可
x.value = value;
return odValue;
}
}
//3、若不存在该key值，则说明该元素是第一次出现，将该元素头插到当前索引下的子链表中
//产生该节点
Node node = new Node(key,value);
//当前子链表的头部与新节点建立联系：data[index]是子链表的头部
node.next = data[index];
//此时链表的头部就是新节点
data[index] = node;
//更新元素个数
size++;
//判断当前哈希表是否需要扩容
if(size >= data.length * LOAD_FACTOR){
resize();
}
return -1;
}
/**
* 扩容方法：一共三步
*/
private void resize() {
//1、创建一个新数组：大小为原数组的2倍
this.M = data.length << 1;
Node[] newData = new Node[data.length << 1];
//2、计算原数组中的每一个值经过新的哈希函数后得到的在新数组中的新索引值。
// 找数组中每个元素使用双层for循环：外层循环遍历原数组的每一个位置，内层元素则是数组每一个位置上的子链表的遍历
//数组中每一个位置
for (int i = 0; i < data.length; i++) {
//子链表的遍历
for (Node x = data[i]; x!= null;) {
//暂存该节点的下一个节点
Node next = x.next;
//将该节点头插到新数组的新索引处
//计算新索引
int newIndex = hashFun(x.key);
//头插到新数组
x.next = newData[newIndex];
newData[newIndex] = x;
//指向下一个节点
x = next;
}
}
//3、更新数组为新数组
data = newData;
}
/**
* 通过key值删除指定值
* 如果通过value值删除，由于value值可能会重复，因此会误删。
* @param key
* @return
*/
public boolean removeByKey(int key){
//1、计算key值经过哈希函数后的索引
int index = hashFun(key);
//边界条件
if(data[index] == null){
return false;
}
//2、此时就是该索引位置上子链表的删除
//(1)如果该链表头结点就是待删除元素
if(data[index].key == key){
//更新子链表的头结点
data[index] = data[index].next;
size--;
return true;
}
//(2)不是头结点的链表删除:通过前驱节点删除
//当前子链表的头部作为前驱
Node prev = data[index];
//如果不到最后一个节点，就一直遍历
while (prev.next != null){
if(prev.next.key == key){
//找到待删除的节点，更改节点的指向
prev.next = prev.next.next;
//更新节点个数
size--;
return true;
}
}
//没有找到被删除的元素
return false;
}
/**
* 判断当前hashMap中是否包含给定的key值
* @param key
* @return
*/
public boolean containsKey(int key){
//1、计算给定值的索引位置
int index = hashFun(key);
//2、遍历该位置索引下的子链表，判断该key值是否存在:data[index]表示子链表的头部
for (Node x = data[index]; x != null ; x=x.next) {
if(x.key == key){
return true;
}
}
return false;
}
/**
* 判断当前数组中是否含有指定的value值 -> 全表扫描
* 因为hash函数是根据key值计算索引的，所以上面判断是否包含key，则只需要在对应的索引位置下的子链表查找
* 但是value则要在整个数组的所有链表都遍历，也叫作全表扫描。
* @param value
* @return
*/
public boolean containsValue(int value){
//外层：数组中的每个元素都是一个链表
for (int i = 0; i < data.length; i++) {
//内层：遍历每个子链表的节点
for (Node x = data[i]; x != null ; x = x.next) {
if(x.value == value){
return true;
}
}
}
return false;
}
/**
* 返回给定值经过哈希函数计算后的在数组中的索引值
* @param i
* @return
*/
private int hashFun(int i) {
return i % M;
}
}
文章出处登录后可见！
