常见的哈希表操作包括查询、添加键值对、删除键值对和遍历哈希表等。
基于数组实现
class Pair: def __init__(self, key, value) -> None: self.key = key self.value = value class Array_Hash: def __init__(self): self.buckets = [None]*100 for i in range(100): self.buckets[i] = [] def hash_func(self, key): return key % 100 def put(self, key, value): pair = Pair(key=key, value=value) index = self.hash_func(key) if self.buckets[index] == None: self.buckets[index] = [] self.buckets[index].append(pair) def get(self, key): index = self.hash_func(key) lst = self.buckets[index] for pair in lst: if pair.key == key: return pair.value raise ValueError('没有这个键') def remove(self, key): index = self.hash_func(key) lst = self.buckets[index] for ix, pair in enumerate(lst): if pair.key == key: break del lst[ix] def entry_set(self): pair_list = [] for bucket in self.buckets: for pair in bucket: pair_list.append(pair) return pair_list def key_set(self): key_list = [] pair_list = self.entry_set() for pair in pair_list: key_list.append(pair.key) return key_list def value_set(self): value_list = [] pair_list = self.entry_set() for pair in pair_list: value_list.append(pair.value) return value_list def print_hash(self): buckets = self.buckets for ix, bucket in enumerate(buckets): if bucket != []: print(ix, end=' --- ') for pair in bucket: print(pair.key, "->", pair.value, end=' >>> ') print('结束')
基于链表实现
class ListNode: def __init__(self, key, value) -> None: self.key = key self.value = value self.next = None class ListHash: def __init__(self) -> None: self.buckets = [None] * 100 def hash_func(self, key): return key % 100 def put(self, key, value): node = ListNode(key, value) index = self.hash_func(key) if self.buckets[index] == None: self.buckets[index] = node else: original_node = self.buckets[index] while original_node.next: original_node = original_node.next original_node.next = node def get(self, key): index = self.hash_func(key) bucket = self.buckets[index] while bucket: if bucket.key == key: return bucket.value else: bucket = bucket.next raise IndexError('hash没有这个键') def remove(self, key): index = self.hash_func(key) bucket = self.buckets[index] while bucket: if bucket.next != None: if bucket.next.key == key: remove_node = bucket.next bucket.next = remove_node.next remove_node.next = None break bucket = bucket.next def entry_set(self): lst = [] for bucket in self.buckets: if bucket != None: lst.append(bucket) return lst def key_set(self): lst = [] listnodes = self.entry_set() for listnode in listnodes: while listnode: lst.append(listnode.key) listnode = listnode.next return lst def value_set(self): lst = [] listnodes = self.entry_set() for listnode in listnodes: while listnode: lst.append(listnode.value) listnode = listnode.next return lst def print_hash(self): for ix, bucket in enumerate(self.buckets): if bucket: print(ix, end=' --- ') while bucket: print(bucket.key, "->", bucket.value, end=' >>> ') bucket = bucket.next print('结束')
进一步优化
当链表很长时，查询效率 𝑂(𝑛) 很差。此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 𝑂(log 𝑛)
哈希算法目标
哈希算法特点
- 确定性：对于相同的输入，哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠的。
- 效率高：计算哈希值的过程应该足够快。计算开销越小，哈希表的实用性越高。
- 均匀分布：哈希算法应使得键值对平均分布在哈希表中。分布越平均，哈希冲突的概率就越低。
实际上，哈希算法除了可以用于实现哈希表，还广泛应用于其他领域中。 - 密码存储：为了保护用户密码的安全，系统通常不会直接存储用户的明文密码，而是存储密码的哈希值。当用户输入密码时，系统会对输入的密码计算哈希值，然后与存储的哈希值进行比较。如果两者匹配，那么密码就被视为正确。
- 数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整的。
对于密码学的相关应用，为了防止从哈希值推导出原始密码等逆向工程，哈希算法需要具备更高等级的安全特性。 - 抗碰撞性：应当极其困难找到两个不同的输入，使得它们的哈希值相同。
- 雪崩效应：输入的微小变化应当导致输出的显著且不可预测的变化。
哈希算法的设计
- 加法哈希：对输入的每个字符的 ASCII 码进行相加，将得到的总和作为哈希值。
def add_hash(key: str) -> int: hash = 0 modulus = 1000000007 for c in key: hash += ord(c) return hash % modulus
- 乘法哈希：利用了乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII 码累积到哈希值中。
def mul_hash(key: str) -> int: hash = 0 modulus = 1000000007 for c in key: hash = 31 * hash + ord(c) return hash % modulus
- 异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。
def xor_hash(key: str) -> int: hash = 0 modulus = 1000000007 for c in key: hash ^= ord(c) return hash % modulus
- 旋转哈希：将每个字符的 ASCII 码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作。
def rot_hash(key: str) -> int: hash = 0 modulus = 1000000007 for c in key: hash = (hash << 4) ^ (hash >> 28) ^ ord(c) return hash % modulus
对大质数 1000000007 取模,避免约分导致扎堆
![[Pasted image 20230919222910.png]]
重点回顾
- 输入 key ，哈希表能够在 𝑂(1) 时间内查询到 value ，效率非常高。
- 常见的哈希表操作包括查询、添加键值对、删除键值对和遍历哈希表等。
- 哈希函数将 key 映射为数组索引，从而访问对应桶并获取 value 。
- 两个不同的 key 可能在经过哈希函数后得到相同的数组索引，导致查询结果出错，这种现象被称为哈希冲突。
- 哈希表容量越大，哈希冲突的概率就越低。因此可以通过扩容哈希表来缓解哈希冲突。与数组扩容类似，哈希表扩容操作的开销很大。
- 负载因子定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件。
- 链式地址通过将单个元素转化为链表，将所有冲突元素存储在同一个链表中。然而，链表过长会降低查询效率，可以进一步将链表转换为红黑树来提高效率。
- 开放寻址通过多次探测来处理哈希冲突。线性探测使用固定步长，缺点是不能删除元素，且容易产生聚集。多次哈希使用多个哈希函数进行探测，相较线性探测更不易产生聚集，但多个哈希函数增加了计算量。
- 不同编程语言采取了不同的哈希表实现。例如，Java 的 HashMap 使用链式地址，而 Python 的 Dict 采用开放寻址。在哈希表中，我们希望哈希算法具有确定性、高效率和均匀分布的特点。在密码学中，哈希算法还应该具备抗碰撞性和雪崩效应。
- 哈希算法通常采用大质数作为模数，以最大化地保证哈希值的均匀分布，减少哈希冲突。
- 常见的哈希算法包括 MD5、SHA‑1、SHA‑2 和 SHA3 等。MD5 常用于校验文件完整性，SHA‑2 常用于安全应用与协议。
- 编程语言通常会为数据类型提供内置哈希算法，用于计算哈希表中的桶索引。通常情况下，只有不可变对象是可哈希的。
