HashMap(python实现原理)

时间:2024-03-13 19:58:17

一、什么是字典?

字典是一堆key、value配对组成的元素的集合。字典是一个可变容器,可以存储任意类型对象。

 

二、字典是否是有序的?

在python3.6之前,字典是无序的,但是python3.7+,字典是有序的。在python3.7中,字典有序正式成为语言特性。

 

三、字典的各种操作时间复杂度?

字典的查询、添加、删除的平均时间复杂度都是O(1),相比列表与元组,性能更优。

 

四、字典的实现原理

1. python3.6及之前的版本

字典的底层是维护了一张哈希表,我们可以把哈希表看成一个二维数组,哈希表中的每一个元素又存储了哈希值(hash)、键(key)、值(value)3个元素。

enteies = [
    [\'--\', \'--\', \'--\'],
    [hash, key, value],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [hash, key, value],
]

 由上可见哈希表的存储结构,我们也可以看出,元素之间有一些空元素,我们通过增加一个元素来讲解具体实现。

  • 计算key的hash值【hash(key)】,在和mask做与操作【mask=字典的最小长度(DictMinSize)-1】,运算后会得到一个数字index,这个index就是要插入enteies哈希表中的下标位置。
  • 若index下标位置已经被占用,则会判断enteies的key是否与要插入的key相等。
  • 如果key已经存在,则更新vlaue值
  • 如果key不存在,就表示hash冲突,会继续向下寻找空位置

以上介绍了老字典的实现过程,下面我们带入具体的数值来介绍。

# 给字典添加一个值,key为hello, value为word
mydict[\'hello\'] = \'word\'

# 假设是一个空列表,hash表初始如下
enteies = [
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
]
注:以下计算值为假设值,不等于实际值
hash_value = hash(\'hallo\') # 假设值为12345
index = hash_value & (len(enteies) - 1) # 假设index值计算后等于3, 

# 下面会将值存在enteies中
enteies = [
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [12345, \'hello\', \'word\'],  # index=3
    [\'--\', \'--\', \'--\'],
]

# 我们继续向字典中添加值
my_dict[\'color\'] = \'green\'

hash_value = hash(\'color\')  # 假设值为 同样为12345
index = hash_value & ( len(enteies) - 1)  # 假设index值计算后同样等于3

# 下面会将值存在enteies中
enteies = [
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [\'--\', \'--\', \'--\'],
    [12345, \'hello\', \'word\'],  # 由于index=3的位置已经被占用,且key不一样,所以判定位hash冲突,继续向下寻找
    [12345, \'color\', \'green\'],  # 找到空余位置,则保存
]

上诉就是字典的插入过程,其实删除和查询也是差不多的方法。我们可以看到,不同的key计算出的index是不一样的,在enteies中插入的位置不一样,在entiese中插入的位置就不一样,所以我们在遍历字典的时候,字典的顺序与我们插入的顺序是不一样的。

我们可以发现,enteies表是稀疏的,随着我们插入的值不同,表会越来越稀疏(hash表也是一个会动态扩展长度的,每一次扩展,都会重新计算所有的key和hash值),所以新的字典的实现就出现了。

2. python3.7+后的新实现方法

老版的字典使用一张hash表,新字典在此基础上,再使用了一张新的indices表来辅助。

indices = [None, None, index, None, index, None, index]
enteies = [
    [hash0, key0, value0],
    [hash1, key1, value1],
    [hash2, key2, value2]
]

具体实现过程:

  • 计算key的hash值【hash(key)】,在和mask做与操作,运算后得到一个数字【index】,这个index就是要插入的indices的下标位置
  • 得到index后,会找到indices的位置,但是此位置不是存的hash值,hash值、key、value存在enteies表中,indices的index存到对应在enteies中存放数据的下标
  • 如果出现hash冲突,按照老字典的处理方式处理
# 给字典添加一个值,key为hello,value为word
my_dict[\'hello\'] = \'word\'

# 假设是一个空列表,hash表初始如下
indices = [None, None, None, None, None, None]
enteies = []

hash_value = hash(\'hello\')  # 假设值为 12343543
index = hash_value & ( len(indices) - 1) # 假设index值计算后等于3

# 会找到indices的index为3的位置,并插入enteies的长度
indices = [None, None, None, 0, None, None]
# 此时enteies会插入第一个元素
enteies = [
    [12343543, \'hello\', \'word\']
]

# 我们继续向字典中添加值
my_dict[\'haimeimei\'] = \'lihua\'

hash_value = hash(\'haimeimei\')  # 假设值为 34323545
index = hash_value & ( len(indices) - 1)  # 假设index值计算后等于 0

# 会找到indices的index为0的位置,并插入enteies的长度
indices = [1, None, None, 0, None, None]
# 此时enteies会插入第一个元素
enteies = [
    [12343543, \'hello\', \'word\'],
    [34323545, \'haimeimei\', \'lihua\']
]

 查询字典的具体过程:

# 下面是一个字典与字典的存储
more_dict = {\'name\': \'张三\', \'sex\': \'男\', \'age\': 10, \'birth\': \'2019-01-01\'}

# 数据实际存储
indices = [None, 2, None, 0, None, None, 1, None, 3]
enteies = [
    [34353243, \'name\', \'张三\'],
    [34354545, \'sex\', \'男\'],
    [23343199, \'age\', 10],
    [00956542, \'birth\', \'2019-01-01\'],
]

print(more_dict[\'age\'])  # 当我们执行这句时

hash_value = hash(\'age\')  # 假设值为 23343199
index = hash_value & ( len(indices) - 1)  # index = 1

entey_index = indices[1]  # 数据在enteies的位置是2
value = enteies[entey_index]  # 所以找到值为 enteies[2]

 由上可以看出,新字典存储数据的hash表并不会稀疏,由indices来维护具体存储的位置,enteies中的数据的顺序跟插入数据的前后是一样的,所以字典是有序的。

 

五、时间复杂度说明

我们在上面提到了,字典的平均时间复杂度是O(1),因为字典是通过哈希算法来实现的,哈希算法不可避免的问题就是hash冲突,Python字典发生哈希冲突时,会向下寻找空余位置,直到找到位置。如果在计算key的hash值时,如果一直找不到空余位置,则字典的时间复杂度就变成了O(n)了,所以Python的哈希算法就显得非常重要了。Python字典的哈希算法,会尽量保证哈希值计算出的index是平均分布且每一个值之间有剩余位置,例如:

[index, None, None, None, index, None, None, None]

 index尽量只为 0, 3, 5, 7类似值,保证在发生哈希冲突时,能很快的找到空余位置。

 

六、字典的key能使用什么值?

Python字典的key可以使用str, int, tuple等不变数据类型。因为字典是通过hash算法来计算key的值在进行字典操作的,所以key必须为可哈希的,list不能作为字典的key,因为list是可变的。

l1 = [1]
l2 = [1, 2]

test_d = {l1: \'1\', l2: \'2\'}

# 如果此时把l1.append(2),则字典的两个key hash出来的结果是一样的
那么字典该给你返回"1",还是"2"呢?
l1.append(2)

 字典的删除操作

对于删除操作,python会暂时对这个位置的元素,赋一个特殊的值,等到重新调整哈希表大小的时候,再将其删除

不难理解,哈希冲突的发生,往往会降低字典和集合操作的速度,因此,为了保证其高效性,字典内的哈希表,通常会保证至少留有1/3的剩余空间。随着元素不断插入,当剩余空间小于1/3时,python会重新获取更大的内存空间,扩充哈希表,不过,这种情况下,表内所有的元素位置会被重新排放

虽然哈希冲突和哈希表大小的调整,都会导致速度缓慢,但是这种情况发生的次数极少,所以,平均情况下,这仍能保证插入、查找和删除的时间复杂度都为O(1)

 

七、解决哈希冲突的方法

 1.开放寻址法:如果哈希函数计算出来的index位置已经有值,则可以向后探查新的位置来存储这个值。

  • 线性探查:如果位置i被占用,则探查i+1, i+2...
  • 二次探查:如果位置i被占用,则探查i+1^2, i-1^2, i+2^2,i-2^2..
  • 二度哈希:有n个哈希函数,当使用第一个hash函数h1发生冲突时,则尝试使用h2,h3..

2.拉链法:hash表每个位置都链接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后

拉链法解决hash冲突代码实现

# 链表类
class LinkList:
    class Node:
        def __init__(self, item=None):
            self.item = item
            self.next = None

    class LinkListIterator:
        def __init__(self, node):
            self.node = node

        def __next__(self):
            if self.node:
                cur_node = self.node
                self.node = cur_node.next
                return cur_node.item
            else:
                raise StopIteration

        def __iter__(self):
            return self

    def __init__(self, iterable=None):
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)

    def append(self, obj):
        s = LinkList.Node(obj)
        if not self.head:
            self.head = s
            self.tail = s
        else:
            self.tail.next = s
            self.tail = s

    def extend(self, iterable):
        for obj in iterable:
            self.append(obj)

    def find(self, obj):
        for n in self:
            if n == obj:
                return True
        else:
            return False

    def __iter__(self):
        return self.LinkListIterator(self.head)

    def __repr__(self):
        return "<<"+", ".join(map(str, self))+">>"


# 类似于集合的结构
class HashTable:
    def __init__(self, size=101):
        self.size = size
        self.T = [LinkList() for i in range(self.size)]

    def h(self, k):
        return k % self.size

    def insert(self, k):
        i = self.h(k)
        if self.find(k):
            print("Duplicated Insert")
        else:
            self.T[i].append(k)

    def find(self, k):
        i = self.h(k)
        return self.T[i].find(k)


ht = HashTable()

ht.insert(0)
ht.insert(1)
ht.insert(3)
ht.insert(102)
ht.insert(508)

print(",".join(map(str, ht.T)))
print(ht.find(203))

常见hash函数:

  • 除法哈希法:h(k) = k % m
  • 乘法哈希法
  • 全域哈希法