2022年 11月 3日

Python数据结构：哈希表

哈希

散列（哈希）是电脑科学中一种对资料的处理方法，通过某种特定的函数/算法（称为散列函数/算法）将要检索的项与用来检索的索引（称为散列，或者散列值）关联起来，生成一种便于搜索的数据结构（称为散列表）。

哈希表是什么

哈希表（散列表）是根据键（Key）直接访问内存存储位置的数据结构。根据键（Key）值将数据映射到内存中一个位置的函数称为哈希函数，根据哈希函数建立的记录数据的表称为哈希表。

哈希表的特点

  • 若关键字为 ，则其值存放在的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系  为散列函数，按这个思想建立的表为散列表。

  • 对不同的关键字可能得到同一散列地址，即 ，而 ，这种现象称为冲突。

  • 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

处理冲突

开放定址法

开放定址法就是产生冲突之后去寻找下一个空闲的空间。函数定义为：

其中，hash(key) 是哈希函数， 是增量序列， 为已冲突的次数。

  • 线性探测法：，或者其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，然后放置在该单元。

  • 平方探测法：

链表法

这是另外一种类型解决冲突的办法，散列到同一位置的元素，不是继续往下探测，而是在这个位置是一个链表，这些元素则都放到这一个链表上。

再散列

如果一次不够，就再来一次，直到冲突不再发生。

建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表(注意：在这个方法里面是把元素分开两个表来存储)。

哈希表的应用

  • 查字典

  • 网络防火墙中，根据源IP，目的IP，源端口，目的端口，协议号构成的五元组来标识一条网络数据流的，并且根据五元组来建立会话表项(session entry)。为了查找便捷，一般都使用Hash表来实现这个会话表，以提高转发的效率。

  • Linux 内核大量采用哈希表

下面用开放地址法（线性探测）实现了一个简单的哈希表。仔细阅读后试试哈希表的各种操作，感受以下哈希表飞一般的速度吧！

代码段 1

  1. class Hash:
  2.     # 表的长度定位11
  3.     def __init__(self):
  4.         self.hash_table=[[None,None]for i in range(11)]
  5.     
  6.     # 散列函数
  7.     def hash(self,k,i):
  8.         h_value=(k+i)%11
  9.         if self.hash_table[h_value][0]==k:
  10.             return h_value
  11.         if self.hash_table[h_value][0]!=None:
  12.             i+=1
  13.             h_value=self.hash(k,i)
  14.         return h_value
  15.     
  16.     def put(self,k,v):
  17.         hash_v=self.hash(k,0)
  18.         self.hash_table[hash_v][0]=k
  19.         self.hash_table[hash_v][1]=v
  20.  
  21.     def get(self,k):
  22.         hash_v=self.hash(k,0)
  23.         return self.hash_table[hash_v][1]
  24.  
  25. hash = Hash()
  26. hash.put(1 ,'wang')
  27. print(hash.get(1))

上述代码实现了一个简单的哈希表，但表的长度只有11，填入表中元素越来越多后，产生冲突的可能性会越来越大。

由此引出另一个概念，叫做载荷因子（load factor）。载荷因子的定义为：

所以当达到一定程度后，表的长度要变的，载荷因子被设计为0.75；超过0.8，cpu 的cache missing 会急剧上升。即需要新定义一个 resize 函数扩大表的长度，一般选择扩到已插入元素数量的两倍。

在上述代码中重新升级我们的 Hash 吧！示例代码代码段2中。

