Python 算法基础篇：哈希表与散列函数

Python 算法基础篇：哈希表与散列函数

引用

哈希表是一种高效的数据结构，常用于存储键值对并支持快速的插入、查找和删除操作。散列函数是哈希表的关键组成部分，用于将键映射到哈希表的索引位置。本篇博客将介绍哈希表和散列函数的基本概念，并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 哈希表的概念

哈希表是一种数据结构，它将键值对存储在一个数组中，并通过散列函数将键映射到数组的索引位置。这样可以快速地插入、查找和删除键值对，使得哈希表成为一种高效的数据结构。哈希表的查找操作的平均时间复杂度为 O ( 1 )，在理想情况下可以达到常数时间。

哈希表的主要优点是快速的查找操作，但它也有一些局限性。首先，哈希表的键必须是可哈希的，即可以通过散列函数计算得到唯一的哈希值。其次，哈希表的内存消耗较大，因为需要维护一个数组来存储数据。最后，哈希表的查找操作在最坏情况下可能变得很慢，如果哈希函数导致冲突，多个键被映射到同一个索引位置，就需要处理冲突。

2. 散列函数的概念

散列函数是哈希表的关键组成部分，它将键映射到哈希表的索引位置。散列函数必须满足以下特性：

a ) 一致性

对于相同的键，散列函数应该始终返回相同的哈希值。这样可以确保相同的键在哈希表中总是存储在相同的位置，实现快速的查找操作。

b ) 均匀性

散列函数应该将键均匀地映射到哈希表的不同索引位置，减少冲突的发生。这样可以确保哈希表中的数据分布均匀，避免出现过多的冲突。

c ) 高效性

散列函数应该能够在常数时间内计算出哈希值，以保持快速的插入、查找和删除操作。

3. 散列函数的实现

Python 内置了一个 hash() 函数，它可以用于获取对象的哈希值。对于大多数内置类型， hash() 函数能够返回唯一的哈希值。例如，对于整数、浮点数和字符串等类型， hash() 函数都能返回唯一的哈希值。下面是一个示例代码：

# 使用hash()函数获取哈希值
print(hash(42))
print(hash(3.14))
print(hash('hello'))

代码解释：上述代码演示了 hash() 函数在整数、浮点数和字符串类型上的应用。对于整数和浮点数， hash() 函数能够返回唯一的哈希值；对于字符串，它也能返回唯一的哈希值。

然而，需要注意的是，用户自定义的对象默认情况下不支持 hash() 函数，因为 Python 不知道如何将用户自定义的对象映射到哈希表的索引位置。如果需要自定义散列函数，可以在对象的类中实现 __hash__() 方法。

4. 哈希表的实现

Python 中没有直接的哈希表数据结构，但我们可以使用字典（ dictionary ）来实现哈希表的功能。字典是 Python 中的一种内置数据结构，用于存储键值对。下面是一个示例代码：

# 创建字典
student_scores = {'Alice': 95, 'Bob': 80, 'Charlie': 75, 'David': 90}

# 查找元素
print("Alice 的成绩：", student_scores['Alice'])

# 插入元素
student_scores['Emma'] = 88

# 删除元素
del student_scores['Charlie']

# 打印字典
print("学生成绩表：", student_scores)

代码解释：上述代码演示了如何使用字典实现哈希表的功能。首先，我们创建了一个存储学生姓名和成绩的字典。通过使用键来查找元素，我们可以快速获取学生的成绩。然后，我们可以插入新的键值对和删除不需要的键值对。最后，打印字典的内容。

5. 哈希表的冲突解决

在散列函数的映射过程中，不同的键可能会产生相同的哈希值，这就是冲突。当出现冲突时，我们需要解决冲突，确保每个键能够正确地映射到哈希表的索引位置。

a ) 链地址法

链地址法是一种简单且常用的解决冲突的方法。它使用一个链表来存储哈希值相同的键值对。当发生冲突时，新的键值对会被添加到链表中，这样可以保证所有的键值对都能被正确地存储在哈希表中。

b ) 开放地址法

开放地址法是另一种解决冲突的方法。它在发生冲突时不使用链表，而是在哈希表中寻找下一个可用的空槽来存储键值对。有多种开放地址法的实现方式，如线性探测、二次探测和双重散列等。

6. 实例演示

现在，让我们通过一个实例来演示哈希表的应用，以及使用链地址法解决冲突。

实例：电话簿

假设我们需要实现一个电话簿应用，存储人名和对应的电话号码。下面是一个示例代码：

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self._hash_function(key)
        self.table[index].append((key, value))

    def search(self, key):
        index = self._hash_function(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

    def delete(self, key):
        index = self._hash_function(key)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return

# 创建电话簿
phone_book = HashTable(10)

# 添加联系人信息
phone_book.insert('Alice', '123456789')
phone_book.insert('Bob', '987654321')
phone_book.insert('Charlie', '456789123')

# 查找联系人电话号码
print("Alice 的电话号码：", phone_book.search('Alice'))

# 删除联系人信息
phone_book.delete('Bob')

# 打印电话簿
print("电话簿内容：", phone_book.table)

代码解释：上述代码演示了使用哈希表实现电话簿应用的示例。我们创建了一个 HashTable 类来表示哈希表，其中包括插入、查找和删除操作的实现。我们通过散列函数将人名映射到哈希表的索引位置，并使用链地址法解决冲突，确保人名和电话号码正确地存储在哈希表中。

总结

本篇博客介绍了哈希表和散列函数的基本概念，并通过实例代码演示了它们的应用。哈希表是一种高效的数据结构，用于存储键值对并支持快速的插入、查找和删除操作。散列函数是哈希表的关键组成部分，用于将键映射到哈希表的索引位置。