散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列表
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
散列函数
散列函数，顾名思义，它是一个函数。如果把它定义成 hash(key) ，其中 key 表示元素的键值，则 hash(key) 的值表示经过散列函数计算得到的散列值。
散列函数的特点：
确定性
如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
散列碰撞
散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。
不可逆性
一个哈希值对应无数个明文，理论上你并不知道哪个是。
混淆特性
输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
常见的散列函数
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;
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());
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();
}
}
|
结果如下：
