DomBro Studio

散列

2018/01/26

概览

散列 (hashing)是常见的数据结构之一。它是以常数平均时间执行插入、删除和查找的技术。而与排序有关操作——查找最大最小值、按大小顺序打印等操作不被支持。

一些概念

概览 简单介揭开了散列的面纱。下面通过一些概念介绍散列。

关键字(key)

关键字的英文就是很常见的 key 。通常我们所说的查找,查找的是查找项的某一部分(即数据域),而这一部分就叫做关键字(key)。

散列

散列(散列表)简单来说就是一个包含一些项的具有固定大小的数组。如果散列表的大小是 size,则让散列表从 0 到 size-1 变化。每个关键字被映射到从 0 到 size-1 这个范围中的某个数,并被放到合适的单元中,这个映射就叫做散列函数。如下图就是一个散列表

在图中 tom 散列到 1 ,sim 散列到 2 ,mike 散列到 4 。

冲突

散列在理想条件下,要保证任何两个不同关键字映射到不同的单元,(如上图中的散列表就是一个理想的散列表) 但是这是不可能的,因为单元数目是有限的,而关键字实际上是用不完的!如果两个关键字散列到同一个值时,这就出现了冲突!而当冲突出现时要做什么就是我们下面要研究的问题之一。

装填因子

装填因子 λ ,代表散列表中元素与表大小的比。

散列函数

散列函数单独拿出来作为一节内容,当然是因为它的重要性。不夸张的说正是因为散列函数,散列表这种数据结构才得以实现。散列函数要做的就是帮助关键字找到合适的单元存储。而这个合适单元一般就是指 0 到 size-1 这个范围中的某个数。

合理的散列函数

简单散列函数

一般合理的散列函数是 key mod size 。若果关键字 key 是整数则直接返回 key mod size 即可,但如果 key 字符串,可以计算出该字符串每个字符的ASCⅡ码值加起来。实现如下:

1
2
3
4
5
6
7
8
9
10
publlic static int hash(String hash,int size){

int hashVal = 0;

for(int i = 0; i < size;i++ ) {
hashVal += hash.cahrAt(i);
}

retuen hashVal % size;
}

散列表大小(size)选取

表的大小 size 的选取具有一定学问,为什么呢?例如表的大小是 10 ,而关键字都是十的倍数,则经过散列函数的映射取余后所有的关键字都会映射到 0 单元,这显然不合理。好的办法是散列表大小尽量是素数,这样的散列函数不仅计算起来简单而且关键字分配也较均匀

好的散列函数

什么是好的散列函数?无非就是要保证每个关键字均匀的分配在散列表的单元中,上面推荐了散列表大小尽量是素数这样的策略,但即使这样也还是有一定缺陷。考虑这样一种情况,假设每个关键字字符串均包含8个字符串,且表大小 size 为 10007(素数)。ASCⅡ字符的值最多为127,则8个字符表示最大的数为 8*127=1016,按照简单散列函数的算法,所有字符串都会被映射在 0 和 1016 单元之间。显然这不是一个好的散列函数!
下面介绍一种好的散列函数,该函数利用到了 Horner 法则。这个函数就表的分布来说并不是最好的,但确实是简单高效的。

1
2
3
4
5
6
7
8
9
10
11
12
13
publlic static int hash(String hash,int size){

int hashVal = 0;

for(int i = 0; i < hash.length(); i++ ) {
hashVal = 37 * hashVal + keyn.cahrAt(i);
}

hashVal %= size;
if(hashVal < 0)
hashVal += size;
retuen hashVal % size;
}

解决冲突

如果当一个元素被插入时,与一个已经插入的元素散列到一个相同的单元,那么就产生一个冲突,这个冲突需要消除。解决冲突的方法有好几种介绍最简单的两种:分离链接法和开放定址法。

分离链接法

原理

分离链接法做法是将散列到同一个单元的所有元素保留到一个表中

上图中(该图不是一个好的例子,表的大小没有被设计成素数)关键字 0,20,30 都被散列到 0 单元,产生了冲突,但将这几个冲突的关键字放置在同一个链表中就解决了冲突。这个结构直观感受起来比描述起来更简单对吧!

查找过程

使用分离链表法在进行查找时,需要使用散列函数确定关键字在哪个链表(即找到关键字对应所在单元)中,然后再被确定的链表中执行一次查找。

插入过程

插入过程同样需要散列函数找到该关键字应插入单元的链表,如该关键字是一个新元素,那他将被插入到链表的前端。

实现

