hello 大家好，我是1z，真的是好久不见啦！今天给大家分享的是一种常见的数据结构-散列表
什么是散列表？
散列表，听起来是个高大上的名字，但是它有着更被我们熟知的称呼，哈希表（Hash table）。
散列表的定义
为了规范下列描述，统一使用散列表来称呼。
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
举个栗子: 假设在电影院准备看电影，你需要做的就是记住自己在电影院的位置，然后直接坐到位置上即可。这时候你一个人就确定了一个位置。你就像一个“key”，你的位置就像是“value”。电影院的座次安排就像是“散列表”。而映射函数呢，就是你如何选择座位啦。
什么是散列函数？
简单来说，就是通过一个数（key）得到一个唯一值（value）的逻辑。
像是小学二年级学的y = x + 1,通过一个x可以得到唯一的y。此时的函数就可以称为散列函数。
散列函数的设计规则
-
散列函数计算得到的散列值是一个非负整数
-
若 key1 == key2,则散列函数之后的值也相等
-
若key1 != key2，则散列函数之后的值不相等
散列冲突的出现和解决方式？
有没有可能你去电影院，发现你的位置被别人占用了？这时候说不定就起冲突了…
如果出现了两个散列值不相等，但是最终结果一致，这个时候我们称出现了散列冲突，这几乎是无法避免的问题。
该如何解决散列冲突问题呢？
常见的散列冲突解决方式有两种: 开放寻址法（open addressing）和链表法（chaining）
-
开放定址法
①核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。
②线性探测法（Linear Probing) 插入数据：当我们往散列表中插入数据时，如果某个数据经过散列函数之后，存储的位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。
查找数据：我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素是否相等，若相等，则说明就是我们要查找的元素；否则，就顺序往后依次查找。如果遍历到数组的空闲位置还未找到，就说明要查找的元素并没有在散列表中。
删除数据：为了不让查找算法失效，可以将删除的元素特殊标记为deleted，当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来，而是继续往下探测。
结论：最坏时间复杂度为O(n)
③二次探测（Quadratic probing）：线性探测每次探测的步长为1，即在数组中一个一个探测，而二次探测的步长变为原来的平方。(原: hash+1，hash+2; 现在 hash+1^2,hash+2^2…)
④双重散列（Double hashing）：使用一组散列函数，直到找到空闲位置为止。
⑤线性探测法的性能描述：用“装载因子”来表示空位多少，散列表装载因子=填入表中的个数/散列表的长度。装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。
注: ThreadLocalMap即使用了开放寻址法解决hash冲突。
-
链地址法(常用）
插入数据：当插入的时候，我们需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即可，所以插入的时间复杂度为O(1)。
查找或删除数据：当查找、删除一个元素时，通过散列函数计算对应的槽，然后遍历链表查找或删除。对于散列比较均匀的散列函数，链表的节点个数k=n/m，其中n表示散列表中数据的个数，m表示散列表中槽的个数，所以是时间复杂度为O(k)。 注: HashMap即使用了开放寻址法解决hash冲突。
利用散列表实现需求
需求说明:假设现在需要简单的记录多位学生的信息，并且可以做到添加 和 查询，该如何实现呢。
分析需求:这时候可以使用散列表这一数据结构来解决啦，我们需要思考几个问题
-
1、如何构建散列表的数据结构？ -
2、如何解决散列冲突？ -
3、如何确定散列函数？ -
4、如何抽象学生的基础信息和一些操作行为？
1、如何构建散列表的数据结构？
在这里我们使用数组 + 链表的方式进行构建散列表，形如下图。
2、如何解决散列冲突？
使用链地址法
3、如何确定散列函数?
//散列函数
public int hashFun(int id){
//id % size
return id & (size - 1);
}
4、如何抽象学生的基础信息 和 一些操作行为?
将单个学生的信息抽象成实体，将学生的信息挂载在链表上，并进行操作链表。
show me the code!
/**
* 学生信息
* */
public class Student {
public int id;
public String name;
public Student next;
public Student(int id, String name) {
super();
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + ''' +
'}';
}
}
//链表
public class StudentLinkedList {
private MyHashStruct struct;
//需要一个头指针，指向第一个Stu,因为我们这个链表的head是直接指向第一个Stu
private Student head;//默认为空
/**
* 添加节点
* */
public void addStu(Student stu){
//添加第一个元素
if(head == null){
head = stu;
return;
}
//否则采用尾插法
Student cur = head;
while(true){
if(cur.next == null) break;
cur = cur.next;
}
//跳出循环的时候 cur到达了最后一位
cur.next = stu;
}
/**
* 遍历链表
* */
public void list(int no){
if(head == null){
return;
}
//否则存在值
System.out.print("第"+no+"条链表信息为:");
Student cur = head;
while(true){
System.out.printf(" => id=%d name=%st",cur.id,cur.name);
if(cur.next == null) break;
cur = cur.next;
}
System.out.println();
}
/**
* 根据id查找链表
* */
public Student findStuById(int id){
struct = new MyHashStruct(16);
if(head == null){
System.out.println("当前的链表为空");
return null;
}
//辅助
Student curStu = head;
while(true){
if(struct.hashFunc(curStu.id) == id){
break;
}
if(curStu.next == null){
curStu = null;
break;
}
curStu = curStu.next;
}
return curStu;
}
}
//散列表主体
public class MyHashStruct {
private StudentLinkedList[] stuLinkedListArrays;
//存在多少条链表
public int size;
//构造器
public MyHashStruct(int size){
this.size = size;
stuLinkedListArrays = new StudentLinkedList[size];
//还需要去初始化每个链表
for(int i = 0;i < size;i++){
stuLinkedListArrays[i] = new StudentLinkedList();
}
}
//添加(根据id)
public void add(Student stu){
int stuListNO = hashFun(stu.id);
//将stu加入到链表中
stuLinkedListArrays[stuListNO].addStu(stu);
}
//遍历
public void list(){
for(int i = 0; i < size;i++){
stuLinkedListArrays[i].list(i);
}
}
//根据输入的id查找学生
public void findStuById(int id){
//使用散列函数
int no = hashFun(id);
Student stu = stuLinkedListArrays[no].findStuById(no);
if(stu != null){
System.out.printf("在第%d条链表中找到学生%s",no,stu.name);
}else{
System.out.println("未找到该学生");
}
}
//散列函数
public int hashFun(int id){
//id % size
return id & (size - 1);
}
}
//功能测试
public class HashStructDemo {
public static void main(String[] args) {
MyHashStruct hashTable = new MyHashStruct(16);
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();
//创建雇员
Student stu = new Student(id, name);
hashTable.add(stu);
break;
case "list":
hashTable.list();
break;
case "exit":
scanner.close();
System.exit(0);
case "find":
System.out.println("请输入待查找的id");
int findId = scanner.nextInt();
hashTable.findStuById(findId);
System.out.println();
default:
break;
}
}
}
}
测试效果如下:
注: 上述的例子存在多个扩展点，包括散列表的修改，动态扩容等。有兴趣的小伙伴可以将代码补充完整喔。
说在最后
这篇文章我们主要了解关于散列表（哈希表）的一些知识，包括散列表的定义，散列函数的定义和设计规则等，最后借助一个小例子手写简单的散列表。希望大家可以从这篇文章中加深对散列表这种结构的认识。然后可以更加方便的深入研究java对于散列表的实现。
(包括HashMap,ConcurrentHashMap,ThreadLocalMap等)
TIP：为了检验自己的学习成果，这里摆出一道题目供大家测试喔。
-
https://leetcode-cn.com/problems/design-hashmap/comments/
我是1z，那么这期就聊到这。
往期推荐：
我们是FingerDance，欢迎加入我们！
原文始发于微信公众号（FingerDance）：数据结构之散列表篇
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/26730.html
