什么是哈希表？
哈希表就是借鉴了数组的随机访问能力，利用数组的随机访问的高效性产生了哈希表
哈希函数其实就是把任意的数据类型转成数组的索引
e.g. char --> int? ? ? ?char - 'a' = int
????????大的int类型转为小的int类型 一般都是取模操作，根据数论摸一个素数
????????String --> int? ? ? ? ? ?字符串的内部就是字符数组，因此还是按照字符转为int的方式
????????其他类型 -- > int? ? ? 因为任意的数据类型都有toString方法，所以可以先转为String --> int
什么是哈希冲突？
不同的两个key值，经过哈希函数的运算得到了两个相同的索引。
在理论上，数学中的任意函数f(x),两个不相同的x都一定有可能会映射到相同的y，哈希冲突无法避免！
怎们解决哈希冲突？
1.闭散列：
当发生冲突时，找到冲突位置的旁边是否存在空闲位置，直到找到第一个空闲位置放入元素。
好存难查更难删，工程中很少使用此方案
图解:?
?
查找：
要查找120时，先120 %101 = 19,发现19这个位置存放的不是120，则继续向后找，直到找到120位置，若一直向后遍历走完整个数组还没找到，则这个元素不存在。
若整个哈希表冲突非常严重，此时查找一个元素从O(1)=>遍历数组O(n)。所以一般不用
2.开散列：
?
查找任意元素:
如果取模后若冲突，遍历链表。 在最坏情况下，开散列方案遍历链表，相较于闭散列方案查找次数会大大降低，元素删除，查找，链表的对应操作，相较于闭散列方案来说容易很多。
若遇见最最最坏的情况，若当前哈希表中某个位置，比如图中19这个位置冲突非常严重，恰好每个元素取模后都是19，某个数组对应的链表的长度过长，查找效率就会降低。面对这种情况一般有两种解决方案：
1.针对整个数组进行扩容(比如现在数组长度101，扩容到202)就会由原先%101 => %202，很多原来同一个链表上的元素均分到其他新的位置，降低哈希冲突。 e.g. C++中的STL的Map
2.将这个冲突严重的链表再次变为新的哈希表/二分搜索树(将O(n) => O(logn))不用整张哈希表进行处理，只处理冲突严重的链表。 e.g. JDK的方案
?第二种方法如图：
?
练习题：
已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h (key) = key%7计算散列地址，并散列存储在散列表A[...6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C）
????????A.1.5???????????????????????????????? B.1.7???????????????????????????????? C.2.0 ????????????????????????????????D.2.3
?
解：
成功查找的平均查找长度为：?当前表中所有元素的查找次数 / 表中有效的元素个数 --> 12/6 =2
?拓展：开散列时：
?
小结：
对于一般场景下的哈希函数的设计:
一般来说不用自己写，用现成的即可。MD5,MD4,MD3 SHA1,SHA256 MD5—般用在字符串计算hash值的特点:
1.定长。无论输入的数据有多长，得到的MD5值长度固定。
2.分散。如果输入的数据稍有偏差，得到的MD5值相差很大(冲突概率非常低，工程领域忽略不计)
3.不可逆。根据字符串计算md5很容易，想通过得到的md5还原字符串到底是啥非常难(基本不可能)
4.根据相同的数据计算的md5值稳定的，不会发生变化。 稳定性是所有哈希函数都要满足的特点
MD5用途：
1.作为hash运算
⒉.用于加密
3.对比文件内容(内容稍有修改，得到的md5值天差地别)。上传下载。
?自己设计一个开散列代码：
完整代码：
import java.util.NoSuchElementException;
/**
* @Author qiqichongya
* @Date 2022/8/14 19:20
* @PackageName:HashMap
* @ClassName: HashMapTest
* @Description: 自己设计一个 开散列
*/
public class MyHashMap {
// 有效节点数
private int size;
// 实际存储元素的 Node 数组
private Node[] hashTable;
// 取模数
private int M;
// 负载因子
private static final double LOAD_FACTOR = 0.75;
public MyHashMap() {
this(16);
}
public MyHashMap(int init) {
this.hashTable = new Node[init];
this.M = init;
}
/**
* 对key求哈希值
*
* @param key
* @return
*/
public int hash(int key) {
return Math.abs(key) % M;
}
/**
* 将一对
*
* @param key
* @param val
*/
public int put(int key, int val) {
// 1.先取模找到key对应的Node数组中的索引下标。
int index = hash(key);
// 2.遍历对应索引下标的链表，查询key是否已经存在
for (Node x = hashTable[index]; x != null; x = x.next) {
if (x.key == key) {
int oldValue = x.value;
x.value = val;
return oldValue;
}
}
// 此时说明该键值对是一个新的，需要新增节点头插到哈希表中
// 也就是说 此时 Node x == null --> hashTable[index] == null --> 还没有放值。
Node node = new Node(key, val);
node.next = hashTable[index];
hashTable[index] = node;
size++;
if (size >= hashTable.length * LOAD_FACTOR) {
expansion();
}
return val;
}
/**
* 数组扩容为原来的二倍 和 搬移数据
*/
private void expansion() {
// 1.产生一个新的数组并且长度是原来长度的二倍。
Node[] newTable = new Node[hashTable.length << 1];
// 2.进行元素的搬移操作，此时取模应该为新的数组长度
this.M = newTable.length;
for (int i = 0; i < hashTable.length; i++) {
for (Node x = hashTable[i]; x != null; ) {
// 求出 x 在新的数组中的索引下标
int index = hash(x.key);
Node next = x.next;
// 在新数组中进行头插
x.next = newTable[index];
newTable[index] = x;
// 继续搬移剩下的链表节点。
x = next;
}
}
}
/**
* 判断key是否存在
*
* @param key
* @return
*/
public boolean containsKey(int key) {
int index = hash(key);
for (Node x = hashTable[index]; x != null; x = x.next) {
if (x.key == key) {
return true;
}
}
return false;
}
/**
* 判断value是否存在
*
* @param value
* @return
*/
public boolean containsValue(int value) {
// 全表扫描
for (int i = 0; i < hashTable.length; i++) {
for (Node x = hashTable[i]; x != null; x = x.next) {
if (x.value == value) {
return true;
}
}
}
return false;
}
/**
* 在哈希表删除指定键值对（key,value）
*
* @param key
* @param value
* @return
*/
public boolean remove(int key, int value) {
// 先拿到当前 key 在数组中的索引
int index = hash(key);
// 判断头节点是不是待删除节点
Node head = hashTable[index];
if (head.key == key && head.value == value) {
// 此时头节点就是待删除节点
hashTable[index] = head.next;
size--;
return true;
}
// 此时头节点不是待删除节点
Node prev = hashTable[index];
while (prev.next != null) {
if (prev.next.key == key && prev.next.value == value) {
// 此时当前节点是待删除节点的前驱节点
Node current = prev.next;
prev.next = current.next;
size--;
return true;
} else {
prev = prev.next;
}
}
// 哈希表中没有这个节点
throw new NoSuchElementException("no such node!remove error");
}
}
class Node {
// 对key进行hash运算
int key;
int value;
// 下一个节点的地址
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}查找：
/**
* 判断key是否存在
*
* @param key
* @return
*/
public boolean containsKey(int key) {
int index = hash(key);
for (Node x = hashTable[index]; x != null; x = x.next) {
if (x.key == key) {
return true;
}
}
return false;
}
/**
* 判断value是否存在
*
* @param value
* @return
*/
public boolean containsValue(int value) {
// 全表扫描
for (int i = 0; i < hashTable.length; i++) {
for (Node x = hashTable[i]; x != null; x = x.next) {
if (x.value == value) {
return true;
}
}
}
return false;
}哈希表删除指定键值对：
/**
* 在哈希表删除指定键值对（key,value）
*
* @param key
* @param value
* @return
*/
public boolean remove(int key, int value) {
// 先拿到当前 key 在数组中的索引
int index = hash(key);
// 判断头节点是不是待删除节点
Node head = hashTable[index];
if (head.key == key && head.value == value) {
// 此时头节点就是待删除节点
hashTable[index] = head.next;
size--;
return true;
}
// 此时头节点不是待删除节点
Node prev = hashTable[index];
while (prev.next != null) {
if (prev.next.key == key && prev.next.value == value) {
// 此时当前节点是待删除节点的前驱节点
Node current = prev.next;
prev.next = current.next;
size--;
return true;
} else {
prev = prev.next;
}
}
// 哈希表中没有这个节点
throw new NoSuchElementException("no such node!remove error");
}