初识散列表

引子——散列思想

一个跑步比赛，选手编号为 051167,05 表示年级，中间 11 表示班级，最后两位 67表示编号。

那么我们怎么能快速查找到选手信息呢？

我们可以用基于数组的方式，截取后两位 67 映射数组下标，获取选手信息。现在我用 python 来实现一下：

"""
hash 思想，获取参赛选手的信息
051167 编号
"""


class Plays(object):
    def __init__(self, name, age, num, grade, cls, project):
        self.name = name
        self.age = age
        self.num = num
        self.grade = grade
        self.cls = cls
        self.project = project

    def get_no(self):
        player_no = self.grade + self.cls + self.num

        return player_no

    def __str__(self):
        return '这位选手的参赛信息为：\n' \
               '比赛项目：{}\n' \
               '班级：{}年级-{}班-学号{}\n' \
               '姓名：{}\n'.format(self.project, self.grade, self.cls, self.cls, self.name)


class HashTable(object):
    def __init__(self):
        self.cap = 100
        self.players = [None] * self.cap

    def hash_func(self):
        pass

    def hash_insert(self, no, item):
        index = int(no[-2:])
        self.players[index] = item

    def get(self, no):
        index = int(no[-2:])
        return self.players[index]


if __name__ == '__main__':
    xiaowang = Plays(name='小王', age='12', num='67', grade='05', cls='11', project='100m')
    xiaoli = Plays(name='小李', age='12', num='01', grade='05', cls='11', project='100m')
    h = HashTable()
    print(xiaowang.get_no(), xiaoli.get_no())
    h.hash_insert(xiaowang.get_no(), xiaowang)
    h.hash_insert(xiaoli.get_no(), xiaoli)
    print(h.get(xiaowang.get_no()))
    print(h.get(xiaoli.get_no()))

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

什么是散列表?

散列表——最有用的基本数据结构之一

散列表用的是数组支持按照下表随机访问数据的特性，所以散列表其实就数组的一种扩展，由数组演化而来。可以说，如果没有数组就没有散列表

散列表（hash table）实则是由散列函数和数组组成。

散列表的两个核心问题就是：散列函数设计和散列冲突解决

常见的哈希算法：MD5，SHA， CRC

散列函数

散列函数的特性：

• 散列函数计算得到的散列值是一个非负整数

• 它必须是一致的。每次对于相同的输入，都会得到相同的输入

  如果 key1 = key2, 那么 hash(key1) == hash(key2)

• 它将不同的输入映射到不同的输出。

  如果 key2 != key2, 那么 hash(key1) != hash(key2)

散列函数的查找：

• 散列函数总是将同样的输入映射到相同的索引
• 散列函数将不同的输入映射到不同的索引
• 散列函数知道数组有多大，值返回有效的索引

散列函数的应用

• 用于查找

​ 特定的映射关系

• 防止重复

​ 哈希表的 key 是唯一的，对于相同的 key，写入的值都将是覆盖的过程

• 用作缓存

​ web 网站的缓存，对于同一个页面的请求，其返回的网页可以利用 key-value 的形式进行缓存。

哈希冲突

理论上来说，散列函数总是将不同的键映射到数组的不同位置

实际上，这是不严谨的

实际上的情况可能是，对于同一个位置可能存储这不同的 value 值。

若两个 key 映射到了同一位置，就在这个位置存储一个链表。

因此：

• 散列函数很重要，理想的情况是散列函数将键均匀地映射到散列表的不同位置
• 如果散列表存储的链表很长，散列表的速度将急剧下降

常用的哈希冲突解决办法

• 开发寻址法

  开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入

• 二次探测

  二次探测是基于线性探测的，线性探测每次探测的步长为 1， 那它探测的下标序列就是 hash(key)+0, hash(key)+1, hash(key)+2…

  二次探测的步长就变成了线性探测的二次方——hash(key) + 0, hash(key)+1^2 …

• 双重散列，意思就是不仅是用一个散列函数。我们使用一组散列函数：hash1(key), hash2(key), hash3(key)…依次计算，若计算得到的存储位置已经被占用了，再使用第二个散列函数，依次类推，直到找到空闲的存储位置。

• 链表法

  

填装因子

散列表的填装因子计算

当填装因子大于 1 时，意味着 key 数量超过了数组位置。

因此，一旦填装因子开始增大，你就需要在散列表中添加位置，需要调整长度

经验论而言，一旦填装因子大于 0.7 ，就调整散列表的长度。

性能

散列表的查找速度为 O(1)

在平均情况下，散列表的查找速度与数组一样快，而插入和删除速度与链表一样快，因此它兼具两者的优点。

为避免冲突：

• 需要具备较低的填装因子；
• 良好的散列函数；