由上所述,分离链接法解决散列冲突,散列表需要存储一个链表数组,用链表数组的索引代表散列表的单元。前面提到的散列表的大小 size 就是该链表数组的规模

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
55
56
57
58
59
60
61
public class SeparateChainingHashTable<AnyType> {
//指定散列表默认大小
private static final int DEFAULT_TABLE_SIZE = 101;
//基于分离链表法实现,需要储存一个表的数组
private List<AnyType>[] theLists;
//当前散列表中插入关键字个数
private int currentSize;
//使用构造方法对 theLists 初始化
public SeparateChainingHashTable(int size) {
theLists = new LinkedList[size];
for (int i = 0;i < theLists.length;i++){
theLists[i] = new LinkedList<>();
}
}

public SeparateChainingHashTable() {
this(DEFAULT_TABLE_SIZE);
}

public void makeEmpty(){
for (int i = 0; i < theLists.length; i++){
theLists[i].clear();
}
currentSize = 0;
}
//散列函数
private int myhash(AnyType x){
int hashVal = x.hashCode();
hashVal %= hashVal/theLists.length;
if (hashVal < 0){
hashVal += theLists.length;
}
return hashVal;
}
//判断散列表中是否包含某关键字
public boolean contains(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
return whichList.contains(x);
}
//插入过程
public void insert(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
if ( !whichList.contains(x)){
whichList.add(x);
if (++currentSize > theLists.length)
rehash();
}
}
//删除关键字
public void remove(AnyType x){
List<AnyType> whichList = theLists[myhash(x)];
if ( whichList.contains(x)){
whichList.remove(x);
currentSize--;
}
}

private void rehash() {
//代码见下一节
}
}

算法分析

分离链接法简单易懂。它的效率也很好计算,查找一次所需要的时间是计算散列函数所需要的常数时间和遍历链表所需时间。一般来说使用分离链接法的使用原则是预料的元素与表大小(链表数组长度)相等即 装填因子λ ≈ 1,如果元素个数超过了表大小,则调用177行的rehash()方法,这个方法在再散列小节研究。分离链接法的缺点是使用了一些链表:给新单元分配地址需要时间,这使得算法速度有些慢,同时还要使用第二种数据结构实现(链表),散列表本身就是一种数据结构。

无链表的散列表

上面提到分离链接法的缺点就是用到了另一种数据结构——链表,不用链表解决冲突的方法是尝试将产生冲突的元素散列到另一些空的单元,也就说明所有的关键字都要放入散列表内,所以散列表的大小也要比分离链接法更大。一般来说对于不使用分离链接的散列表来说 装填因子λ应该低于0.5,这样的表叫做探测散列表。探测列表通常有三种解决方案。

冲突函数

探测散列表中,会使用冲突函数f(i) 解决冲突问题

线性探测法

听起来有点高大上,不要害怕。跟住思路,线性探测法的散列公式(即关键字插入到散列表某个单元的公式) 是 h~i~(x) = hash(x) + f(i) 其中 f(i) = i 。不难理解公式中的 f(i) = i 是冲突函数,使用hash()找到关键字应该在的散列表中单元后,如果发生冲突则从该单元开始探测逐个单元,以查找出一个空单元。

上图这个例子中,基于简单散列函数进行散列,我找了三个极端的例 0、11、22 他们对size(本例中为11)取余均为0。具体过程图片中以给出。简单来说线性探测法在遇到冲突时会一直向下寻找下一个(可以回绕)不冲突的单元。
线性探测的使用场景是预计的插入元素(关键字)要小于散列表的大小,否则线性探测的效率是很低的。
还有一个问题值得注意,0,11,22与10中间隔了一大片空白,使用线性探测会出现这种小范围聚集的现象,被称为一次聚集,使得散列表元素分配不够均匀。为了改善这种一次聚集现象,使用平方探测法解决冲突是一个很好的选择。

平方探测法

平方探测是消除线性探测中一次聚集的冲突解决方法。平方探测是将 h~i~(x) = hash(x) + f(i) 中的 冲突函数 f(i) 为二次的方法。流行的选择是 f(i) = i^2^。

由上图所示,使用平方探测法解决冲突, 改善了一次聚集的情况,使散列表元素的分布更加均匀。

  • 平方探测定理

如果使用平方探测,且表的大小是素数,那么当表至少有一半至少是空时候,总能插入一个新元素。

平方探测法具体实现
  • 基本策略