代码段 2

  1. class Map:
  2.     def __init__(self):
  3.         self.capacity=11
  4.         self.hash_table=[[None,None]for i in range(self.capacity)]
  5.         self.num=0
  6.         self.load_factor=0.75
  7.     
  8.     def hash(self,k,i):
  9.         h_value=(k+i)%self.capacity
  10.         if self.hash_table[h_value][0]==k:
  11.             return h_value
  12.         if self.hash_table[h_value][0]!=None:
  13.             i+=1
  14.             h_value=self.hash(k,i)
  15.         return h_value
  16.  
  17.     def resize(self):
  18.          #扩容到原有元素数量的两倍
  19.         self.capacity=self.num*2
  20.         temp=self.hash_table[:]
  21.         self.hash_table=[[None,None]for i in range(self.capacity)] 
  22.         for i in temp:
  23.              #把原来已有的元素存入
  24.             if(i[0]!=None):
  25.                 hash_v=self.hash(i[0],0)
  26.                 self.hash_table[hash_v][0]=i[0]
  27.                 self.hash_table[hash_v][1]=i[1]
  28.  
  29.     def put(self,k,v):
  30.         hash_v=self.hash(k,0)
  31.         self.hash_table[hash_v][0]=k
  32.         self.hash_table[hash_v][1]=v
  33.         #暂不考虑key重复的情况，具体自己可以优化
  34.         self.num+=1
  35.         # 如果比例大于载荷因子
  36.         if(self.num/len(self.hash_table)>self.load_factor):
  37.             self.resize()
  38.  
  39.     def get(self,k):
  40.         hash_v=self.hash(k,0)
  41.         return self.hash_table[hash_v][1]

经典实践

Python 中的字典就是用哈希表来实现的，它的特点如下：

  • 字典的每个键值 key=>value 对用冒号 : 分割，每个键值对之间用逗号 , 分割，整个字典包括在花括号 {} 中 ,格式：dict = {key1 : value1, key2 : value2 }

  • 通过中括号访问，添加，更新元素

  1. dictionary = {'name': 'wang', 'age': 17, 'class': 'first'}
  2. dictionary['age'] = 18
  3. dictionary['country'] = 'china'
  4. print(dictionary['age'])
  5. print(dictionary['country'])

