简单讲解哈希表

哈希表（Hash Table），也被称为散列表，是一种高效的数据结构，它可以在O(1)的时间复杂度下完成插入、删除、查找等基本操作。哈希表是通过将关键字映射到一个固定大小的表中来实现的，这个映射函数被称为哈希函数。

什么是哈希函数

哈希函数是将任意长度的输入值（也称为“键”或“关键字”）映射为固定大小的输出值（也称为“哈希值”或“散列”）。哈希函数必须将不同的关键字映射到不同的哈希值中，从而使得关键字之间的比较可以转化为哈希值之间的比较，提高了查找效率。

常用的哈希函数有以下几种：

1. 直接取模法：对哈希表的大小（通常为素数）取模，取模的结果作为哈希值。直接取模法的缺点是可能会使得某些哈希值的分布不均匀，影响了性能。
2. 加权取模法：将关键字的每一位乘以不同的权值，再将所有结果相加，最后对哈希表的大小取模，取模的结果作为哈希值。加权取模法可以解决直接取模法产生的哈希冲突问题。
3. MD5和SHA1：基于MD5和SHA1算法的哈希函数，可以生成128位和160位哈希值，具有较高的安全性和哈希性能。

哈希表的实现

哈希表的实现主要包含两个部分：哈希函数和哈希冲突的解决方法。

哈希函数

哈希函数的选择决定了哈希表的性能，好的哈希函数可以使哈希值的分布较为均匀，从而减少哈希冲突的概率。常用的哈希函数如下：

def hash_function(key, size):
    """
    直接取模法哈希函数
    :param key: 关键字
    :param size: 哈希表的大小
    :return: 哈希值
    """
    return key % size

哈希冲突的解决方法

哈希冲突指的是不同的关键字映射到同一个哈希值的情况。常用的哈希冲突解决方法有以下几种：

1. 开放地址法：当出现哈希冲突时，依次查找下一个空的哈希桶，直到找到为止。
2. 链地址法：将哈希桶中的元素存储在一个链表中，当出现哈希冲突时，在链表的末尾添加一个新元素。

哈希表的操作

插入操作

插入操作包含以下步骤：

1. 计算关键字的哈希值；
2. 根据哈希值找到对应的哈希桶；
3. 判断哈希桶是否为空，如果为空，直接插入元素；
4. 如果哈希桶不为空，根据哈希冲突的解决方法，找到下一个空闲的哈希桶，插入元素。

def insert(hash_table, key, value):
    # 计算哈希值
    hash_value = hash_function(key, len(hash_table))
    # 找到对应的哈希桶
    bucket = hash_table[hash_value]
    # 插入元素
    if not bucket:
        hash_table[hash_value] = [(key, value)]
    else:
        for i in range(len(bucket)):
            if bucket[i][0] == key:
                bucket[i] = (key, value)
                break
        else:
            bucket.append((key, value))

删除操作

删除操作比插入操作稍微复杂一些，因为需要考虑到哈希冲突。

删除操作包含以下步骤：

1. 计算关键字的哈希值；
2. 根据哈希值找到对应的哈希桶；
3. 在哈希桶中查找是否存在关键字对应的元素；
4. 如果存在，删除元素，如果不存在，返回错误提示。

def delete(hash_table, key):
    # 计算哈希值
    hash_value = hash_function(key, len(hash_table))
    # 找到对应的哈希桶
    bucket = hash_table[hash_value]
    # 在哈希桶中查找元素
    if bucket:
        for i in range(len(bucket)):
            if bucket[i][0] == key:
                del bucket[i]
                return
    print(f"Key {key} not found.")

查找操作

查找操作和删除操作类似，也需要考虑到哈希冲突。

查找操作包含以下步骤：

1. 计算关键字的哈希值；
2. 根据哈希值找到对应的哈希桶；
3. 在哈希桶中查找是否存在关键字对应的元素；
4. 如果存在，返回对应的值，如果不存在，返回错误提示。

def search(hash_table, key):
    # 计算哈希值
    hash_value = hash_function(key, len(hash_table))
    # 找到对应的哈希桶
    bucket = hash_table[hash_value]
    # 在哈希桶中查找元素
    if bucket:
        for i in range(len(bucket)):
            if bucket[i][0] == key:
                return bucket[i][1]
    print(f"Key {key} not found.")

示例说明

示例一

假设我们需要存储学生的姓名和对应的成绩信息，我们可以选择使用哈希表来实现。以下是实现的代码：

hash_table = [None] * 100

def add_student(name, score):
    insert(hash_table, name, score)

def get_score(name):
    return search(hash_table, name)

在上面的代码中，我们使用了一个长度为100的哈希表来存储学生信息，每个元素的格式为(key, value)，其中key为学生的姓名，value为对应的成绩。我们通过调用insert函数来向哈希表中添加学生信息，通过调用search函数来查找学生信息。

示例二

假设我们需要存储一些网站的URL地址和对应的IP地址信息，我们可以选择使用哈希表来实现。以下是实现的代码：

hash_table = [None] * 100

def add_url(url, ip):
    insert(hash_table, url, ip)

def get_ip(url):
    return search(hash_table, url)

在上面的代码中，我们使用了一个长度为100的哈希表来存储URL地址和对应的IP地址信息，每个元素的格式为(key, value)，其中key为URL地址，value为对应的IP地址。我们通过调用insert函数来向哈希表中添加URL地址和对应的IP地址信息，通过调用search函数来查找URL对应的IP地址。