哈希表的简介：
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
哈希表的基本工作原理：
1.哈希函数：
哈希函数是哈希表的核心，它将输入的键（key）转换为一个固定大小的整数（哈希值）。这个整数通常用于确定键在哈希表中的存储位置。理想情况下，哈希函数应该能够将不同的键映射到不同的哈希值，以减少冲突的发生。然而，在实际应用中，由于哈希表的大小有限，并且键的数量可能很大，因此冲突是不可避免的。
2.存储桶：
哈希表由一组存储桶组成，每个存储桶可以存储一个或多个键值对。存储桶的数量通常是固定的，并且决定了哈希表的大小。当插入一个键值对时，哈希函数会计算键的哈希值，然后使用该哈希值来确定键值对应该存储在哪个存储桶中。
3.冲突解决策略：
当两个不同的键产生相同的哈希值时，就发生了冲突。为了解决这个问题，哈希表使用了几种不同的冲突解决策略，其中最常用的是：
开放寻址法（Open Addressing）：
当发生冲突时，算法会在哈希表中查找下一个可用的存储桶来存储键值对。这可以通过线性探测（Linear Probing）、二次探测（Quadratic Probing）或双重哈希（Double Hashing）等方法实现。开放寻址法的优点是空间利用率高，但可能导致聚集现象，降低性能。
链地址法（Chaining）：
每个存储桶都关联一个链表或其他动态数据结构。当发生冲突时，具有相同哈希值的键值对都被添加到相应存储桶的链表中。这种方法可以避免聚集现象，但可能增加空间开销，因为需要为链表分配额外的内存。
4.插入操作：
当插入一个键值对时，哈希函数首先计算键的哈希值。然后，根据冲突解决策略，找到适当的存储桶或链表，并将键值对存储在那里。
5.查找操作：
为了查找一个键对应的值，哈希函数首先计算键的哈希值。然后，哈希表使用该哈希值来定位相应的存储桶或链表。在存储桶或链表中查找键，如果找到则返回对应的值，否则返回未找到。
6.删除操作：
删除操作与查找操作类似，首先通过哈希函数找到键对应的存储桶或链表。然后，在存储桶或链表中删除相应的键值对。在链地址法中，可能需要调整链表的结构以删除键值对。
下面是一个简单的示例，展示如何在Java中使用HashTable：
import java.util.Hashtable;
public class HashTableExample {
public static void main(String[] args) {
// 创建一个Hashtable实例
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 插入键值对
hashtable.put("apple", 1);
hashtable.put("banana", 2);
hashtable.put("cherry", 3);
// 获取键对应的值
Integer value = hashtable.get("apple");
System.out.println("The value for 'apple' is: " + value); // 输出：The value for 'apple' is: 1
// 检查键是否存在
boolean exists = hashtable.containsKey("banana");
System.out.println("Does 'banana' exist? " + exists); // 输出：Does 'banana' exist? true
// 遍历Hashtable
for (String key : hashtable.keySet()) {
System.out.println("Key: " + key + ", Value: " + hashtable.get(key));
}
// 删除键值对
hashtable.remove("banana");
// 再次检查键是否存在
exists = hashtable.containsKey("banana");
System.out.println("Does 'banana' exist after deletion? " + exists); // 输出：Does 'banana' exist after deletion? false
}
}
在这个例子中，我们首先创建了一个 Hashtable 实例，并向其中插入了几个键值对。然后，我们使用 get 方法根据键获取值，使用 containsKey 方法检查键是否存在。我们还展示了如何遍历 Hashtable 中的所有键值对，并使用 remove 方法删除了一个键值对。