本文主要是介绍大一学生分享哈希表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数据结构与算法，众妙之门，魅力无穷
---同行者联盟
哈希表
哈希表使用场景与详细介绍
需求：
“三分钟内，我要那个女生的全部资料”，这是我们在霸道总裁爱上我的电视剧中常听到的话，
维护一份学生人员资料信息，当输入人员学号时，要快速查到该学生的基本信息，越快越好，且不使用数据库，要节省内存
什么是哈希表：
“散列表（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;}@Overridepublic 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);
}这篇关于大一学生分享哈希表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
