Python Hash Table 散列表

Question

用于存储 key 对应的 value，给定 key，能够在非常快速的时间内找到 value。

设计一个散列函数，计算出关键字 key 对应的函数值 hashcode，作为数据对象 value 的存储地址。对某个关键字进行查找时，通过散列函数得到地址（或者是array的索引），通过索引访问数组直接得到这个 key 对应的 value，实现 O(1) 的时间复杂度。需要解决哈希冲突（Collision）的问题：即两个关键字映射到同一地址。一种解决办法是在产生冲突的地方使用链表存储，会带来新的问题就是如何确定 key 对应的 value 是链表中的哪个，所以这种情况下链表中不仅要存储 value，也要存储 key，也就是需要有两个 field，既存储 key，也存储 value

如果同一个 key 要插入不同的 value，有几种解决方式：一种是新插入的总是覆盖之前的 value，一种是允许一个key存在多个value，查找时随机返回一个 value，或者使用 find_all 返回所有 value

填充因子：n/N，已填充（已有的 key 的数量）/总空间；当填充因子变大时，会失去常数时间的效率，所以需要 resize：遍历原来的哈希表，re-hash 所有的 key，再把 value 存到新的哈希表的对应位置。当填充因子变小时，也需要 resize 释放内存

散列方法的存储对关键字是随机的，不适用于顺序查找关键字，不适用于最大/最小值查找或范围查找

散列函数的设计

散列函数最好计算高效，且映射之后对应的地址空间最好分布均匀以减少冲突。举例：

• 数字：取模；平方取中法；折叠法（把数字拆分再相加）
• 一个比较好的方法：hash_code(key) = (((a*key + b) mod p) mod N)；p是一个远大于N 的素数（促进均匀分布），N是存储空间的长度（数组的长度）
• 字符：ASCII 码加和再取模（很多冲突）
• 一个比较好的方法（最终的 hashcode 取决于每个字符）：

def hash_code(string_a, N):
  hash_val = 0
  for i in range(len(string_a)):
    hash_val = (127 * hash_val + string_a[i]) % 16908799
  return hash_val % N

哈希冲突

上面已经说了什么是哈希冲突，这里说一下处理哈希冲突的常用方法：

• 线性探测法：发生冲突后，向前寻找一个空位来存储。注意删除操作应当将右侧所有相邻的键值对重新插入散列表中
• 拉链法：在发生冲突的位置使用链表存储

这两种方法存储的时候都要同时存储 key 和 value，这样查找的时候才知道是否命中对应的key

主要功能实现：

使用拉链法解决哈希冲突；假设 key 是数字；如果同一个 key 插入不同的 value，则总是覆盖。

class listNode:
  def __init__(self, key, value):
    self.key = key
    self.value = value
    self.next = None

class HashTable:
  def __init__(self,N):
    self.size = N
    self.table = [None] * N

hash_code(key) -- 计算 key 的哈希值：参考上面提到的对应数字和字符串的散列方法

insert(key, value) -- 在哈希表中插入新的 key 及其对应的 value

def insert(self, key, value):
  index = self.hash_code(key)
  head = self.table[index]
  if not head:  # 如果哈希表对应位置还是空的
    self.table[index] = listNode(key, value)
  else:
    while head.next:
      head = head.next
    head.next = listNode(key, value)

find(key) -- 寻找 key 对应的 value

def find(self, key):
  index = self.hash_code(key)
  head = self.table[index]
  if not head:
    return None
  else:
    while head:
      if head.key == key:
        return head.value
      head = head.next
    return None

remove(key) -- 从哈希表中删除一个 key 及其对应的 value

def remove(self, key):
  index = self.hash_code(key)
  head = self.table[index]
  if not head:
    return None
  else:
    prev = None
    while head:
      if head.key == key:
        next_node = head.next
        if prev:
          prev.next = next_node
          return head.value
        else:
          self.table[index] = head.next
          return head.value
      else:
        prev = head
        head = head.next
    return None