1.基于数组实现散列表结构,即关键字插入到该数组中。
2.删除元素时使用惰性删除,即将元素的 isActive 设为false

  • 实现代码
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class QuadraticProbingHashTable<AnyType> {

private static final int DEFAULT_TABLE_SIZE = 11;
private HashEntry<AnyType>[] array;
private int currentSize;

public QuadraticProbingHashTable() {
this(DEFAULT_TABLE_SIZE);
}



public QuadraticProbingHashTable(int size) {
allocateArray(size);
makeEmpty();
}
//置空散列表
public void makeEmpty(){
currentSize = 0;
for (int i = 0;i < array.length;i++){
array[i] = null;
}
}
//初始化 HashEntry 数组
private void allocateArray(int arraySize){
array = new HashEntry[arraySize];
}

public boolean contains(AnyType x){
int currentPos = findPos(x);
return isActive(currentPos);
}

//判断散列表中元素是否有意义
private boolean isActive(int currentPos) {
return array[currentPos] != null && array[currentPos].isActive;
}
//探测函数,找到关键字应插入位置
public int findPos(AnyType x){
int offset = 1;
int currentPos = myhash(x);
while (array[currentPos] != null && !array[currentPos].element.equals(x)){
currentPos += offset;
offset += 2;
if (currentPos >= array.length){
currentPos -= array.length;
}
}
return currentPos;
}
//删除,这里是惰性删除
public void remove(AnyType x){
int currentPos = findPos(x);
if (isActive(currentPos)){
array[currentPos].isActive = false;
}
}
//将关键字插入散列表中
public void insert(AnyType x){
//找到插入单元
int currentPos = findPos(x);
//如果x已存在与散列表则什么也不做
if (isActive(currentPos)){
return;
}
array[currentPos] = new HashEntry<AnyType>(x,true);
if (currentSize > array.length/2){
rehash();
}
}

private void rehash() {
}


private int myhash(AnyType x){
int hashVal = x.hashCode();
hashVal %= array.length;
if (hashVal < 0){
hashVal += array.length;
}
return hashVal;
}

//嵌套类,isActive属性判断元素在散列表中是否存在于散列表
private static class HashEntry<AnyType>{

public AnyType element;
public boolean isActive;
public HashEntry(AnyType e){
this(e,true);
}

public HashEntry(AnyType e,boolean i){
element = e;
isActive = i;
}
}
}

值得一提的是 findPos 方法,这个方法用于探测到元素应该插入的位置,你可能会奇怪并没有看到平方,实际上平方探测法就是为了使元素之间具有一段距离,通过 offset+2 也可以达到一样的效果,并且由于没有使用乘法,它探测的速度更快!同样rehash方法也在再散列小节研究

再散列

再散列 rehash 可以说是一个过程。例如,如果使用平方探测法,散列表中元素添加超过一半的单元,那么插入和查找的效率就很慢(对于分离链接法来说是插入元素等于单元个数时),解决办法是建一个两倍大小的表,并扫描整个原始散列表,计算每个未删除元素的的新散列值并插入到新表中。也就是要达到下图的效果

rehash 之后表的长度是 2*原表长 后的第一个素数。

分离链接法的再散列函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void rehash() {

List<AnyType>[] oldLists = theLists;
theLists = new List[2*theLists.length];
for (int i = 0; i < theLists.length;i++){
theLists[i] = new LinkedList<>();
}
currentSize = 0;
for (int j = 0; j < oldLists.length; j++){
for (AnyType item:oldLists[j]){
insert(item);
}
}
}

探测列表法的在散列函数

1
2
3
4
5
6
7
8
9
10
private void rehash() {
HashEntry<AnyType> [] oldArray = array;
allocateArray(2*array.length);
currentSize = 0;
for (int i = 0; i < oldArray.length;i++){
if (oldArray[i] != null && oldArray[i].isActive){
insert(oldArray[i].element);
}
}
}

Java 标准库中的散列表

Java标准库包括 Set 和 Map 的散列表实现,即 HashSet 和 HashMap。在 HashSet 中的项必须提供 equals 方法 和 hashCode 方法。HashSet 和 HashMap 通常是使用分离链接散列实现的。

CATALOG
  1. 1. 概览
  2. 2. 一些概念
    1. 2.1. 关键字(key)
    2. 2.2. 散列
    3. 2.3. 冲突
    4. 2.4. 装填因子
  3. 3. 散列函数
    1. 3.1. 合理的散列函数
      1. 3.1.1. 简单散列函数
      2. 3.1.2. 散列表大小(size)选取
      3. 3.1.3. 好的散列函数
  4. 4. 解决冲突
    1. 4.1. 分离链接法
      1. 4.1.1. 原理
      2. 4.1.2. 查找过程
      3. 4.1.3. 插入过程
      4. 4.1.4. 实现
      5. 4.1.5. 算法分析
    2. 4.2. 无链表的散列表
      1. 4.2.1. 冲突函数
      2. 4.2.2. 线性探测法
      3. 4.2.3. 平方探测法
        1. 4.2.3.1. 平方探测法具体实现
  5. 5. 再散列
    1. 5.1. 分离链接法的再散列函数
    2. 5.2. 探测列表法的在散列函数
  6. 6. Java 标准库中的散列表