概述

  • 哈希表(Hash Table)又称散列表，是一种通过键(Key)来访问值(Value)的数据结构。
  • 通过某种计算将键值对映射到数组的某个位置/索引上，以此查找记录内容的过程称为哈希(Hashing)，
  • 实现将键值对映射到数组的某个位置的函数称为哈希函数(Hash Function)

简单图示

Hashing

特性

场景

  • 适用与精确查找的场景(给定一个键k，找到与k对于的值v)
  • 不适用场景
    • 具有多个相同键值对的记录场景
    • 范围查找
    • 最大最小键值查找
    • 按键值顺序访问

哈希函数

  • 数字
    • 直接将键作为索引
    • 取模索引
    • …
  • 字符串
    • 计算哈希值作为索引存储

负载因子

  • 记录哈希表的满载程度, α=N/M\alpha = N / M

    • 其中，N 表示实际存储的元素个数，M 表示哈希表容量(桶/槽个数，数组长度…)

  • 负载因子越高，哈希表空间利用率越高，发生冲突的概率越大，插入、查找、删除复杂度越差

  • 负载因子越低，空闲槽位越多，空间利用率越低

冲突

  • 出现原因：出现不同键值使用哈希函数计算出来的哈希值是相同的
  • 解决方法：开散列(Open Hashing)、闭散列(Close Hashing)

开散列法(数据存储位置是开放的，无数组大小限制)

  • 拉链法: 在存放数据的地方开一个链表，相同索引的数据放到同一个链表中，查询的时候遍历列表获取数据

拉链法

闭散列法(数据存储位置受数组范围影响)

  • 如果发生冲突，就在冲突位置按照某种规则，往下继续查找，直到找到一处空位置为止，规则可以使用探测函数 p 表示(例如，发生冲突后的第 i 次探测表示: Pos(i) = (h(k) + p(k, i)) % M，其中，Pos 表示最终位置，h 为哈希函数，k 为键，M 为哈希表大小)
    • 线性探查法：p(k, i) = i
      • Primary Clustering 问题(元素在物理层面连续，大量元素挤在连续内存中)
        Primary Clustering
        • 解决方法
          • 改良线性探测: p(k, i) = i * c (c 为常数)
          • 伪随机: p(k, i) = random() (假设查找的元素是冲突元素，得获取原本的随机数才能找到元素，所以不能真随机)
          • 二次探测/平方探测: p(k, i) = i^2
      • Secondary Clustering 问题(元素在物理层面不一定连续，但是在探测函数上连续)
        Secondary Clustering
        • 解决方法
          • 双重哈希(Double Hashing): p(k, i) = i * h2(k)
  • 删除元素时，将相关元素标记为 Tombstone(墓碑)，在搜索时跳过，插入时覆写

桶哈希法

这个好像比较模糊，在教材 《Data Structures and Algorithm Analysis Edition 3.2 (C++ Version)》 —— Clifford A. Shaffer 中，把桶哈希归入闭散列法，但在网上也有开散列法的说法

桶哈希法

  • 将整个哈希表分为多个块，称为桶(bucket)，每个桶内部有固定的槽位(slot)
  • 键通过哈希函数映射到某个桶，槽位满了之后，存储到桶里的其它槽位
  • 桶满了之后，按照设定规则处理(例如覆盖桶里的槽位)(教材给出了处理方式是，额外搞一个无限容量的桶来存储溢出的数据，这个地方有开散列的味道)

复杂度分析

操作 平均时间复杂度 最坏时间复杂度
查找 O(1) O(n)
插入 O(1) O(n)
删除 O(1) O(n)
  • 平均时间复杂度预设: 元素分布均匀
    • 开散列法: O(1 + α\alpha) (α\alpha 是负载因子) (失败查找期望)
    • 闭散列法: O(1 / (1 - α\alpha)) (α\alpha 是负载因子) (失败查找期望)
  • 最坏时间复杂度都是发生冲突导致的
    • 开散列法: 所有元素都在一条链上
    • 闭散列法: 数组聚集且塞满