根据 Python 中的字典特性，自己手动实现一个 Python 字典吧

  1. class MyDictionary(object):
  2.     # 字典类的初始化
  3.     def __init__(self):
  4.         self.table_size = 13 # 哈希表的大小
  5.         self.key_list = [None]*self.table_size #用以存储key的列表
  6.         self.value_list = [None]*self.table_size #用以存储value的列表
  7.     
  8.     # 散列函数，返回散列值
  9.     # key为需要计算的key
  10.     def hashfuction(self, key):
  11.         count_char = 0
  12.         key_string = str(key)
  13.         for key_char in key_string: # 计算key所有字符的ASCII值的和
  14.             count_char += ord(key_char) # ord()函数用于求ASCII值
  15.         length = len(str(count_char))
  16.         if length > 3 : # 当和的位数大于3时，使用平方取中法，保留中间3位
  17.             mid_int = 100*int((str(count_char)[length//2-1])) \
  18.                     + 10*int((str(count_char)[length//2])) \
  19.                     + 1*int((str(count_char)[length//2+1]))
  20.         else: # 当和的位数小于等于3时，全部保留
  21.             mid_int = count_char
  22.             
  23.         return mid_int%self.table_size # 取余数作为散列值返回
  24.         
  25.     # 重新散列函数，返回新的散列值
  26.     # hash_value为旧的散列值
  27.     def rehash(self, hash_value):
  28.         return (hash_value+3)%self.table_size #向前间隔为3的线性探测
  29.         
  30.     # 存放键值对
  31.     def __setitem__(self, key, value):
  32.         hash_value = self.hashfuction(key) #计算哈希值
  33.         if None == self.key_list[hash_value]: #哈希值处为空位，则可以放置键值对
  34.             pass
  35.         elif key == self.key_list[hash_value]: #哈希值处不为空，旧键值对与新键值对的key值相同，则作为更新，可以放置键值对
  36.             pass
  37.         else: #哈希值处不为空，key值也不同，即发生了“冲突”，则利用重新散列函数继续探测，直到找到空位
  38.             hash_value = self.rehash(hash_value) # 重新散列
  39.             while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然不能插入键值对，重新散列
  40.                 hash_value = self.rehash(hash_value) # 重新散列
  41.         #放置键值对      
  42.         self.key_list[hash_value] = key
  43.         self.value_list[hash_value] = value
  44.  
  45.     # 根据key取得value
  46.     def __getitem__(self, key):
  47.         hash_value = self.hashfuction(key) #计算哈希值
  48.         first_hash = hash_value #记录最初的哈希值，作为重新散列探测的停止条件
  49.         if None == self.key_list[hash_value]: #哈希值处为空位，则不存在该键值对
  50.             return None
  51.         elif key == self.key_list[hash_value]: #哈希值处不为空，key值与寻找中的key值相同，则返回相应的value值
  52.             return self.value_list[hash_value]
  53.         else: #哈希值处不为空，key值也不同，即发生了“冲突”，则利用重新散列函数继续探测，直到找到空位或相同的key值
  54.             hash_value = self.rehash(hash_value) # 重新散列
  55.             while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然没有找到，重新散列
  56.                 hash_value = self.rehash(hash_value) # 重新散列
  57.                 if hash_value == first_hash: #哈希值探测重回起点，判断为无法找到了
  58.                     return None
  59.             #结束了while循环，意味着找到了空位或相同的key值
  60.             if None == self.key_list[hash_value]: #哈希值处为空位，则不存在该键值对
  61.                 return None
  62.             else: #哈希值处不为空，key值与寻找中的key值相同，则返回相应的value值
  63.                 return self.value_list[hash_value]
  64.     
  65.     # 删除键值对
  66.     def __delitem__(self, key):
  67.         hash_value = self.hashfuction(key) #计算哈希值
  68.         first_hash = hash_value #记录最初的哈希值，作为重新散列探测的停止条件
  69.         if None == self.key_list[hash_value]: #哈希值处为空位，则不存在该键值对，无需删除
  70.             return
  71.         elif key == self.key_list[hash_value]: #哈希值处不为空，key值与寻找中的key值相同，则删除
  72.             self.key_list[hash_value] = None
  73.             self.value_list[hash_value] = None
  74.             return
  75.         else: #哈希值处不为空，key值也不同，即发生了“冲突”，则利用重新散列函数继续探测，直到找到空位或相同的key值
  76.             hash_value = self.rehash(hash_value) # 重新散列
  77.             while (None != self.key_list[hash_value]) and (key != self.key_list[hash_value]): #依然没有找到，重新散列
  78.                 hash_value = self.rehash(hash_value) # 重新散列
  79.                 if hash_value == first_hash: #哈希值探测重回起点，判断为无法找到了
  80.                     return
  81.             #结束了while循环，意味着找到了空位或相同的key值
  82.             if None == self.key_list[hash_value]: #哈希值处为空位，则不存在该键值对
  83.                 return
  84.             else: #哈希值处不为空，key值与寻找中的key值相同，则删除
  85.                 self.key_list[hash_value] = None
  86.                 self.value_list[hash_value] = None
  87.                 return
  88.     
  89.     # 返回字典的长度
  90.     def __len__(self):
  91.         count = 0
  92.         for key in self.key_list:
  93.             if key != None:
  94.                 count += 1
  95.         return count
  96.  
  97. def main():
  98.     H = MyDictionary()
  99.     H["kcat"]="cat"
  100.     H["kdog"]="dog"
  101.     H["klion"]="lion"
  102.     H["ktiger"]="tiger"
  103.     H["kbird"]="bird"
  104.     H["kcow"]="cow"
  105.     H["kgoat"]="goat"
  106.     H["pig"]="pig"
  107.     H["chicken"]="chicken"
  108.     print("字典的长度为%d"%len(H))
  109.     print("键 %s 的值为为 %s"%("kcow",H["kcow"]))
  110.     print("字典的长度为%d"%len(H))
  111.     print("键 %s 的值为为 %s"%("kmonkey",H["kmonkey"]))
  112.     print("字典的长度为%d"%len(H))
  113.     del H["klion"]
  114.     print("字典的长度为%d"%len(H))
  115.     print(H.key_list)
  116.     print(H.value_list)
  117.     
  118. if __name__ == "__main__":
  119.     main()

最近我花费了几天的时间，整理了1份理论+实践的Python入门进阶教程，这或许是你见过非常好的一份学习资料之一。独家打造、完全免费，需要的同学可以关注gzh【Python编程学习圈】，发送“学习资料”获取~