前言

前面学习到的几种算法比如红黑树二叉搜索树,查找插入时间复杂度最快也只能到O(logn).现在介绍一种算法可以使查找插入时间复杂度达到常数级别。

散列表(Hash table)

也称为哈希表。是字典的一种抽象。比如说你要查一个字,通过这个字的拼音首字母,找到这个字的页码,然后翻到那页找就行了。这种方法直接把查找时间复杂度降到了常数。但是要牺牲一定的计算索引的时间。计算索引的那个函数称为哈希函数(散列函数`)。如果两个不同的key算出了同一个索引,此时就要用到一定的方法来解决哈希冲突。

哈希函数

哈希函数一般具有如下特点。

  • 相等的key产生相等的哈希值
  • 计算简单方便
  • 哈希值均匀分布。(若过度集中,则容易使效率降低到o(n))

构造哈希函数有多种方法,这里不详细讲解。

哈希冲突

若两个不相等的key产生了相等的哈希值,这时则需要采用哈希冲突

拉链法

Java标准库的HashMap基本上就是用拉链法实现的。拉链法的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

实现步骤

  • 得到一个key
  • 计算keyhashValue
  • 根据hashValue值定位到data[hashValue]。(data[hashValue]是一条链表)
  • data[hashValue]为空则直接插入
  • 不然则添加到表头

这里需要注意的是,哈希函数必须保证哈希值均匀分布,若全部集中在一条链表中,则时间复杂度和顺序链表相同。

还有一点则是数组的大小,若你能估计数据的大小,则直接指定即可,否则就需要动态扩充数组。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class SeparateChainingHashST<Key,Value> {
//这里的M需要根据实际情况调整
public SeparateChainingHashST(int M) {
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i=0;i<M;i++){
st[i]=new SequentialSearchST<Key,Value>();
}
}

private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
public void put(Key k,Value v){
int hashValue = hash(k);
st[hashValue].put(k,v);
}

public Value get(Key k){
int hashValue = hash(k);
return st[hashValue].get(k);
}
}

线性探测

线性探测直接使用数组来存储数据。可以想象成一个停车问题。若当前车位已经有车,则你就继续往前开,直到找到下一个为空的车位。

实现步骤

  • 得到key
  • 计算得hashValue
  • 若不冲突,则直接填入数组
  • 若冲突,则使hashValue++,也就是往后找,直到找到第一个data[hashValue]为空的情况,则填入。若到了尾部可循环到前面。

实现

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
public class LinearProbingHashST<Key,Value> {
public LinearProbingHashST(int cap) {
keys = (Key[]) new Object[cap];
values = (Value[]) new Object[cap];
M = cap;
}

private int hash(Key key){
return (key.hashCode() & 0x7fffffff) % M;
}
public void put(Key key,Value value){
//若当前数据含量超过了总容量的一半,则重新调整容量
if(N>=M/2) resize(2*M);
int hashValue = hash(key);
if (values[hashValue]==null){
keys[hashValue] = key;
values[hashValue] = value;
N++;
}
else if(keys[hashValue].equals(key)){
values[hashValue]=value;
}
else{
while (values[hashValue] != null){
hashValue = (hashValue+1)%M;
}
keys[hashValue] = key;
values[hashValue] = value;
N++;
}
}
public Value get(Key key){
int hashValue = hash(key);
if (keys[hashValue]!=null&&!keys[hashValue].equals(key)){
while (keys[hashValue]!=null &&keys[hashValue]!=key){
hashValue = (hashValue+1)%M;
}
}
return values[hashValue];
}
}

性能比较

一般来说,使用散列表会比红黑树快很多。但具体还是要看哈希函数的计算效率。但是散列表无法保证顺序,所以如果你需要进行有关顺序的操作,应该使用红黑树或者二叉搜索树

对于线性探测来说动态调整数组大小是必要的,不然会产生死循环。

拉链法的删除操作比较方便,直接链表修改地址即可。而线性探测删除操作很复杂,而且线性探测耗费的内存比拉链法要多。

分别对四个文件进行插入搜索操作。

  • tale.txt(779kb)
    顺序查找(7.143秒) 二分查找(0.46秒) 二叉搜索树(0.191秒) 红黑树(0.237秒) 拉链法(0.124秒) 线性探测(0.103秒)
  • leipzig100k.txt(12670kb)
    顺序查找(无) 二分查找(13.911秒) 二叉搜索树(1.389秒) 红黑树(1.442秒)
    拉链法(0.707秒) 线性探测(0.562秒)
  • leipzig300k.txt(37966kb)
    顺序查找(无) 二分查找(60.222秒) 二叉搜索树(2.742秒) 红黑树(3.104秒)
    拉链法(1.839秒) 线性探测(1.559秒)
  • leipzig1m.txt(126607kb)
    顺序查找(无) 二分查找(无) 二叉搜索树(3.016秒) 红黑树(2.797秒)
    拉链法(3.938秒) 线性探测(3.668秒)

Reference

维基百科

算法 4th