关于散列表
2021-04-24 06:31:46 #数据结构与算法  #数据结构与算法  #CPP 

散列表

TableSize：表的大小，习惯于让表从 0 到TableSize-1变化

散列函数：映射，用于将每个关键字映射到从 0 到 TableSize-1 这个范围中的某个数，并放到适当的单元中

理想情况下，不同的关键字映射到不同的单元；但实际上不可能实现，单元个数有限

冲突：不同的关键字由散列函数得到一致的 hash，导致插入的位置一致所产生的冲突

分离链接法和开放定址法解决

分离链接法

将元素的关键字进行散列，根据散列，将元素保存到对应位置的链表中，STL 中有相关实现方法，重点看一下 HashTable 的原理

search：

  1. 计算散列
  2. 得到适当的链表
  3. 在链表中查找

insert：

  1. 计算散列
  2. 得到适当的链表
  3. 头插
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
// HashTable.h
#ifndef HASHTABLE_HASHTABLE_H
#define HASHTABLE_HASHTABLE_H

#include "../include/Hash.h"
#include <vector>
#include <list>

template<typename HashEdObj>
class HashTable {
public:
    explicit HashTable(int size = 101);

    bool contains(const HashEdObj &x) const;

    void makeEmpty();

    bool insert(const HashEdObj &x);

    bool insert(HashEdObj &&x);

    bool remove(const HashEdObj &x);

private:
    std::vector<std::list<HashEdObj>> theLists;
    int currentSize;

    void rehash();

    size_t myhash(const HashEdObj &x) const;
};

// 计算散列
template<typename HashEdObj>
inline size_t
HashTable<HashEdObj>::myhash(const HashEdObj &x) const {
    static hash<HashEdObj> hf;
    return hf(x) % theLists.size();
}

template<typename HashEdObj>
inline void
HashTable<HashEdObj>::makeEmpty() {
    for (auto &thisList:theLists)
        thisList.clear();
}

template<typename HashEdObj>
inline bool
HashTable<HashEdObj>::contains(const HashEdObj &x) const {
    auto &whichList = theLists[myhash(x)];// 计算散列并获得对应的链表
    return find(begin(whichList), end(whichList), x) != end(whichList);// 在whichList的范围中查找x
}

template<typename HashEdObj>
inline bool
HashTable<HashEdObj>::remove(const HashEdObj &x) {
    auto &whichList = theLists[myhash(x)];
    auto itr = find(begin(whichList), end(whichList), x);

    if (itr == end(whichList))
        return false;

    whichList.erase(itr);
    --currentSize;
    return true;
}

template<typename HashEdObj>
inline bool
HashTable<HashEdObj>::insert(const HashEdObj &x) {
    auto &whichList = theLists[myhash(x)];

    if (find(begin(whichList), end(whichList), x) != end(whichList))
        return false;

    // 判断是否需要再散列
    if (++currentSize > theLists.size())
        rehash();

    return true;
}

template<typename HashEdObj>
inline bool
HashTable<HashEdObj>::insert(HashEdObj &&x) {
    auto &whichList = theLists[myhash(x)];

    if (find(begin(whichList), end(whichList), x) != end(whichList))
        return false;

    // 判断是否需要再散列
    if (++currentSize > theLists.size())
        rehash();

    return true;
}

#endif //HASHTABLE_HASHTABLE_H

开放定址法

将元素的关键字进行散列，根据散列，将元素保存到对应的位置（定址）；如果对应位置发生冲突，寻找空闲的位置保存（开放）

线性探测法

冲突解决方法：

：放置的位置

：冲突次数

根据散列探测表中的空闲位置，直接放置；发生冲突时查找下一个位置，如果下一个位置空闲则防止，否则继续查找下一个位置

对于一个较大且较空的表，也可能会存在这样一种情况：很多元素聚集在一些区块，称为一次聚集

例：插入{89，18，49，58，69}，冲突解决方法：

image-20210423163258104

平方探测法

冲突解决方法：

：放置的位置

：冲突次数

  1. 根据散列探测表中的空闲位置（此时冲突 ），如果成立则直接放置（）
  2. 发生冲突时查找下一个位置（冲突为 ），如果空闲，则根据 ，得到放置的位置是散列位置的下一个单元
  3. 如果再次冲突（冲突为 ），则查找 ，第四个位置，空闲则放置，得到放置的位置是散列位置后的第四个单元
  4. 再次冲突（冲突为 ），则查找 ，第九个位置，空闲则放置

例：插入{89，18，49，58，69}，冲突解决方法：

image-20210423164825751

再散列

当元素综述超过表的固定大小时，重置表，进行扩展，再将所有元素重新计算散列，存入相应位置

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename HashEdObj>
inline void
HashTable<HashEdObj>::rehash() {
    std::vector<std::list<HashEdObj>> oldLists = theLists;
    theLists.resize(nextPrime(2 * theLists.size()));
    for (auto &thisList:theLists)
        thisList.clear();

    currentSize = 0;
    for (auto &thisList:oldLists)
        for (auto &x:thisList)
            insert(std::move(x));
}