所有数据结构都有其自身的特点,例如,当需要快速搜索元素(在log(n)中)时,会使用BST。当需要在恒定时间内获取最小或最大元素时,使用堆或优先级队列。类似地,哈希表用于在恒定时间内获取、添加和删除元素。在继续实施方面之前,任何人都必须清楚哈希表的工作原理。因此,这里是哈希表工作的简要背景,还应该注意的是,我们将互换使用哈希映射和哈希表术语,尽管在 Java 中哈希表是线程安全的,而 HashMap 不是。
背景:每个哈希表都以(键,值)组合的形式存储其数据。有趣的是,哈希表中的每个键都是唯一的,但值可以重复,这意味着其中存在的不同键的值可以相同。现在,当我们在数组中观察以获取值时,我们提供与该数组中的值相对应的位置/索引。在哈希表中,我们不使用索引,而是使用键来获取与该键对应的值。
每次生成密钥时。密钥被传递给哈希函数。每个哈希函数都有两部分:哈希码和压缩器。
哈希码是一个整数(随机或非随机)。在Java中,每个对象都有自己的哈希码。我们将在哈希函数中使用 JVM 生成的哈希码,并根据哈希表的大小对哈希码取模 (%) 来压缩哈希码。所以模运算符在我们的实现中是一个压缩器。
现在我们要做的是制作一个与哈希表的特定桶相对应的链表,以容纳映射到同一桶的不同键对应的所有值。
现在可能存在一种情况,所有键都映射到同一个存储桶,并且我们有一个来自单个存储桶的 n(哈希表的大小)大小的链表,所有其他存储桶都是空的,这是最坏的情况其中哈希表充当链表,搜索的时间复杂度为 O(n)。
哈希冲突和负载因子
那么我们该怎么办?
负载系数:如果 n 是我们最初决定填充的桶总数,假设为 10,现在假设其中 7 个已被填充,那么负载系数为 7/10=0.7。
在我们的实现中,每当我们向哈希表添加键值对时,我们都会检查负载因子,如果它大于 0.7,我们就会将哈希表的大小加倍。
我们将尝试制作一个通用映射,而不对键和值的数据类型施加任何限制。此外,每个哈希节点都需要知道它在链表中指向的下一个节点,因此还需要一个下一个指针。
我们计划保留在哈希图中的函数如下:
ArrayList<HashNode<K, V>> Bucket = new ArrayList<>();
实现辅助函数来获取键的索引,以避免其他函数(如 get、add 和 remove)中的冗余。该函数使用内置的java函数生成哈希码,我们将哈希码压缩HT的大小,使得索引在HT的大小范围内
get 函数仅将键作为输入,如果该键存在于表中,则返回相应的值,否则返回 null。步骤是:
现在来看看整个实现中最有趣和最具挑战性的功能。这很有趣,因为当负载因子高于我们指定的值时,我们需要动态增加列表的大小。
如果对应于特定存储桶的链表往往变得太长,Java 在其自己的哈希表实现中会使用二叉搜索树。
// Java程序演示了使用链式法解决碰撞检测的自定义哈希表实现
import java.util.ArrayList;
import java.util.Objects;
// 链的节点
class HashNode<K, V> {
K key;
V value;
final int hashCode;
// 下一个节点的引用
HashNode<K, V> next;
// 构造函数
public HashNode(K key, V value, int hashCode)
{
this.key = key;
this.value = value;
this.hashCode = hashCode;
}
}
// 表示整个哈希表的类
class Map<K, V> {
// bucketArray 用于存储链数组
private ArrayList<HashNode<K, V> > bucketArray;
// 当前数组列表的容量
private int numBuckets;
// 当前数组列表的大小
private int size;
// 构造函数(初始化容量、大小和空链。
public Map()
{
bucketArray = new ArrayList<>();
numBuckets = 10;
size = 0;
// 创建空链
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
}
public int size() { return size; }
public boolean isEmpty() { return size() == 0; }
private final int hashCode (K key) {
return Objects.hashCode(key);
}
// 这个实现了一个哈希函数,用于找到一个键的索引
private int getBucketIndex(K key)
{
int hashCode = hashCode(key);
int index = hashCode % numBuckets;
index = index < 0 ? index * -1 : index;
return index;
}
// Method to remove a given key
public V remove(K key)
{
// 将哈希函数应用于给定的键以找到索引
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
// 获取链的头部
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 在其链中搜索键
HashNode<K, V> prev = null;
while (head != null) {
// 如果找到密钥
if (head.key.equals(key) && hashCode == head.hashCode)
break;
// 否则继续在链中移动
prev = head;
head = head.next;
}
// 如果键不存在
if (head == null)
return null;
// 缩小
size--;
// 删除键
if (prev != null)
prev.next = head.next;
else
bucketArray.set(bucketIndex, head.next);
return head.value;
}
// 返回键值
public V get(K key)
{
// 找到给定键的链表头部
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 在链中搜索钥匙
while (head != null) {
if (head.key.equals(key) && head.hashCode == hashCode)
return head.value;
head = head.next;
}
// 如果找不到键
return null;
}
// 向哈希表添加键值对
public void add(K key, V value)
{
// 找到给定键的链表头部
int bucketIndex = getBucketIndex(key);
int hashCode = hashCode(key);
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 检查键是否已经存在
while (head != null) {
if (head.key.equals(key) && head.hashCode == hashCode) {
head.value = value;
return;
}
head = head.next;
}
// 将钥匙插入链中
size++;
head = bucketArray.get(bucketIndex);
HashNode<K, V> newNode
= new HashNode<K, V>(key, value, hashCode);
newNode.next = head;
bucketArray.set(bucketIndex, newNode);
// 如果负载系数超过阈值,则将哈希表大小加倍
if ((1.0 * size) / numBuckets >= 0.7) {
ArrayList<HashNode<K, V> > temp = bucketArray;
bucketArray = new ArrayList<>();
numBuckets = 2 * numBuckets;
size = 0;
for (int i = 0; i < numBuckets; i++)
bucketArray.add(null);
for (HashNode<K, V> headNode : temp) {
while (headNode != null) {
add(headNode.key, headNode.value);
headNode = headNode.next;
}
}
}
}
// 测试Map类的驱动方法
public static void main(String[] args)
{
Map<String, Integer> map = new Map<>();
map.add("this", 1);
map.add("coder", 2);
map.add("this", 4);
map.add("hi", 5);
System.out.println(map.size());
System.out.println(map.remove("this"));
System.out.println(map.remove("this"));
System.out.println(map.size());
System.out.println(map.isEmpty());
}
}
该方法将一个键值对添加到哈希表中。该方法的时间复杂度为O(1),因为它是常数时间。空间复杂度为 O(n),因为它会随着哈希表中存储的项目数量而增加。
时间复杂度:O(1) 空间复杂度:O(1)
此方法从哈希表中删除给定的键。该方法的时间复杂度为O(1),因为它是常数时间。空间复杂度为 O(1),因为它不依赖于哈希表中存储的项目数量。
时间复杂度:O(1) 空间复杂度:O(1)
此方法返回哈希表中给定键的值。该方法的时间复杂度为O(1),因为它是常数时间。空间复杂度为 O(1),因为它不依赖于哈希表中存储的项目数量。
时间复杂度:O(1) 空间复杂度:O(1)