发散/随想/自身理解(?)

  • C++ 中 std::unordered_map<>, std::unordered_set<> 底层是哈希表
  • 核心是哈希函数(映射函数)
  • 用的地方很多很多，对于精确查找的场景很方便
  • 同样可以和其它结构和算法打组合拳，例如和双向链表组合搞 LRU

实现

ADT

1
2
3
4
5
6
7
8
9
10
11
12
13
class Hash {
public:
    Hash() {}
    virtual ~Hash() {}

    virtual bool Insert(const int key, const int value) = 0;
    virtual void Remove(const int key) = 0;
    virtual bool Find(const int key, int& value) const = 0;

    virtual int Size() const = 0;
    bool Empty() { return Size() == 0; }

};

开散列法(拉链法)

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
100
101
102
103
104
105
class OpenHash : public Hash {
public:
    OpenHash() { init(); }
    virtual ~OpenHash() { release(); }

    bool Insert(const int key, const int value) override { return insert(key, value); }
    void Remove(const int key) override { remove(key); }
    bool Find(const int key, int& value) const override { return find(key, value); }

    int Size() const override { return size; }

private:
    struct Node {
        int key;
        int value;
        Node* next;
        Node (int k, int v, Node* n = nullptr) : key(k), value(v), next(n) {}
    };

private:
    void init() {
        hash_table.resize(INDEX, nullptr);
    }

    void release() {
        for (int i = 0; i < INDEX; ++i) {
            Node* cur = hash_table[i];
            hash_table[i] = nullptr;
            while (cur != nullptr) {
                auto next = cur->next;
                delete cur;
                cur = next;
            }
        }
    }

    bool insert(const int key, const int value) {
        Node* node = find_node(key);
        if (node != nullptr) {
            node->value = value;
            return true;
        }

        int index = hash_function(key);
        Node* new_node = new Node(key, value);
        Node* cur = hash_table[index];
        new_node->next = cur;
        hash_table[index] = new_node;
        ++size;
        return true;
    }

    void remove(const int key) {
        int index = hash_function(key);
        Node* cur = hash_table[index];
        if (cur == nullptr) return;
        if (cur->key == key) {
            hash_table[index] = cur->next;
            delete cur;
            --size;
            return;
        }
        while (cur->next != nullptr) {
            auto next = cur->next;
            if (next->key == key) {
                cur->next = next->next;
                delete next;
                --size;
                break;
            }
            cur = next;
        }
    }

    bool find(const int key, int& value) const {
        Node* node = find_node(key);
        if (node != nullptr) {
            value = node->value;
            return true;
        }
        return false;
    }

    Node* find_node(const int key) const {
        int index = hash_function(key);
        Node* cur = hash_table[index];
        while (cur != nullptr) {
            if (cur->key == key) {
                return cur;
            }
            cur = cur->next;
        }
        return nullptr;
    }

    int hash_function(const int key) const {
        return (key % INDEX + INDEX) % INDEX;
    }

private:

    static constexpr int INDEX = 10;
    vector<Node*> hash_table;
    int size{0};
};

闭散列法(线性探查法)

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
100
101
102
103
class CloseHash: public Hash {
public:
    CloseHash() { init(); }
    virtual ~CloseHash() { release(); }

    bool Insert(const int key, const int value) override { return insert(key, value); }
    void Remove(const int key) override { remove(key); }
    bool Find(const int key, int& value) const override { return find(key, value); }

    int Size() const override { return size; }

private:
    enum Status {
        EMPTY,
        OCCUPIED,
        DELETED
    };
    struct Node {
        int key;
        int value;
        Status status;

        Node(int k = INT_MIN, int v = INT_MIN, Status s = EMPTY)
            : key(k), value(v), status(s) {}
    };


private:
    void init() {
        hash_table.resize(INDEX, Node());
    }

    void release() {
        hash_table.clear();
    }

