Python 算法基础篇之散列查找算法：哈希表、哈希集合、哈希映射

小蓝枣

发布于 2023-07-24 15:11:13

2880

发布于 2023-07-24 15:11:13

文章被收录于专栏：CSDN博客专家-小蓝枣的博客

Python 算法基础篇之散列查找算法：哈希表、哈希集合、哈希映射

引言

散列查找算法是一种高效的查找技术，通过散列函数将键映射到数组的索引位置，实现快速的查找、插入和删除操作。本篇博客将介绍散列查找算法的三种常见应用：哈希表、哈希集合和哈希映射，并通过实例代码演示它们的应用。

😃😄 ❤️ ❤️ ❤️

1. 散列查找算法概述

散列查找算法是一种基于散列函数的查找技术，它将键映射到数组的索引位置，从而实现快速的查找、插入和删除操作。在散列查找算法中，关键的组成部分是散列函数，它负责将键映射到数组的索引位置。当有多个键映射到同一个索引位置时，会发生冲突，散列查找算法需要解决这些冲突。

散列查找算法的主要优点是查找操作的平均时间复杂度为 O ( 1 )，在理想情况下可以达到常数时间。然而，它也有一些局限性，首先是散列函数的设计需要满足一致性和均匀性的要求，以保证良好的性能。其次，散列查找算法的空间消耗较大，因为需要维护一个数组来存储数据。

2. 哈希表的概念

哈希表是散列查找算法的一种常见应用，它是一种数据结构，用于存储键值对。在哈希表中，通过散列函数将键映射到数组的索引位置，然后将键值对存储在该位置。哈希表的主要优点是查找、插入和删除操作的平均时间复杂度为 O ( 1 )，因此具有快速的查找能力。

哈希表的实现需要解决冲突的问题，当有多个键映射到同一个索引位置时，需要使用链地址法或开放地址法来解决冲突。链地址法将冲突的键值对存储在同一个索引位置的链表中，而开放地址法则在哈希表中寻找下一个可用的空槽来存储冲突的键值对。

3. 哈希集合的概念

哈希集合是一种基于哈希表的集合数据结构，它存储唯一的元素，并支持快速的插入、查找和删除操作。哈希集合使用散列函数将元素映射到数组的索引位置，从而实现快速的查找能力。

哈希集合的实现类似于哈希表，不同之处在于哈希集合只存储键而不存储值。当需要判断元素是否存在于哈希集合中时，可以通过散列函数计算出元素的哈希值，然后查找哈希集合中的索引位置，如果存在则表示元素存在于哈希集合中。

4. 哈希映射的概念

哈希映射是一种基于哈希表的映射数据结构，它存储键值对，并支持快速的插入、查找和删除操作。哈希映射使用散列函数将键映射到数组的索引位置，从而实现快速的查找能力。

哈希映射的实现类似于哈希表，它存储键值对而不仅仅是键。当需要查找或操作键对应的值时，可以通过散列函数计算出键的哈希值，然后查找哈希映射中的索引位置，从而快速地获取键对应的值。

5. 实例演示

现在，让我们通过实例代码来演示哈希表、哈希集合和哈希映射的应用。

实例1：哈希表

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

# 创建哈希表
hash_table = HashTable(10)

# 添加键值对
hash_table.insert('apple', 2)
hash_table.insert('banana', 3)
hash_table.insert('orange', 4)

# 查找键对应的值
print("apple 对应的值：", hash_table.search('apple'))

# 删除键值对
hash_table.delete('banana')

# 打印哈希表
print("哈希表内容：", hash_table.table)

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

实例2：哈希集合

class HashSet:
    def __init__(self):
        self.hash_set = set()

    def add(self, key):
        self.hash_set.add(key)

    def contains(self, key):
        return key in self.hash_set

    def remove(self, key):
        if self.contains(key):
            self.hash_set.remove(key)

# 创建哈希集合
hash_set = HashSet()

# 添加元素
hash_set.add('apple')
hash_set.add('banana')
hash_set.add('orange')

# 判断元素是否存在
print("apple 存在于集合中：", hash_set.contains('apple'))

# 删除元素
hash_set.remove('banana')

# 打印哈希集合
print("哈希集合内容：", hash_set.hash_set)

代码解释：上述代码演示了使用哈希集合存储水果名称的实例。我们创建了一个 HashSet 类来表示哈希集合，并实现了添加、判断是否存在和删除操作。我们通过散列函数将水果名称映射到哈希集合中，并使用内置的集合数据结构来实现哈希集合的功能。

实例3：哈希映射

class HashMap:
    def __init__(self):
        self.hash_map = {}

    def put(self, key, value):
        self.hash_map[key] = value

    def get(self, key):
        return self.hash_map.get(key, None)

    def remove(self, key):
        if key in self.hash_map:
            del self.hash_map[key]

# 创建哈希映射
hash_map = HashMap()

# 添加键值对
hash_map.put('apple', 2)
hash_map.put('banana', 3)
hash_map.put('orange', 4)

# 获取键对应的值
print("apple 对应的值：", hash_map.get('apple'))

# 删除键值对
hash_map.remove('banana')

# 打印哈希映射
print("哈希映射内容：", hash_map.hash_map)

代码解释：上述代码演示了使用哈希映射存储水果名称和对应的数量的实例。我们创建了一个 HashMap 类来表示哈希映射，并实现了添加、获取和删除操作。我们通过散列函数将水果名称映射到哈希映射中，并使用内置的字典数据结构来实现哈希映射的功能。