目录
1.哈希表的起源？
2.哈希函数（hashcode())
3.哈希冲突
4.负载因子
5.基于开散列的哈希表代码实现
1.哈希表的起源？
首先我们来分析一下从一组数据中查找某个元素的效率：
如果顺序查找，则需要从头开始查找，时间复杂度为O（N）；即使用刚学的BST进行查找，时间复杂度也为O（log N);
那么有没有一种方法使查找效率更高呢？
如下面这个例子：
给定一组数据：【6，5，2，4，7】，求该组数据中是否有元素4
我们的一种思路是这样的：
该组数据中最大的元素为7，那我们就创建一个长度为8的boolean数组temp；原数据中的数字为多少，我们就令temp数组中索引下标为这个数的元素置为true；
（如原数据中不是有数字6吗，就令temp[6] = true)
最后，查找哪个元素是否存在就直接返回temp数组中该索引下标位置即可
(如本题中查找数字4，直接返回temp[4]即可）
public static void main(String[] args) {
// 【6，5，2，4，7】
int[] a = {6,5,2,4,7};
boolean[] temp = new boolean[8];
for (int i = 0; i < a.length; i++) {
temp[a[i]] = true;
}
// 查找4
System.out.println(temp[4]);
// 查找1
System.out.println(temp[1]);
}
输出结果：
这道题的解法就是巧妙借助了数组的索引下标，直接返回某元素对应的索引下标值即可；
于是我们想到构造一种存储结构，使元素的存储位置与它的关键码之间能够建立一一映射的关系，这样依据存储位置直接便查找到了该元素。
所以我们有了哈希表这种结构，而哈希表实则就是由数组衍生而来的，借助数组的随机访问性，由索引下标即可快速查找，使得哈希表的查找操作时间复杂度可为O（1），大大提高了效率同时也可以看到，其实哈希表是用空间换时间所以哈希表由键值对构成，key和value，如若查找某值，直接返回key值对应的value值即可
2.哈希函数（hashcode())
（1）对于元素分散的数据，如 【1，100，239，3】，如果还是直接元素数据对应索引下标必然会带来很多空间浪费，或者诸如其他非数字类型，故而，有了哈希函数的产生。
（2）哈希函数就是将任意数据类型进行函数运算后使之变为整型，也就是在原数据和数据索引之间建立映射关系。
（3）哈希函数最常用的运算之一就是模运算,对于负数，通常是取绝对值再进行模运算
（4）哈希函数设计原则：
使运算结果分布尽可能均匀（一般是对一个素数取模）稳定性，相同的Key值要保证运算结果为唯一的一个值
3.哈希冲突
（1）哈希冲突
有时候不同的key值，进行哈希运算后，可能得到一个相同的值，这就发生冲突了，也就是哈希冲突
（2）哈希冲突的解决措施
闭散列（开放地址法）：当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去
那么下一个空位置如何找呢？
线性探测法：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止二次探测法：左右跳跃式探测
【注意】对于线性探测法，若哈希冲突严重，则其实查找某元素时仍然相当于是遍历操作，效果并不好
开散列：又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
如下图：
闭散列相当于化大集合为小集合，到小集合里去查找；
而如果哈希冲突严重时，就意味着小集合的搜索性能其实也时不佳的，这个时候我们可以继续优化：
方法一：适当进行哈希表扩容方法二：将小集合的链表优化为一个新的哈希表方法三：将小集合的链表优化为一个红黑树（JDK8的HashMap就采用这种方法，当整个哈希表的长度>64并且链表长度>6，就将链表转化为红黑树
4.负载因子
负载因子越大，说明填入表中元素越多，发生冲突可能性越大！负载因子越小，说明填入表中元素越少，发生冲突可能性越小JDK8中，HashMap中的负载因子为0.75
5.基于开散列的哈希表代码实现
以下实现的哈希表，为基于开散列的哈希表，每个哈希桶由单链表连接起来，当负载因子大于预定默认范围时，我们暂且选择扩容操作来减缓哈希冲突
实际就是下图这种表现形式，数组的每个位置存储的其实是链表的头节点，每一个节点由key值，value值，和下一个节点引用next组成
（1）插入键值对——put操作
（在插入时要考虑是否需要扩容，故而这里还有一个扩容方法——grow操作）
先判断是否已经存储过该key值，去该key值哈希运算后对应的索引位置里的链表里查找；
如果已经存储过，只需修改value值；
如果未存储过，则需创建新节点，并头插入对应索引位置的链表中去；
public int put(int key, int value) {
int index = hashCode(key);
// 先查看是否已经存储过该key值，如果存储过，只需更新val值
for (Node cur = data[index];cur != null;cur = cur.next) {
if(cur.key == key){
int old = cur.val;
cur.val = value;
return old;
}
}
// 此时，说明无该key值，则我们需要新建节点插入
Node newNode = new Node(key,value,data[index]);
data[index] = newNode;
size ++;
// 查看是否需要扩容
if(data.length * LOAD_FACTOR <= size){
grow();
}
return newNode.val;
}
// 扩容操作,默认扩大为2倍
private void grow() {
Node[] newData = new Node[data.length * 2];
// 随即将取模数k更改
k = newData.length - 1;
// 遍历原数组，将原数组重新哈希函数后搬入扩容后的新数组
for (int i = 0; i < data.length; i++) {
// 将不为空的节点处的所有元素搬迁
if(data[i] != null){
for(Node cur = data[i];cur != null;){
Node next = cur.next;
int newIndex = hashCode(cur.key);
// 将元素头插入新数组newIndex处
cur.next = newData[newIndex];
data[newIndex] = cur;
// 然后继续搬迁下一个元素
cur = next;
}
}else{
continue;
}
}
// 最后将newData赋值给原来的data
data = newData;
}
（2）删除（根据给定的key值删除）——remove操作
找到key值对应的哈希位置，从该位置的链表里删除，实则就是链表的删除节点操作；
如果找不到该键值对，抛出异常即可；
public int remove(int key) {
int index = hashCode(key);
// 先判断头节点是否就是该元素
Node head = data[index];
if (head.key == key) {
int v = head.val;
data[index] = head.next;
head = head.next = null;
size--;
return v;
} else {
// 此时说明不是头节点
Node pre = head;
while (pre.next != null) {
if (pre.next.key == key) {
Node cur = pre.next;
int v = cur.val;
pre.next = cur.next;
cur.next = cur = null;
size--;
return v;
}
}
// 如果都没找到，说明无该键值对
throw new NoSuchElementException("cannot find key!!!");
}
}
(3)查找某key值是否存在——containsKey操作
同上，也是先计算key值对应的哈希值，哈希值就是存储位置的索引下标，然后根据索引下标去链表里找；
public boolean containsKey(int key) {
int k = hashCode(key);
Node head = data[k];
while (head != null) {
if (head.key == key) {
return true;
}
head = head.next;
}
return false;
}
（4）查找某value值是否存在——containsVal操作
查找val值，因为无法得知其key值对应的哈希值，也就无法直接访问该节点，所以，这里，效率低，只能逐个访问查找
public boolean containsVal(int value) {
// 遍历每一个链表
for (int i = 0; i < data.length; i++) {
for (Node x = data[i]; x != null; x = x.next) {
if (x.val == value) {
return true;
}
}
}
return false;
}
最后给上完整代码，并进行Test
import java.util.NoSuchElementException;
public class My_Hashmap {
// node节点
private class Node {
private int key;
private int val;
private Node next;
public Node() {
this.val = 0;
this.key = 0;
}
public Node(int key, int val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
// size存储空间元素个数
private int size;
// 默认空间大小为10
private static final int DEFAULT_CAPACITY = 10;
// 默认负载因子的大小
private static final double LOAD_FACTOR = 0.75;
// 实际存储的数组
private Node[] data;
// 取模数，这里定义是因为扩容后取模数也会变
private int k;
// 无参构造、有参构造
public My_Hashmap() {
this(DEFAULT_CAPACITY);
}
public My_Hashmap(int length) {
data = new Node[length];
k = length - 1;
}
// 哈希函数，简单进行一个取模运算
private int hashCode(int key) {
return Math.abs(key) % k;
}
public int put(int key, int value) {
int index = hashCode(key);
// 先查看是否已经存储过该key值，如果存储过，只需更新val值
for (Node cur = data[index];cur != null;cur = cur.next) {
if(cur.key == key){
int old = cur.val;
cur.val = value;
return old;
}
}
// 此时，说明无该key值，则我们需要新建节点插入
Node newNode = new Node(key,value,data[index]);
data[index] = newNode;
size ++;
// 查看是否需要扩容
if(data.length * LOAD_FACTOR <= size){
grow();
}
return newNode.val;
}
public int remove(int key) {
int index = hashCode(key);
// 先判断头节点是否就是该元素
Node head = data[index];
if (head.key == key) {
int v = head.val;
data[index] = head.next;
head = head.next = null;
size--;
return v;
} else {
// 此时说明不是头节点
Node pre = head;
while (pre.next != null) {
if (pre.next.key == key) {
Node cur = pre.next;
int v = cur.val;
pre.next = cur.next;
cur.next = cur = null;
size--;
return v;
}
}
// 如果都没找到，说明无该键值对
throw new NoSuchElementException("cannot find key!!!");
}
}
public boolean containsKey(int key) {
int k = hashCode(key);
Node head = data[k];
while (head != null) {
if (head.key == key) {
return true;
}
head = head.next;
}
return false;
}
public boolean containsVal(int value) {
// 遍历每一个链表
for (int i = 0; i < data.length; i++) {
for (Node x = data[i]; x != null; x = x.next) {
if (x.val == value) {
return true;
}
}
}
return false;
}
// 扩容操作,默认扩大为2倍
private void grow() {
Node[] newData = new Node[data.length * 2];
// 随即将取模数k更改
k = newData.length - 1;
// 遍历原数组，将原数组重新哈希函数后搬入扩容后的新数组
for (int i = 0; i < data.length; i++) {
// 将不为空的节点处的所有元素搬迁
if(data[i] != null){
for(Node cur = data[i];cur != null;){
Node next = cur.next;
int newIndex = hashCode(cur.key);
// 将元素头插入新数组newIndex处
cur.next = newData[newIndex];
data[newIndex] = cur;
// 然后继续搬迁下一个元素
cur = next;
}
}else{
continue;
}
}
// 最后将newData赋值给原来的data
data = newData;
}
}
对增加、删除、查找进行Test：
public class Test {
public static void main(String[] args) {
My_Hashmap map = new My_Hashmap(15);
map.put(3,6);
map.put(4,7);
map.put(5,8);
map.put(4,9);
boolean a = map.containsKey(3);
boolean b = map.containsKey(8);
boolean c = map.containsVal(9);
boolean d = map.containsVal(7);
map.remove(3);
System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(d);
boolean e = map.containsKey(3);
System.out.println(e);
}
}
测试结果：
可见，我们的方法操作是成功的，并且如若重复插入同一个key值，只会更新val值，而不会说会有两个key值相同的节点。
【注意】jdk8中，当哈希冲突严重时，会将链表改为红黑树，以保持查找效率的平衡性
