哈希表

发表于 | 分类于
字数统计: 1.1k

基本概念

哈希表是一种特殊的数据结构，通过索引，能快速的查找到某个元素。

put get
List O(n) O(n)
Balanced BST O(logn) O(logn)
Hash Table O(1) O(1)

设计原理

通过哈希函数，将key映射到value上。

  • Java 中哈希的实现
Balanced BST HashTable
TreeSet HashSet
TreeMap HashMap

哈希函数 (hash function)

确定性，不可逆性。
输入任何二进制数据，输出整数。
在密码学也有广泛应用。
一个好的哈希函数，要在给定的输入范围内，尽可能少的发生碰撞；而且计算复杂度不能太高。

  • 除余法(modulo division)

    1
    2
    3
    4
    // Java String hashcode
    for (char c : str) {
        hashCode = 31 * hashCode + c;
    }

  • 平方取中法(mid-square)

  • 基数转换法(radix transformation)

冲突解决(collision)

  • 开散列(open hashing)
    开辟一个数组
    数组的每一个元素是一个链表的头结点的引用
    通过Hash函数，计算key对应的index，将index相同的key-value插入到同 一个链表中
  • 闭散列(closed hashing)
    open addressing
    开辟一个数组，一个位置只放一个key-value
    通过Hash函数，计算key对应的index，将key-value放在相应的位置
    如果这个位置已经有了元素，则查找其他合适的空位置放入
    线性探查 (linear probing)
    二次探查 (quadratic probing)
    随机探查 (random probing)
    双散列探查 (double hashing)

重哈希(rehashing)

当哈希表中的元素越来越多的时候，冲突的几率也就越来越高。为了提高查询的效率，就要对哈希表进行扩容。
负载因子(load factor) : 哈希表中的元素个数除以哈希表的容量。
哈希表检索的时间与负载因子有关, 当负载因子小于0.5时，大部分检索长度小于2; 当负载因子大于0.5时，性能急剧下降。这是一种空间换时间的方法。
重哈希就是调整哈希表的大小，并将元素重新摆放。
当哈希表过于稀疏，可以节省空间。
当哈希表过于稠密，可以加速查找。

实现

基本操作

查找
添加
删除
平均来说各操作的时间复杂度为O(1)，但最坏情况会到O(n)。因为在添加的过程中会出现碰撞和重哈希的过程。

定义HashMap接口

1
2
3
4
public interface Map {
    void put(String key, String val);
    String get(String key);
}

定义键值对

1
2
3
4
5
6
7
8
public class Pair {
    String key;
    String val;
    Pair(String key, String val) {
        this.key = key;
        this.val = val;
    }
}

使用open hashing解决collision

separate chaining方法

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
class ListNode {
    Pair pair;
    ListNode next;
    ListNode(Pair pair) {
        this.pair = pair;
        next = null;
    }
}

public class openHashingMap implements Map {
    private ListNode[] data;
    private int capacity;
    private int size;
    private static final float LOAD_FACTOR = 0.75f; // 设置loadFactor为0.75
    public openHashingMap() {
        capacity = 16;
        size = 0;
        data = new ListNode[capacity];
    }
    public openHashingMap(int capacity) {
        this.capacity = capacity;
        size = 0;
        data = new ListNode[capacity];
    }
    @Override 
    public void put(String key, String val) {
        if (key == null) return;
        if (size >= capacity * LOAD_FACTOR) {
            rehashing();
        }
        int index = key.hashCode() % capacity; // 使用Java自带的String.hashCode()当做hash function
        ListNode cur = data[index];
        while (cur != null) {
            if (cur.pair.key.equals(key)) {
                // map中已经有这个key了，更新value
                cur.pair.val = val;
                return;
            }
            cur = cur.next;
        }
        // map中没有这个key，在这个index添加新节点
        ListNode newNode = new ListNode(new Pair(key, val));
        newNode.next = data[index];
        data[index] = newNode;
        size++;
    }
    @Override
    public String get(String key) {
        if (key == null) {
            return null;
        }
        int index = key.hashCode() % capacity;
        ListNode cur = data[index];
        while (cur != null) {
            if (cur.pair.key.equals(key)) {
                return cur.pair.val;
            }
            cur = cur.next;
        }
        return null;
    }
    // 重哈希扩大为原容量的2倍
    private void rehashing() {
        int newCapacity = capacity * 2;
        ListNode[] newData = new ListNode[newCapacity];
        for (int i = 0; i < capacity; ++i) {
            ListNode cur = data[i];
            while (cur != null) {
                ListNode tmp = cur;
                cur = cur.next;
                int newIndex = tmp.pair.key.hashCode() % newCapacity;
                tmp.next = newData[newIndex];
                newData[newIndex] = tmp;
            }
        }
        capacity = newCapacity;
        data = newData;
    }
}

使用closed hashing解决collision

linear probing 方法

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
public class LPHashing implements Map{
    private Pair[] data = null;
    private int capacity = 0;
    public LPHashing() {
        capacity = 16;
        data = new Pair[capacity];
    }
    public LPHashing(int capacity) {
        this.capacity = capacity;
        data = new Pair[capacity];
    }
    @Override
    public void put(String key, String val) {
        if (key == null) return;
        int index = key.hashCode() % capacity;
        for (int i = 0; i < capacity; ++i) {
            int cur = (index + i) % capacity;
            if (data[cur] == null) {
                data[cur] = new Pair(key, val);
                return;
            } else if (data[cur].key.equals(key)) {
                data[cur].val = val;
                return;
            }
        }
        throw new IllegalStateException("HashMap is already full");
    }
    @Override
    public String get(String key) {
        if (key == null) {
            return null;
        }
        int index = key.hashCode() % capacity;
        for (int i = 0; i < capacity; ++i) {
            int cur = (index + i) % capacity;
            if (data[cur] == null) {
                return null;
            } else if (data[cur].key.equals(key)) {
                return data[cur].val;
            }
        }
        return null;
    }
}

Lintcode 相关练习

Count Characters
Strobogrammatic Number
two sum
Anagrams
Copy List with Random Pointer