# 4. 哈希表（Hash Table) \> \*\*一般哈希表都是用来快速判断一个元素是否出现集合里。\*\* \> \> 例如要查询一个名字是否在这所学校里。 \> \> 要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。 \> \> 我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。 \> \> 将学生姓名映射到哈希表上就涉及到了\*\*hash function ，也就是哈希函数\*\*。 #### 一. 定义 \*\*散列表（Hash table，也叫哈希表）\*\*，是根据键（Key）而直接访问在内存存储位置的\*\*数据结构\*\*。也就是说，它通过计算一个关于\*\*键值\*\*的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一般来说，实现哈希表我们可以采用两种方法：数组+链表或数组+二叉树。 \*\*散列技术\*\*：是一种新的存储技术。可通过查找关键字不需要比较就可获得需要记录的存储位置。散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系\`f\`，使得每个关键字Key对应一个存储位置\`f（key）\`。查找时，根据这个确定的对应关系找到给定值key的映射(key)，若查找集合中存在这个记录，则必定在\`f（key）\`的位置上。这里我们把这种对应关系f称为\*\*散列函数\*\*，又称为\*\*哈希（Hash）函数\*\*。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为\*\*散列表或哈希表（Hash Table）\*\*。那么关键字对应的记录存储位置我们称为\*\*散列地址\*\*。 散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。 散列技术最适合的求解问题是\*\*查找与给定值相等的记录\*\*。对于查找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。 比如那种同样的关键字，它能对应很多记录的情况，就不适合用散列技术。一个班级几十个学生，他们的性别有男有女，你用关键字"男"去查找，对应的有许多学生的记录，这显然是不合适的。只有如用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。同样散列表也不适合范围查找，比如查找一个班级18～22岁的同学，在散列表中没法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。 #### 二. 散列函数的构造方法 \*\*1. 直接定址法\*\*：取关键字本身 / 关键字的某个线性函数值 作为哈希地址。即：\`Hash(key) = key\` 或者 \`Hash(key) = a \* key + b\`，其中 \`a\` 和 \`b\` 为常数。 这种方法计算最简单，且不会产生冲突。适合于关键字分布基本连续的情况，如果关键字分布不连续，空位较多，则会造成存储空间的浪费。 \*\*2. 除留余数法：\*\*假设哈希表的表长为 m，取一个不大于 m 但接近或等于 m 的质数 p，利用取模运算，将关键字转换为哈希地址。即：Hash(key) = key % p，其中 p 为不大于 m 的质数。 这也是一种简单且常用的哈希函数方法。其关键点在于 p 的选择。根据经验而言，一般 p 取素数或者 m，这样可以尽可能的减少冲突。 \*\*3. 平方取中法：\*\*先通过求关键字平方值的方式扩大相近数之间的差别，然后根据表长度取关键字平方值的中间几位数为哈希地址。比如：Hash(key) = (key \* key) // 100 % 1000，先计算平方，去除末尾的 2 位数，再取中间 3 位数作为哈希地址。 这种方法因为关键字平方值的中间几位数和原关键字的每一位数都相关，所以产生的哈希地址也比较均匀，有利于减少冲突的发生。 \*\*4. 基数转换法\*\*：将关键字看成另一种进制的数再转换成原来进制的数，然后选其中几位作为哈希地址。比如，将关键字看做是 \`13\` 进制的数，再将其转变为 \`10\` 进制的数，将其作为哈希地址。 #### 三. 处理散列冲突的方法 我们说了这么多，散列函数应该如何设计？这个我们需要重点来讲解，总之设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。另一个问题是冲突。在理想的情况下，每一个关键字，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。我们时常会碰到两个关键字key\~1\~ 不等于 key\~2\~，但是却有f（key\~1\~）=f（key\~2\~），这种现象我们称为\*\*冲突（collision）\*\*，并把key\~1\~和key\~2\~称为这个散列函数的\*\*同义词（synonym\*\*）。 常用的哈希冲突解决方法主要是两类：\*\*开放地址法（Open Addressing）\*\* 和 \*\*链地址法（Chaining）\*\*。 \*\*1. 开放地址法/线性探测法（Open Addressing）：\*\*指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。 当发生冲突时，开放地址法按照下面的方法求得后继哈希地址：H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, ..., n (n ≤ m - 1)。 \*\*2. 链地址法/拉链法（Chaining）\*\*：将具有相同哈希地址的元素（或记录）存储在同一个线性链表中。链地址法是一种更加常用的哈希冲突解决方法。相比于开放地址法，链地址法更加简单。 \> 参考自：https://blog.csdn.net/zy_dreamer/article/details/131036258 \> \> https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0 #### 四. 代码示例 \`\`\`java /\*\* \* desc 哈希表的使用 \* @author GreyPigeon mail:2371849349@qq.com \* @since 2024-01-20-15:42 \*\*/ public class HashTabDemo { public static void main(String\[\] args) { //创建哈希表 HashTab hashTab = new HashTab(7); //写一个简单的菜单 String key = ""; Scanner scanner = new Scanner(System.in); while(true) { System.out.println("add: 添加雇员"); System.out.println("list: 显示雇员"); System.out.println("find: 查找雇员"); System.out.println("exit: 退出系统"); key = scanner.next(); switch (key) { case "add": System.out.println("输入id"); int id = scanner.nextInt(); System.out.println("输入名字"); String name = scanner.next(); //创建 雇员 Emp emp = new Emp(id, name); hashTab.add(emp); break; case "list": hashTab.list(); break; case "find": System.out.println("请输入要查找的id"); id = scanner.nextInt(); hashTab.findEmpById(id); break; case "exit": scanner.close(); System.exit(0); default: break; } } } } //创建HashTab 管理多条链表 class HashTab { private EmpLinkedList\[\] empLinkedListArray; private int size; //表示链表的数量 //构造器 public HashTab(int size) { this.size = size; //初始化empLinkedListArray empLinkedListArray = new EmpLinkedList\[size\]; //分别初始化每个链表，否则会报空指针异常 for(int i = 0; i \< size; i++) { empLinkedListArray\[i\] = new EmpLinkedList(); } } //添加雇员 public void add(Emp emp) { //根据员工的id ,得到该员工应当添加到哪条链表 int empLinkedListNO = hashFun(emp.id); //将emp 添加到对应的链表中 empLinkedListArray\[empLinkedListNO\].add(emp); } //遍历所有的链表,遍历hashtab public void list() { for(int i = 0; i \< size; i++) { empLinkedListArray\[i\].list(i); } } //根据输入的id,查找雇员 public void findEmpById(int id) { //使用散列函数确定到哪条链表查找 int empLinkedListNO = hashFun(id); Emp emp = empLinkedListArray\[empLinkedListNO\].findEmpById(id); if(emp != null) {//找到 System.out.printf("在第%d条链表中找到 雇员 id = %d\\n", (empLinkedListNO + 1), id); }else{ System.out.println("在哈希表中，没有找到该雇员\~"); } } //编写散列函数, 使用除留余数法 public int hashFun(int id) { return id % size; } } //创建EmpLinkedList ,表示链表 class EmpLinkedList { //头指针，执行第一个Emp,因此我们这个链表的head 是直接指向第一个Emp private Emp head; //默认null //添加雇员到链表 //说明 //1. 假定，当添加雇员时，id 是自增长，即id的分配总是从小到大 //因此我们将该雇员直接加入到本链表的最后即可 public void add(Emp emp) { //如果是添加第一个雇员 if(head == null) { head = emp; return; } //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后 Emp curEmp = head; while(true) { if(curEmp.next == null) {//说明到链表最后 break; } curEmp = curEmp.next; //后移 } //退出时直接将emp 加入链表 curEmp.next = emp; } //遍历链表的雇员信息 public void list(int no) { if(head == null) { //说明链表为空 System.out.println("第 "+(no+1)+" 链表为空"); return; } System.out.print("第 "+(no+1)+" 链表的信息为"); Emp curEmp = head; //辅助指针 while(true) { System.out.printf(" =\> id=%d name=%s\\t", curEmp.id, curEmp.name); if(curEmp.next == null) {//说明curEmp已经是最后结点 break; } curEmp = curEmp.next; //后移，遍历 } System.out.println(); } //根据id查找雇员 //如果查找到，就返回Emp, 如果没有找到，就返回null public Emp findEmpById(int id) { //判断链表是否为空 if(head == null) { System.out.println("链表为空"); return null; } //辅助指针 Emp curEmp = head; while(true) { if(curEmp.id == id) {//找到 break;//这时curEmp就指向要查找的雇员 } //退出 if(curEmp.next == null) {//说明遍历当前链表没有找到该雇员 curEmp = null; break; } curEmp = curEmp.next;//以后 } return curEmp; } } //表示一个雇员 class Emp { public int id; public String name; public Emp next; //next 默认为 null public Emp(int id, String name) { super(); this.id = id; this.name = name; } } \`\`\`