数据结构与算法，众妙之门，魅力无穷
---同行者联盟
哈希表
哈希表使用场景与详细介绍
需求：
“三分钟内，我要那个女生的全部资料”，这是我们在霸道总裁爱上我的电视剧中常听到的话，
维护一份学生人员资料信息，当输入人员学号时，要快速查到该学生的基本信息，越快越好，且不使用数据库，要节省内存
什么是哈希表：
“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表/哈希表。
哈希表的本质及其实现方法
哈希表本质就是数组，实现方法有两种
1、数组+链表
2、数组+红黑树
哈希表示意图：
数组+链表以及数组+红黑树两种实现形式的示意图
为什么不直接使用数组而是要使用哈希表：
hash表为了实现：通过某一个关键值（一个具体业务值）可以直接取到数据，达到和数组一样的随机访问效果。但是数组的关键值只能是下标，不具有任何业务意义，所以直接使用数组是不满足我们的需求的。那我们中间加一个函数去实现：关键值 --> 下标 --> 数据，这个就是hash函数。
哈希冲突是什么以及如何解决
哈希冲突：不同的输入数据在经过哈希函数计算后，产生了相同的哈希值。即k1 != k2,但H(k1) = H(k2),这种现象就是哈希冲突。
举个例子，比如哈希函数是: 哈希值 = 关键字 mod 10,那13和23就会产生哈希冲突，因为会映射到同一个地址上，就会产生哈希冲突
怎样解决：
F1: 开放寻址法
基本思想：当哈希冲突发生时，采用一定的规则在哈希表中寻找下一个可用的槽，直到找到一个空槽或者达到某个阈值为止；
对阈值的解释：
数组的长度为16，加载因子设为0.75，阈值就是总长度*加载因子的值，当已经插入的元素个数超过阈值时，需要对哈希表进行扩容操作。因为此时发生哈希冲突的概率会增大
如：
数据关键字：15 2 38 28 4 12
数组大小：13
哈希函数为 下标=关键字 mod 13
如下图，元素 15 已经占据了下标为 2 的位置，元素 2 本身也应该占据下标为 2 的位置，这时遇到哈希冲突，它就往下一个地址寻找空位。
如果遇到冲突，就往下一个地址寻找空位。新地址 = 原始位置+i(i是查找次数)
F2: 链接法
（又叫拉链法， HashMap底层就是这样处理的）
基本思想: 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
如：数据关键字：19,14,23,01,68,20,84,27,55,11,10,79
哈希表长度：13
哈希函数为：哈希值 = key % 13
解决需求：来实现哈希表的创建及其使用
1、哈希表的创建
创建学生类
/**
创建学生类
**/
class Student {
public int id;
public String name;
public int age;
public String addr;
public Student next;
public Student(int id, String name, int age, String addr) {
this.id = id;
this.name = name;
this.age = age;
this.addr = addr;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
", age=" + age +
", addr='" + addr + '\'' +
'}';
}
}创建学生链表
/**
创建学生链表
**/
class StudentList {
public Student head;
public void addStudent(Student student) {
if (head == null) {
head = student;
return;
}
Student cur = head;
while (true) {
if (cur.next == null) {
break;
}
cur = cur.next;
}
cur.next = student;
}
}创建学生哈希表，用于管理链表
class StudentHashTable {
StudentList[] studentLists;
int maxSize;
public StudentHashTable(int maxSize) {
studentLists = new StudentList[maxSize];
this.maxSize = maxSize;
//初始化链表数组
for (int i = 0; i < maxSize; i++) {
studentLists[i] = new StudentList();
}
}
}2、哈希表实现学生信息的插入操作（不考虑学生重复插入）
// 实现添加学生的方法
public void addStudent(Student student) {
// 根据哈希函数，获取学生应该对应的下标
int stuId = student.id % maxSize;
// 将学生插入到该条链表中
studentLists[stuId].addStudent(student);
}3、哈希表实现学生信息的遍历输出
学生链表类中实现遍历学生的方法
public void showStudent(int index) {
if (head == null) {
System.out.println("下标"+index+"下，链表为空，没有学生信息可以输出");
return;
}
System.out.println("下标"+index+"下的学生信息分别是：");
Student cur = head;
System.out.println(cur.toString());
while (true) {
if (cur.next == null) {
break;
}
cur = cur.next;
System.out.println(cur.toString());
}
}哈希表中实现遍历每一个索引
/**
* 遍历学生
**/
public void showStudent() {
for (int i = 0; i < studentLists.length; i++) {
studentLists[i].showStudent(i);
}
}4、哈希表实现根据对应学号快速找到对应学生信息
学生链表类中实现通过学号获取学生信息的方法
public void getStudentById(int id) {
if (head == null) {
System.out.println("不存在学号为" + id+ "的学生");
return;
}
// 辅助节点初始化为头节点，即数组下标位置所代表的学生
Student cur = head;
// 遍历链表
while (true) {
if(cur.id == id){
System.out.println("学号为"+id+"的同学信息为"+cur.toString());
break;
}
if (cur.next == null) {
System.out.println("不存在学号为" + id+ "的学生");
break;
}
cur = cur.next;
}
}哈希表中实现的通过学号获取学生信息的方法
public void getStudentById(int id) {
// 根据学号找到对应的数组下标
int index = id % maxSize;
studentLists[index].getStudentById(id);
}测试实例
public static void main(String[] args) {
StudentHashTable studentHashTable = new StudnetHashTable(3);
for (int i = 1; i <= 6; i++) {
Student stu = new Student(i, "zs" + i, 20 + i, "aaa" + i);
studentHashTable.addStudent(stu);
}
studentHashTable.showStudent();
studentHashTable.getStudentById(5);
}