    bool insert(const int key, const int value) {
        int index = find_node(key);
        if (index != -1) {
            hash_table[index].value = value;
            return true;
        }

        if (size == static_cast<int>(hash_table.size())) return false;
        index = hash_function(key);

        for (int i = 0; i < INDEX; ++i) {
            int pos = probe(index, i);
            if (hash_table[pos].status == EMPTY || hash_table[pos].status == DELETED) {
                hash_table[pos] = Node(key, value, OCCUPIED);
                ++size;
                return true;
            }
        }
        return false;
    }

    void remove(const int key) {
        int index = find_node(key);
        if (index == -1) return;

        hash_table[index].status = DELETED;
        --size;
    }

    bool find(const int key, int& value) const {
        int index = find_node(key);
        if (index == -1) return false;

        value = hash_table[index].value;
        return true;
    }

    int hash_function(const int key) const {
        return (key % INDEX + INDEX) % INDEX;
    }

    int probe(int base_index, int i) const {
        return (base_index + i) % INDEX;
    }

    int find_node(const int key) const {
        int index = hash_function(key);
        for (int i = 0; i < INDEX; ++i) {
            int pos = probe(index, i);
            if (hash_table[pos].status == EMPTY) {
                break;
            }
            if (hash_table[pos].status == OCCUPIED && hash_table[pos].key == key) {
                return pos;
            }
        }
        return -1;
    }

private:

    static constexpr int INDEX = 100;

    vector<Node> hash_table;
    int size{0};
};

桶哈希

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
// 桶满则插入失败，不搞无限槽位
class BucketHash : public Hash {
public:
    BucketHash() { init(); }
    virtual ~BucketHash() { release(); }

    bool Insert(const int key, const int value) override { return insert(key, value); }
    void Remove(const int key) override { remove(key); }
    bool Find(const int key, int& value) const override { return find(key, value); }

    int Size() const override { return size; }

private:
    enum Status { EMPTY, OCCUPIED, DELETED };

    struct Node {
        int key;
        int value;
        Status status;

        Node(int k = INT_MIN, int v = INT_MIN, Status s = EMPTY)
            : key(k), value(v), status(s) {}
    };

private:
    void init() {
        hash_table.resize(BUCKET_COUNT, vector<Node>(SLOT_COUNT, Node()));
    }

    void release() {
        hash_table.clear();
    }

    int hash_function(const int key) const {
        return (key % BUCKET_COUNT + BUCKET_COUNT) % BUCKET_COUNT;
    }

    // 在指定桶内查找 key，返回槽位索引；不存在返回 -1
    int find_in_bucket(const int key, const int bucket) const {
        const vector<Node>& slots = hash_table[bucket];
        for (int i = 0; i < SLOT_COUNT; ++i) {
            if (slots[i].status == EMPTY) {
                break;
            }
            if (slots[i].status == OCCUPIED && slots[i].key == key) {
                return i;
            }
        }
        return -1;
    }

    bool insert(const int key, const int value) {
        int bucket = hash_function(key);

        int slot = find_in_bucket(key, bucket);
        if (slot != -1) {
            hash_table[bucket][slot].value = value;
            return true;
        }

        vector<Node>& slots = hash_table[bucket];
        for (int i = 0; i < SLOT_COUNT; ++i) {
            if (slots[i].status == EMPTY || slots[i].status == DELETED) {
                slots[i] = Node(key, value, OCCUPIED);
                ++size;
                return true;
            }
        }
        return false;
    }

    void remove(const int key) {
        int bucket = hash_function(key);
        int slot = find_in_bucket(key, bucket);
        if (slot == -1) return;

        hash_table[bucket][slot].status = DELETED;
        --size;
    }

    bool find(const int key, int& value) const {
        int bucket = hash_function(key);
        int slot = find_in_bucket(key, bucket);
        if (slot == -1) return false;

        value = hash_table[bucket][slot].value;
        return true;
    }

private:
    static constexpr int BUCKET_COUNT = 10;
    static constexpr int SLOT_COUNT = 10;

    vector<vector<Node>> hash_table;
    int size{0};
};