devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

python版数据结构9、哈希表_python创建哈希表

作者：我家小花儿 | 2024-07-12 01:17:02

赞

踩

python创建哈希表

​​​​​​

  • 目录

    概述

    哈希表的设计

    节点类

    哈希表

    ​编辑

    变量

    操作

    哈希算法

    查getKey

    增add

    删remove

    改update

    遍历哈希表/哈希码链表travel

    扩容/收缩expand/contract

    思考

    为什么计算索引位置用hash&（数组长度-1），而不是hash%数组长度？

    为什么扩容大小为原来的一倍？

    为什么旧链表会这样拆分？

    为什么拆分后的链表要这么放？

    为什么要设置哨兵节点？

    哈希算法

    python实现哈希表

  • 概述

    • 给每份数据分配一个编号，放入表格（数组）
    • 建立编号与数组索引的关系，将来可以通过编号快速查找
    • 有限长度的数组，无法存储大量的数据，因此可以用链表的方式存储数据
    • 作用
      • 用来存储数据量超大的键值对数据，减少存储空间

  • 哈希表的设计

    • 节点类

      • 键
        • 可以超过大类的类别数
        • 比如类别数为8，键可以取到100
        • 唯一
      • 值
      • next

    • 哈希表

      • 变量

        • 默认空数组
        • 哈希表的大小
        • 哈希表的扩容因子，超过阈值需要进行倍增扩容

      • 操作

        • 哈希算法
          • 用按位与运算&将key转换为哈希码
          • key&（n-1），其中，n为哈希表长度，要求n必须为2的n次方
        • 查getKey
          • 根据key值查找value
          • O(m)，m为哈希码链表长度
        • 增add
          • 增加元素有两种情况，key唯一
            • 如果key存在，则不增加，只更新value
            • 如果key不存在，则新增元素到指定哈希码链表的末尾
          • O(m)，m为哈希码链表的长度
          • 增加元素之后，需要进行扩容判断
        • 删remove
          • 根据key删除元素，并返回删除元素的value
          • 删除元素后需要进行收缩判断
          • 时间复杂度：O(M)
        • 改update
          • 根据key修改对应的value
          • 时间复杂度：O(M)
        • 遍历哈希表/哈希码链表travel
          • 时间复杂度：O(N*M)
        • 扩容/收缩expand/contract
          • 哈希表元素超过或小于阈值时进行扩容/收缩。
          • 扩容/收缩因子a，a=\frac{n}{m}a=nma=\frac{n}{m}a=mn​
            • n代表哈希表的元素数
            • m代表哈希表的长度
            • 一般扩容因子a为0.75
          • 扩容后的长度为原来的一倍，收缩后的长度为原来的1/2
          • 扩容/收缩后元素都需要进行重排，重拍方式如下
            • 扩容重排
              • 每一个链表最多拆成两个
                • 元素的哈希值和旧数组的长度进行按位与运算
                • 等于0和不等于0的各自为一组
              • 拆分后链表放置的位置
                • 一个链表保持不动，另一个链表原索引位置+旧哈希表长度
            • 收缩重排
              • 第[i]个哈希码链表和第[i+收缩后的哈希表长度]个哈希码链表进行组合
              • 第[i+收缩后的哈希表长度]个哈希码链表连接到第i个哈希码链表的尾端
          • 时间复杂度：O(n*m)
            • n为哈希表的长度
            • m为哈希码链表的长度

    • 思考

      • 为什么计算索引位置用hash&（数组长度-1），而不是hash%数组长度？

        • 首先，前两者等价。它们有共同前提：数组长度是2的n次方
        • 10进制中，某个数x对10/100/1000，也就是10^1/10^2/10^3，取余数时，余数就是x的后1/2/3位
        • 同理，2进制中，某个数y对2/4/8，也就是2^1/2^2/2^3，取余数时，余数就是y的后1/2/3位
        • 为了达到这种效果，可以使用按位与运算
        • 当数组长度是2的n次方的时候，hash和数组长度-1进行按位与运算的时候，就相当于只保留hash的后n位，也就是余数。
        • 比如，数组长度为8=2^3，hash=13（ 0000 1101），7=0000 0111，则hash&7=0000 0101=5

      • 为什么扩容大小为原来的一倍？

        • 这样能保证扩容之后的大小还符合2^n，可以直接用按位与运算来计算余数，或者说，任意hash，可以通过其二进制的后n位直接获得索引位置，大大降低计算复杂度。

      • 为什么旧链表会这样拆分？

        • 旧数组的长度2^n换算成二进制后，首个1在倒数第n位，则任意hash值的后n-1位为索引位置
        • 旧链表的hash值和旧数组长度进行按位与运算之后，可以分为两部分，一部分元素的hash的第n位不变，依旧为0，一部分元素的hash值第n位变成了1，因此旧链表可以分为两组

      • 为什么拆分后的链表要这么放？

        • 由于扩容了一倍，所以通过hash值求索引的位数增加了一位，因此，按位与运算之后，hash值第n位为0的新链表索引不变，hash值第n位变成1的新元素的索引要加上旧链表的长度，也就是2^n。（新哈希表长度为2^(n+1)）

      • 为什么要设置哨兵节点？

        • 哨兵节点可以将头节点的操作和非头节点的操作一致化，不同特殊处理头节点了

  • 哈希算法

    • 生成哈希码的算法，也叫摘要算法，散列算法
    • 作用：将任意长的数据通过哈希算法变成固定长度，就是hash值
    • hash算法被广泛应用于数据完整性校验和加密等方面
    • 常见的hash算法
      • MDS,SHA1,SHA256,（常用）CRC32
    • 字符串的hash算法

  • python实现哈希表

    1. # 哈希表链表实现：哈希表为顺序表，哈希码为链表
    2. # 节点类
    3. class Node:
    4.     def __init__(self, key, value):
    5.         self.key = key  # 键
    6.         self.value = value  # 值
    7.         self.next = None  # next
    8.  
    9.  
    10. class Hash:
    11.     def __init__(self, n: int, factor: float = 0.75):
    12.         """
    13.         :param n: 哈希表的初始大小，要求n为2的n次方
    14.         :param factor: 哈希表的扩容因子
    15.         """
    16.         # 要求n为2的n次方
    17.         while n % 2 != 0:
    18.             n = int(input('n不是2的n次方，不满足要求，请重新设置哈希表的长度：n='))
    19.         # 构造空的哈希表，列表的索引代表哈希码，初始键为-1，代表该哈希码下没有元素
    20.         # 给每个哈希码链表构造一个哨兵节点
    21.         self.table = []
    22.         self.create(n)
    23.         self.num = 0  # 哈希表的元素个数，静态变量
    24.         self.factor = factor  # 哈希表的扩容因子
    25.  
    26.     def create(self, n):
    27.         """
    28.         哈希表扩容/创建哈希表,O(N)
    29.         :param n: 哈希表大小/哈希表新增长度
    30.         """
    31.         for _ in range(n):
    32.             node = Node(-1, -1)
    33.             self.table.append(node)
    34.  
    35.     def getLength(self):
    36.         # 获得哈希表的长度
    37.         return len(self.table)
    38.  
    39.     def getExpandThread(self):
    40.         # 获得哈希表的扩容阈值
    41.         return self.factor * self.getLength()
    42.  
    43.     def getContractThread(self):
    44.         # 获得哈希表的收缩阈值
    45.         return (1-self.factor) * self.getLength()
    46.  
    47.     def getHashCode(self, key):  # 此处为哈希算法
    48.         # 哈希算法，将键映射为哈希码,O(1)
    49.         length = self.getLength()
    50.         # 按位与运算&获得哈希码，也就是哈希表的索引
    51.         hashCode = key & (length-1)  # 等价于key%length，但是&比%更高效
    52.         return hashCode
    53.  
    54.     def expand(self):
    55.         # 哈希表扩容,长度倍增,阈值改变,o(n*m)
    56.         length = self.getLength()
    57.         self.create(length)  # O(N)
    58.         print(f'------元素个数：{self.num}>=阈值：{length*self.factor}，需要扩容:{length}->{self.getLength()}------')
    59.         # 元素重分配,O(N*M)
    60.         for t in range(length):  # O(N)
    61.             head = self.table[t]
    62.             if head.next is None or head.next.next is None:
    63.                 continue
    64.             print(f'哈希码链表元素重分配，hash={t}:')
    65.             aHead = Node(-1, -1)
    66.             bHead = Node(-1, -1)
    67.             pa = aHead
    68.             pb = bHead
    69.             while head.next:  # O(M)
    70.                 head = head.next
    71.                 flag = head.key & length
    72.                 if flag == 0:
    73.                     pa.next = head
    74.                     pa = head
    75.                 else:
    76.                     pb.next = head
    77.                     pb = head
    78.             if aHead.next:
    79.                 pa.next = None
    80.                 self.table[t] = aHead
    81.                 self.travel(t)
    82.             if bHead.next:
    83.                 pb.next = None
    84.                 self.table[t+length] = bHead
    85.                 self.travel(t+length)
    86.  
    87.     def contract(self):
    88.         # 删除元素之后，判断是否收缩哈希表
    89.         length = self.getLength()
    90.         print(f'------元素个数：{self.num}<=阈值：{length * (1-self.factor)}，需要收缩哈希表:{length}->{length/2}------')
    91.         newLength = int(length/2)
    92.         # 元素重分配
    93.         for t in range(newLength):  # O(N)
    94.             if self.table[t+newLength].next:
    95.                 head = self.table[t]
    96.                 while head.next:
    97.                     head = head.next
    98.                 head.next = self.table[t+newLength].next
    99.         self.table = self.table[:newLength]
    100.  
    101.     def travel(self, hashCode=-1):
    102.         if hashCode == -1:  # 遍历哈希表,O(NxM)
    103.             print('----------travel table start------------')
    104.             for i in range(self.getLength()):  # O(N)
    105.                 head = self.table[i]
    106.                 if head.next:
    107.                     print('hash=', i)
    108.                 while head.next:  # O(M)
    109.                     head = head.next
    110.                     print(head.key, head.value)
    111.             print('----------travel table end------------')
    112.         else:
    113.             # 遍历哈希码链表，O(M)
    114.             print(f'----------travel hash={hashCode} start------------')
    115.             if hashCode < 0 or hashCode >= self.getLength():
    116.                 print('输入的哈希码错误，可输入范围应为：0-', self.getLength()-1)
    117.                 return
    118.             head = self.table[hashCode]
    119.             while head.next:
    120.                 head = head.next
    121.                 print(head.key, head.value)
    122.             print(f'----------travel hash={hashCode} end------------')
    123.  
    124.     def remove(self, key):
    125.         # 根据key值删除元素，并返回删除元素的value
    126.         # 1、找key对应的哈希码
    127.         hashCode = self.getHashCode(key)
    128.         # 2、删除元素
    129.         head = self.table[hashCode]
    130.         while head.next and head.next.key != key:
    131.             head = head.next
    132.         # 退出循环时，如果key存在，则head指向待删除结点的前一个结点，如果key不存在，则head指向尾节点
    133.         value = None
    134.         if head.next:  # 如果key存在,则head.next一定不为空
    135.             value = head.next.value
    136.             head.next = head.next.next
    137.             print('remove：key存在，删除元素：', key, value)
    138.             self.num -= 1
    139.             if self.num <= self.getContractThread():
    140.                 self.contract()
    141.         else:
    142.             print('remove: key不存在，无需删除')
    143.         return value
    144.  
    145.     def add(self, key, value):
    146.         # 如果key不重复，则新增；如果key重复，则更新，O(m),m为哈希码链表的长度
    147.         # 1、映射键为哈希码
    148.         hashCode = self.getHashCode(key)
    149.         # 2、添加到哈希码链表, O(m),m为哈希码链表的长度
    150.         # 由于存在哨兵节点，所以插入第一个元素的操作也不用特殊判断
    151.         cur = self.table[hashCode]
    152.         while cur.next:
    153.             cur = cur.next
    154.             if cur.key == key:  # 直接修改key对应的value，不作新增/扩容，因为key唯一
    155.                 print(f'add：key={key}重复，只更新值：{cur.value}->{value}')
    156.                 cur.value = value
    157.                 return
    158.         # 新增一个元素
    159.         # 如果正常退出循环，cur指向最后一个元素
    160.         node = Node(key, value)
    161.         cur.next = node
    162.         print('add：key不重复，新增元素:', key, value)
    163.         # 哈希表元素个数加1
    164.         self.num += 1
    165.         # 判断哈希表是否需要扩容
    166.         if self.num >= self.getExpandThread():
    167.             self.travel()
    168.             self.expand()
    169.  
    170.     def getKey(self, key):
    171.         # 查找某个键对应的值,O(m),m为哈希码链表长度
    172.         # 1、找key对应的哈希码
    173.         hashCode = self.getHashCode(key)
    174.         # 2、查找
    175.         cur = self.table[hashCode]
    176.         while cur.next:
    177.             cur = cur.next
    178.             if cur.key == key:
    179.                 print(f'查找元素：key={key}对应的value={cur.value}')
    180.                 return cur.value
    181.         print(f'查找元素：哈希表中不存在key={key}')
    182.         return None
    183.  
    184.     def updateKey(self, key, value):
    185.         # 更新key对应的值，O(M)
    186.         hashCode = self.getHashCode(key)
    187.         cur = self.table[hashCode]
    188.         while cur.next:
    189.             cur = cur.next
    190.             if cur.key == key:
    191.                 print(f'更新元素：更新key={key}的value：{cur.value}->{value}')
    192.                 cur.value = value
    193.                 break
    194.  
    195.  
    196. table = Hash(8)
    197. table.add(0, 0)
    198. table.add(3, 3)
    199. table.add(4, 4)
    200. table.add(8, 8)
    201. table.travel()
    202. table.travel(3)
    203. table.getKey(3)
    204. table.add(3, 8)
    205. table.travel()
    206. table.getKey(3)
    207. table.updateKey(4, 8)
    208. table.travel()
    209. table.getKey(2)
    210. table.add(16, 16)
    211. table.add(24, 24)
    212. table.add(32, 32)
    213. table.add(40, 40)
    214. table.travel()
    215. table.remove(0)
    216. table.remove(3)
    217. table.remove(8)
    218. table.remove(32)
    219. table.travel()
    '
    运行

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号