如何在 Python 中设计一个 Hashset？

我们知道 HashSet 是 Java 中一个著名的类。HashSet 用于使用哈希表存储值。在本教程中，我们将介绍 Python 中的 HashSet。我们还将学习如何在 Python 中设计 HashSet。

HashSet 是编程中的一个基本数据结构，常见于 Java 等语言中。它属于 Java Collections Framework，是 Set 接口的实现。HashSet 的独特之处在于它能够以一种方便高效地检查特定元素是否存在的方式存储元素，并确保集合内的唯一性。与列表等结构不同，HashSet 不会维护元素之间的任何特定顺序。

HashSet 的一个关键特性是保证唯一性；它不允许重复元素。添加、删除和检查元素是否存在等操作通常具有平均恒定时间性能，使其成为此类任务的有效选择。但是，需要注意的是，HashSet 中元素的顺序不保证。

关键特性

唯一性：HashSet 不允许重复元素。它使用 equals() 方法检查重复项，确保集合中的每个元素都是唯一的。

无序：HashSet 中的元素不是按任何特定顺序存储的。如果您需要维护元素的顺序，可以考虑使用 LinkedHashSet，它会维护插入顺序。

底层数据结构：内部，HashSet 使用哈希表来存储元素。这使得 add、remove 和 contains 等基本操作具有平均恒定时间复杂度。

Null 元素：HashSet 允许一个 null 元素。如果您尝试添加重复的 null 元素，它将替换现有的元素。

引言

我们可以在不使用任何哈希表库的情况下设计 HashSet。以下是多个不同的函数 -

add(x) - add(x) 方法主要用于将值 x 插入 HashSet。

contains(x) - contains(x) 方法主要用于检查值 x 是否存在于 HashSet 中。

remove(x) - remove(x) 方法主要用于从 HashSet 中删除 x。如果 HashSet 中没有该值，它将不做任何操作。

让我们通过以下示例来理解这些方法。

首先，初始化 HashSet 并调用 add(1) 函数。它会将 1 添加到哈希集中。调用 add(3)，它会添加 3，然后调用 contains(1)。它会检查 1 是否存在于哈希集中。现在我们调用 contains(2)，add(2)，contains(2)，remove(2)，contains(2)。

输出将分别为 1 存在时返回 true，2 不存在时返回 false，2 存在时返回 true，2 不存在时返回 false。

Python 中 HashSet 的基本操作

我们可以使用以下方法对 HashSet 执行一些基本操作。让我们来理解这些方法。

在 HashSet 中添加新值

在下面的示例中，我们将使用 add() 函数向哈希集中添加值。add() 函数一次添加一个值。让我们看下面的代码。

示例 -

输出

Adding value: 2
Adding value: 7
Adding value: 6

从 HashSet 中删除值

我们可以使用 remove() 函数删除现有值。让我们来理解下面的代码。

示例 -

输出

Adding value: 2
Adding value: 7
Adding value: 6
Removed value: 7
Removed value: 6

检查值是否存在于 HashSet 中

在此示例中，我们将演示如何使用 **contains()** 函数检查某个特定值是否存在。让我们来理解下面的代码。

示例 -

输出

Adding value: 2
Adding value: 7
Adding value: 6
It contains: 2

Python 中 HashSet 的算法

第一步，我们定义一个名为 HashList 的数据结构。然后，我们初始化一个空列表作为 **a new_list**。然后，我们定义一个 update() 函数，其中 found 将存储布尔值 False。现在，我们使用 for 循环遍历每个索引 I 和 K。如果键与 'k' 相同，则 **new_list[i]=k** 并将 found 值设置为 True。如果找不到值，则该值将插入到列表的末尾。

下一步是定义 get() 函数，我们将用于循环，并且如果 k 的值与键相同，则输出为 True；否则为 False。如果键与 'k' 相同，则从列表 **new_list 中删除该值。remove() 函数也将应用相同的过程。**

现在，我们将创建 Main 类 HashSet。此类将声明初始化函数，其中 key_space 值 = 2096。hash_table 将包含大小为 **key_space** 的 new_list 类型对象的列表。然后，我们将创建 add() 函数，其中 **hash_key = key%key_space** 并更新 hash_table[hash_key] 的键。之后，我们将调用 **remove 函数**，其中 hash_key = key % key_space，并删除 hash_table[hash_key] 的键。之后，我们将调用 **contains 函数**，其中

hash_key = key % key_space，并获取 hash_table[hash_key] 的键。

让我们看一下分步实现算法。

算法 -

• 创建名为 HashSet 的数据结构，如下初始化
• new_list = []
• 定义一个 update() 函数。它将接收一个键
• found := False
• 对于 new_list 中的每个索引 i 和键 k，执行
• 如果键与 k 相同，则
• new_list[i]:= key
• found:= True
• 跳出循环
• 如果 found 为 False，则
• 将键插入 new_list 的末尾
• 定义一个 get() 函数。它将接收一个键
• 对于 new_list 中的每个 k，执行
• 如果 k 与键相同，则
• 返回 True
• 返回 False
• 定义一个 remove() 函数。它将接收一个键
• 对于 new_list 中的每个索引 i 和键 k，执行
• 如果键与 k 相同，则
• 删除 new_list[i]
• 现在创建一个自定义 hashSet。将有几个方法如下
• 初始化如下 -
• key_space := 2096
• hash_table:= 大小为 key_space 的 bucket 类型对象的列表
• 定义一个 add() 函数。它将接收一个键
• hash_key:= key mod key_space
• 调用 hash_table[hash_key] 的 update(key)
• 定义一个 remove() 函数。它将接收一个键
• hash_key:= keymodkey_space
• 从 hash_table[hash_key] 中删除键
• 定义一个 contains() 函数。它将接收一个键
• hash_key:= keymodkey_space
• 返回 hash_table[hash_key] 的 get(key)

HashSet 在 Python 中的实现

在这里，我们将实现上述算法并创建 Python 程序。我们将定义两个类：HashSet 和 CreateHashset。让我们看下面的代码。

代码 -

输出

10
 Add 10 
6
Add 6
5
Add 5
Contains 10 :  True
Contains 3:  False
Contains 8 :  False
2
Add 2
3
Add 3
Contains 2 :  True
Remove 2
Contains 2 :  False
Contains 3 :  True
[3, 5, 6, 10]

说明

• verifyvalues 类：该类处理值的列表 (new_list) 并提供更新、检查存在性和删除值的方法。
• __init__ 方法：为每个实例初始化一个空列表。
• update 方法：更新现有值或将新值附加到列表中。
• get 方法：检查值是否存在于列表中。
• remove 方法：从列表中删除指定值。
• HashSet 类：这是 HashSet 的主要实现。
• __init__ 方法：初始化具有预定义键空间的 HashSet，并创建一个 verifyvalues 实例的数组 (hash_table) 来处理冲突。
• hash_values 方法：使用模运算为给定的输入键计算哈希键。
• add 方法：通过更新 hash_table 中相应的 verifyvalues 对象来向 HashSet 添加键。
• remove 方法：从 HashSet 中删除一个键。
• contains 方法：检查 HashSet 中是否存在一个键。
• show 方法：打印每个非空 verifyvalues 列表的主要元素，提供数据分布的快照。
• 使用示例：代码通过添加键 (10、6、5)、检查存在性以及显示内部状态的一些数据来演示 HashSet 的用法。