[数据结构与算法]python hash及dict()实现原理

python hash及dict()实现原理

哈希（散列）

dict() 实现原理

ref

Python 中的哈希表：对字典的理解

Python之哈希表

hash 定义

力扣应用

note

哈希操作：

• $f(x)???>y$

  • $f()$：哈希函数
  • $y$：哈希值

• 单向不可逆

• 当不同$x$经过哈希操作后得到了相同的哈希值$y$，则叫做冲突

  解决冲突：

  • open addressing 开放寻址法
  • separate chaining 链地址法

哈系表：

• 一种存储键值对数据的数据结构
• 通过$key$的哈希操作得到$value$
• 查找哈希表的花费时间与哈希表存储的数据多少无关

python dict实现原理：

Python字典dict实现原理

哈希表结构：

entries = [
    ['--', '--', '--'],
    [hash, key, value],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [hash, key, value],
]

大致流程：

• 通过$key$的哈希操作得到哈希值$hash$
• 将$hash$与len(entries)-1(哈希表的长度减一)相与，得到存储下标$index$
  • 改进如下：
    • 也可以增加一个index_list列表，用于记录数据在哈希表中的下标
      • 将$hash$与len(entries)-1(哈希表的长度减一)相与，得到存储下标$index$，在index位置存入当前的len(entries)，相当于记录在哈希表中数据的下标
    • 将哈希表的稀疏性转接到index_list列表，节省空间
• 存入数据
• 动态扩展哈希表时，所有的hash重新计算并重新存储

总结：

• 老算法：
  • 只维护一张哈希表
  • 表稀疏浪费空间
• 新算法
  • 增加一个index_list列表
  • 将哈希表的稀疏性转接到index_list列表，节省空间