记录生活中的点点滴滴

0%

哈希表

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

散列表

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存存储位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。

散列函数

散列函数,顾名思义,它是一个函数。如果把它定义成 hash(key) ,其中 key 表示元素的键值,则 hash(key) 的值表示经过散列函数计算得到的散列值。

散列函数的特点:

  1. 确定性

    如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。

  2. 散列碰撞

    散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的,但也可能不同。

  3. 不可逆性

    一个哈希值对应无数个明文,理论上你并不知道哪个是。

  4. 混淆特性

    输入一些数据计算出散列值,然后部分改变输入值,一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

常见的散列函数

1、MD5

MD5 即 Message-Digest Algorithm 5(信息-摘要算法5),用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一,主流编程语言普遍已有 MD5 实现。

2、SHA-1

SHA-1(英语:Secure Hash Algorithm 1,中文名:安全散列算法1)是一种密码散列函数,SHA-1可以生成一个被称为消息摘要的160位(20字节)散列值,散列值通常的呈现形式为40个十六进制数。

散列冲突

对于散列表而言,无论设置的存储区域(n)有多大,当需要存储的数据大于 n 时,那么必然会存在哈希值相同的情况。这就是所谓的散列冲突

常用的散列冲突解决方法有两类,开放寻址法(open addressing)和链表法(chaining)。

开放寻址法是一种解决碰撞的方法,对于开放寻址冲突解决方法,比较经典的有线性探测方法(Linear Probing)、二次探测(Quadratic probing)和 双重散列(Double hashing)等方法。

事实上,不管采用哪种探测方法,只要当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,需要尽可能保证散列表中有一定比例的空闲槽位。

一般使用加载因子(load factor)来表示空位的多少。

加载因子是表示 Hsah 表中元素的填满的程度,若加载因子越大,则填满的元素越多,这样的好处是:空间利用率高了,但冲突的机会加大了。反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了,但空间浪费多了。

链表法是一种更加常用的散列冲突解决办法,相比开放寻址法,它要简单很多。

如下图:

下面我们自己写一个哈希表的数据结构,散列函数用取余法,并用链表发解决散列冲突。

举个例子

我们先写一个员工节点类,它有id和姓名:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Emp{
private int id;
private String name;
public Emp next;//下一个Emp节点
public Emp(int id, String name) {
this.id = id;
this.name = name;
}
public int getId() {
return id;
}
@Override
public String toString() {
return "Emp{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}

我们用链表来管理它:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class EmpLinkedList{
Emp head;//头结点
public EmpLinkedList(){}
//添加节点
public void add(Emp emp){
if(head==null){
head = emp;
return;
}
Emp temp = head;
while (temp.next!=null){
temp = temp.next;
}
temp.next = emp;
}
//遍历
public void list(){
Emp temp = head;
while (temp!=null){
System.out.print(temp+"-->");
temp = temp.next;
}
System.out.println();
}
//查找
public Emp find(int id){
Emp temp = head;
while (temp!=null){
if(temp.getId()==id){
return temp;
}
temp = temp.next;
}
System.out.println("没有找到!");
return null;
}
//删除
public void del(int id){
//判断头结点
if(head.getId()==id){
head = head.next;
return;
}
Emp temp = head;
while (temp.next!=null){
if(temp.next.getId()==id){
temp.next = temp.next.next;
return;
}
temp = temp.next;
}
System.out.println("没有找到!删除失败!");
}
}

然后构造我们的哈希表类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//哈希表
class MyHashTable{
private int size;//数组大小
private EmpLinkedList[] empLinkedLists;//数组
public MyHashTable(int size){
this.size = size;
empLinkedLists = new EmpLinkedList[size];//初始化数组大小
//分别初始化链表
for (int i = 0; i < size; i++) {
empLinkedLists[i] = new EmpLinkedList();
}
}
//散列函数
public int hash(int id){//返回存在第几个数组中
return id%size;
}
//添加节点
public void add(Emp emp){
int index = hash(emp.getId());//根据id得到放入数组下标
empLinkedLists[index].add(emp);
}
//遍历节点
public void list(){
for (int i = 0; i < size; i++) {
System.out.print("第"+(i+1)+"个节点内容:");
empLinkedLists[i].list();
}
}
//查找节点
public Emp find(int id){
return empLinkedLists[id%size].find(id);
}
//删除节点
public void del(int id){
empLinkedLists[id%size].del(id);
}
}

main方法进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Demo1 {
public static void main(String[] args) {
MyHashTable hashTable = new MyHashTable(5);
hashTable.add(new Emp(1,"张三"));
hashTable.add(new Emp(2,"李四"));
hashTable.add(new Emp(3,"王五"));
hashTable.add(new Emp(4,"赵六"));
hashTable.add(new Emp(15,"15号兄弟"));
hashTable.add(new Emp(5,"Jack"));
hashTable.add(new Emp(6,"Tom"));
hashTable.list();
System.out.println("------查找id为5的节点------");
System.out.println(hashTable.find(5));
System.out.println("------删除id为5的节点------");
hashTable.del(5);
hashTable.list();
}
}

结果如下: