CosmosNing的个人博客

探索·好奇

0%

高效的数据结构——哈希表

发表于 更新于 分类于
本文字数： 5.8k 阅读时长 ≈ 5 分钟
哈希表是一个十分高效的数据结构，它到底高效在哪里呢？
cover

引入

在编程过程中，我们经常会遇到多组一一对应的数据（比如，通讯录中的姓名和电话号码），如何存储这些数据，同时能获得较高的数据操作效率呢？

下面，我们以通讯录中的存储为例进行简单的讨论。

首先，我们会想到利用数组来存储这些数据，一个数组用于存储姓名，另一个数组用于存储电话号码。单单两个数组并不能完成数据中一一对应的要求，因而需要我们自己书写其中的对应关系。

一一对应的关系可以由这样一个映射关系 \(f\) 来描述：\(f : a → b\) 。这个映射关系意味着一个确定的 \(a\) 的值，能够找到与之对应的 \(b\) 。在这里，我们通常把 \(a\) 称作“关键字”（ \(Key\) ），而与之对应的 \(b\) 称作“值”（ \(Value\) ）。对于我们的通讯录例子，因为我们经常需要按人名查找其电话号码，所以我们可以将姓名当作关键词，将电话号码当作值。

数组利用整数作为下标来取用任意位置元素的值，类似的，我们也希望上面所描述的对应关系能够利用关键字来取用对应的值。这种想法怎样实现呢？基于数组这种结构，我们可以对它进行简单的扩展，来实现这种想法。数组下标是整数，而关键字通常是字符串，所以我们要写一个转换函数，它能够将一个字符串映射到自然数域中。举个例子，比如有一个叫做“小明”的人，我利用这个转换函数将“小明”转换成数字 1 ，此时将小明的姓名和电话号码存储在各自数组下标为 1 的位置即可。这种存储方式，就是一种简单的哈希表，其中的字符串转换为数字函数称为哈希函数。

很多高级语言本身内置了类似哈希表的数据类型，可以直接使用。比如Python中，字典（Dict）就是哈希表。哈希表在每种语言中的使用在各类语言教程中已经有了很好的示例，这里不再介绍。而我们要探讨的便是分析一下哈希表中存在的问题、它的性能和一些典型应用。

哈希冲突

经过上述的一些讨论，我们可以发现，哈希表有两个集合和一个函数组成。两个集合分别是关键字集合和值集合，而一个函数则为哈希函数（用于维护关键字到值存储位置的关系）。两个集合的存储可以很容易利用数组实现，从而问题的关键便转向了哈希函数的设计。

构造一个从字符串映射到数字的函数很简单，但是随手设计的哈希函数有时却会产生问题。我们来看一个典型的例子。比如我把哈希函数定义为取字符串的长度，并以此输出结果作为信息存储位置。同时，我有待存储的信息：（小明，12345678910）、（小刚，01987654321）。首先，存储小明的信息。假设一个汉字的字符长度为1，那么“小明”字符长度为2，应该存储在下标为2的位置上。接着存储小刚的信息，此时我们发现，根据给定的哈希函数，小刚的信息也应该存储的在下标为 2 的位置。这种情况下，存储位置就产生了冲突。在哈希表中，这种冲突称作“哈希冲突”。

那么，如何解决哈希冲突呢？一种做法在原有的存储结构上修改：比如在数组对应位置新串接一个链表，存储新的数据；此外，也可以在冲突位置的附近数据为空的位置存储新的信息。二是重新设计哈希函数，使它出现冲突的情况尽可能得少。

要构造一个较好的哈希函数，首先它必须满足以下基本的三个条件：

第一点， 一致性。相同的字符串输入，能够获得相同的数字输出；

第二点， 互异性。不同的字符串输入，获得的数字输出尽量不同；

第三点， 合理性。哈希函数的输出值大小必须在表存储容量的范围之内，保证得到的下标的合理性。比如容量为10的哈希表，对应的哈希函数不能返回100这样的数值。

哈希函数构造方法有很多，大家可以自己去看看，我这里就不过多阐述了。

性能分析

哈希表继承了数组高效获取任意元素的特质，在常数时间内即可完成对任意元素的访问。同时在增添和删除也有十分好的表现。由于哈希表的信息存储并不是像数组一样按照顺序依次存储，而是依据哈希函数确定存储位置，所以增添和删除元素不需要做十分耗费时间的移动操作，因而在哈希表中，增添和删除操作也可以在常数时间内完成。

典型应用

基于哈希表的特性，实际编程中有以下两种应用。第一种，用于建立信息相关的两组数据的联系，方便由一组数据的信息快速查找到它对应的信息。之前的通讯录例子便是这一类的具体应用。第二种，用于过滤重复的信息。有哈希函数的特性可知，不同的关键字对应不同的存储位置，相同的关键字对应相同的位置。我们可以在对应位置存储一个标记信息，用来判断该关键字是新增的还是之前出现过的。利用哈希表这种结构，我们就可以很方便地过滤掉重复的信息。

文章的最后，我们简单总结一下本文的内容：

  1. 哈希表是一种十分高效的数据结构，它通常可以在常数时间内完成对元素的插入、删除和访问。

  2. 哈希表内部通常有两个集合和一个函数。两个集合分别是关键字集合和值集合，而一个函数则为哈希函数（用于维护关键字到值存储位置的关系）。

  3. 哈希表的效率受哈希函数影响，不恰当的哈希函数会造成哈希冲突，造成哈希表效率的下降。

  4. 一个哈希函数通常有以下三个特点：

    第一点，一致性。相同的字符串输入，能够获得相同的数字输出；

    第二点，互异性。不同的字符串输入，获得的数字输出尽量不同；

    第三点，合理性。哈希函数的输出值大小必须在表存储容量的范围之内，保证得到的下标的合理性。比如容量为10的哈希表，对应的哈希函数不能返回100这样的数值。

  5. 利用哈希表可以很容易存储两个联系十分紧密的数据，同时也可以过滤掉重复的信息。

附录：哈希表的简单实现

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
class HashTable(object):
    """
    哈希表类：
      用于创建哈希表
    参数：
      size：哈希表的容量大小
    属性：
      keys：哈希表的关键字集合
      values：哈希表的值集合
      items：哈希表的关键字集合和哈希表的值集合组成的一个元组
    静态变量：
      UNUSED：用于标记某一存储位置是否被使用，其值为None
      DEFAULTSIZE：默认哈希表容量，值为32
    """
    UNUSED = None
    DEFAULTSIZE = 32

    def __init__(self, size=DEFAULTSIZE):
        self.__keys = [HashTable.UNUSED] * size
        self.__values = [HashTable.UNUSED] * size
        self.__size = size
        self.__len = 0

    def delete(self, key):
        """
        删除哈希表中关键字为key的key和value。如果key不在哈希表中，那么将引起KeyError异常
        :param key:待删除的关键字
        :return:无
        """
        found, index = self.__find_index(key)

        if found:
            self.__keys[index] = HashTable.UNUSED
            self.__values[index] = HashTable.UNUSED
        else:
            raise KeyError("关键字不存在")

    def find(self, key):
        """
        在哈希表中查找关键字为key的值。如果找到，返回关键字对应的值；如果不存在，返回None
        :param key: 待查找的关键字
        :return: 关键字对应的值或者是None
        """
        found, index = self.__find_index(key)
        if found:
            return self.__values[index]
        else:
            return None

    def clear(self):
        """
        清空哈希表
        :return: 无
        """
        self.__keys = [HashTable.UNUSED] * HashTable.DEFAULTSIZE
        self.__values = [HashTable.UNUSED] * HashTable.DEFAULTSIZE
        self.__size = HashTable.DEFAULTSIZE
        self.__len = 0

    @property
    def keys(self):
        """
        获取所有关键字
        :return: 一个包含哈希表关键字集合的列表
        """
        return [key for key in self.__keys if key is not HashTable.UNUSED]

    @property
    def values(self):
        """
        获取所有值
        :return: 一个包含哈希表值集合的列表
        """
        return [value for value in self.__values if value is not HashTable.UNUSED]

    @property
    def items(self):
        """
        获取所有关键字和值
        :return: 一个包含keys和values的元组
        """
        return self.keys, self.values

    @property
    def __load_factor(self):
        """
        装载因子，如果此值超过一定数值，需要重新申请新空间，重新做哈希操作
        :return: 返回当前装载因子的值
        """
        return float(self.__len / self.__size)

    def __getitem__(self, key):
        """
        重载[]运算符获取元素的方法
        :param key: 关键字
        :return: 关键字对应的值
        :raise:KeyError("关键字不存在")
        """
        assert self.__len > 0, "哈希表为空！"
        found, index = self.__find_index(key)

        if found:
            return self.__values[index]
        else:
            raise KeyError("关键字不存在")

    def __setitem__(self, key, value):
        """
        重载H[k] = v
        :param key: 关键字
        :param value: 值
        :return: 无
        """
        if self.__load_factor > 0.7:
            self.__rehash()

        found, index = self.__find_index(key)

        if found:
            self.__values[index] = value
        else:
            self.__len += 1
            self.__keys[index] = key
            self.__values[index] = value

    def __find_index(self, key):
        """
        计算或者是查找key存储的位置
        :param key: 关键字
        :return: (bool, int)。第一个返回值代表key是否在哈希表中，index代表key所在的位置（如果不在哈希表中，那么是新位置；否则是原来key的位置）
        """
        index = abs(hash(key)) % self.__size #利用python内置的hash函数计算下标

        while self.__keys[index] is not HashTable.UNUSED:
            if self.__keys[index] == key:
                return True, index
            else:
                index = (index + 1) % self.__size#处理哈希冲突，采用开放定址法

        return False, index

    def __rehash(self):
        """
        重新申请新的空间，存储数据
        :return:无
        """
        old_keys = self.keys
        old_values = self.values

        self.__size *= 2
        self.__len = 0
        self.__keys = [HashTable.UNUSED] * self.__size
        self.__values = [HashTable.UNUSED] * self.__size

        for i in range(len(old_keys)):
            key = old_keys[i]
            value = old_values[i]
            _, index = self.__find_index(key)
            self.__keys[index] = key
            self.__values[index] = value


if __name__ == "__main__":
    hash_table = HashTable(2)

    hash_table[100] = 56
    print(hash_table.keys, hash_table.values)
    hash_table[100] = 46
    print(hash_table.keys, hash_table.values)

    hash_table["aa"] = "44"
    print(hash_table.keys, hash_table.values)

    hash_table[1.44] = 666
    print(hash_table.keys, hash_table.values)

    print(hash_table[100])

    hash_table.delete("aa")

    print(hash_table.keys, hash_table.values)

    print(hash_table.find(444))

    hash_table.clear()

    print(hash_table.keys, hash_table.values)

"""
输出结果：
100] [56]
[100] [46]
[100, 'aa'] [46, '44']
[100, 1.44, 'aa'] [46, 666, '44']
46
[100, 1.44] [46, 666]
None
[] []
"""