散列表(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(); } }
|
结果如下:
