哈希表简介
哈希表，在计算机科学中，是一种通过多对一的映射将键映射到值的数据结构。Hash表通过使用散列函数将每个键映射到一个值上，这个值通常是一个桶号，桶里存储了与这个键对应的值。
一般而言，哈希表的实现需要以下几个步骤：
设计哈希函数，将键转换成键的哈希码；
将哈希码映射到特定的桶上；
处理冲突的方法，如开放定地址法、链接法等；
设计哈希表
1.实现哈希函数
哈希函数的作用是将任意长度的输入（比如字符串）压缩成某个固定长度的输出，通常称为哈希值（hash value）或哈希码（hash code）。
在 Python 中，我们常用的哈希函数有以下几种：
SHA1 加密算法：实现方式比较简单，但安全性相对不够高；
MD5 加密算法：相对于 SHA1 更加安全，但加密效率相对低一些；
CRC32 算法：为了提供高速数据校验而广泛使用的算法，但有很大的哈希冲突。
下面是一段使用 Python 实现哈希函数的代码：
import hashlib
def hash_func(key):
md5 = hashlib.md5()
md5.update(key.encode('utf-8'))
return int(md5.hexdigest(), 16)
上面的代码中，我们选择了 MD5 算法作为哈希函数，并用字符串类型的键计算哈希值，结果返回一个整数类型的哈希码。
2.实现桶
哈希表需要用数组来存储数据，每个元素叫做一个桶（bucket），每个桶可以存放一个或多个键值对。桶的个数通常选为一个合适的质数，可以通过哈希函数将键映射到一个桶中。
下面是一个 Python 实现的哈希表对象：
from typing import List
class HashTable:
def __init__(self, capacity: int = 11):
self.capacity = capacity
self.buckets: List[None] = [None] * self.capacity
# 哈希函数
def hash(self, key: str) -> int:
return hash(key) % self.capacity
# 插入数据
def insert(self, key: str, value: any) -> None:
index = self.hash(key)
if self.buckets[index] is None:
self.buckets[index] = []
self.buckets[index].append((key, value))
# 查询数据
def search(self, key: str) -> any:
index = self.hash(key)
bucket = self.buckets[index]
if bucket is None:
return None
for (k, v) in bucket:
if k == key:
return v
return None
上面的代码中，我们使用了 Python 中的 List 类来存储桶，使用哈希函数将键转换成相应的桶号，然后在相应的桶中进行插入和查询操作。如果桶中已经存在相同键值对，则需要将其添加在哈希冲突的链表中。
3.解决冲突
哈希函数的设计不能避免哈希冲突，因此，解决哈希冲突的方法是哈希表的一个重要组成部分。
常见的解决哈希冲突的方法有以下两种：
（1）线性探测法
线性探测法，也称为开放地址法，是解决哈希冲突的一种方式。当发生哈希冲突时，线性探测法会尝试在哈希表中的下一个空桶中插入数据，直到找到一个空桶为止。这种方法在处理哈希表中冲突较少的情况下比较有效，但在处理冲突较多的情况下效率会变得很低。
下面是一个使用线性探测法解决哈希冲突的 Python 实现：
class HashTable:
def __init__(self, capacity: int = 11):
self.capacity = capacity
self.buckets: List[None] = [None] * self.capacity
# 哈希函数
def hash(self, key: str) -> int:
return hash(key) % self.capacity
# 插入数据
def insert(self, key: str, value: any) -> None:
index = self.hash(key)
if self.buckets[index] is None:
self.buckets[index] = (key, value)
else:
while self.buckets[index] is not None and self.buckets[index][0] != key:
index = (index + 1) % self.capacity
self.buckets[index] = (key, value)
# 查询数据
def search(self, key: str) -> any:
index = self.hash(key)
while self.buckets[index] is not None:
if self.buckets[index][0] == key:
return self.buckets[index][1]
index = (index + 1) % self.capacity
return None
上面的代码中，我们使用了 while 循环解决了哈希冲突问题，当检测到桶已被占用，则算法会尝试在下一个桶中插入数据，直到找到一个空桶或者找到相同的 key 就会停止，这就是线性探测法的基本原理。
（2）链地址法
链地址法，又称为拉链法，是一种常见的处理哈希冲突的方法，用链表来存储哈希表中的所有元素，一旦出现冲突，就直接将元素插入到链表中。
下面是一个使用链地址法解决哈希冲突的 Python 实现：
class HashTable:
def __init__(self, capacity: int = 11):
self.capacity = capacity
self.buckets: List[None] = [None] * self.capacity
# 哈希函数
def hash(self, key: str) -> int:
return hash(key) % self.capacity
# 插入数据
def insert(self, key: str, value: any) -> None:
index = self.hash(key)
if self.buckets[index] is None:
self.buckets[index] = []
self.buckets[index].append((key, value))
# 查询数据
def search(self, key: str) -> any:
index = self.hash(key)
bucket = self.buckets[index]
if bucket is None:
return None
for (k, v) in bucket:
if k == key:
return v
return None
上面的代码中，我们使用了 Python 中的 List 类来存储桶，使用哈希函数将键转换成相应的桶号，然后在相应的桶中进行插入和查询操作。如果桶中已经存在相同键值对，则需要将其添加在哈希冲突的链表中。
使用哈希表
1.插入数据
使用哈希表的常见操作是插入数据，代码示例如下：
hash_table = HashTable()
hash_table.insert('键1', '值1')
hash_table.insert('键2', '值2')
hash_table.insert('键3', '值3')
2.查询数据
使用哈希表查询数据的操作很简单，代码示例如下：
hash_table = HashTable()
hash_table.insert('键1', '值1')
hash_table.insert('键2', '值2')
hash_table.insert('键3', '值3')
value = hash_table.search('键2') # 查找键2对应的值
print(value)
上述程序会输出：
'值2'
总结
哈希表是一种非常高效的数据结构，在 Python 中也有很多实现方法，本文介绍了一个基于数组和 Python List 实现的散列表，并讲述了常见的哈希函数和处理哈希冲突的方法。在实际应用中，我们可以根据具体的条件和需求来选择相应的实现方法。