小白学算法-数据结构和算法教程: 使用开放寻址线性探测实现自己的哈希表

Java 中使用链接实现哈希表

所有数据结构都有其自身的特点，例如，当需要快速搜索元素（在log（n）中）时，会使用BST。当需要在恒定时间内获取最小或最大元素时，使用堆或优先级队列。类似地，哈希表用于在恒定时间内获取、添加和删除元素。在继续实施方面之前，任何人都必须清楚哈希表的工作原理。因此，这里是哈希表工作的简要背景，还应该注意的是，我们将互换使用哈希映射和哈希表术语，尽管在 Java 中哈希表是线程安全的，而 HashMap 不是。

背景：每个哈希表都以（键，值）组合的形式存储其数据。有趣的是，哈希表中的每个键都是唯一的，但值可以重复，这意味着其中存在的不同键的值可以相同。现在，当我们在数组中观察以获取值时，我们提供与该数组中的值相对应的位置/索引。在哈希表中，我们不使用索引，而是使用键来获取与该键对应的值。

每次生成密钥时。密钥被传递给哈希函数。每个哈希函数都有两部分：哈希码和压缩器。 

哈希码是一个整数（随机或非随机）。在Java中，每个对象都有自己的哈希码。我们将在哈希函数中使用 JVM 生成的哈希码，并根据哈希表的大小对哈希码取模 (%) 来压缩哈希码。所以模运算符在我们的实现中是一个压缩器。

现在我们要做的是制作一个与哈希表的特定桶相对应的链表，以容纳映射到同一桶的不同键对应的所有值。 

现在可能存在一种情况，所有键都映射到同一个存储桶，并且我们有一个来自单个存储桶的 n（哈希表的大小）大小的链表，所有其他存储桶都是空的，这是最坏的情况其中哈希表充当链表，搜索的时间复杂度为 O(n)。 

哈希冲突和负载因子

那么我们该怎么办？

负载系数：如果 n 是我们最初决定填充的桶总数，假设为 10，现在假设其中 7 个已被填充，那么负载系数为 7/10=0.7。 

在我们的实现中，每当我们向哈希表添加键值对时，我们都会检查负载因子，如果它大于 0.7，我们就会将哈希表的大小加倍。

执行：

哈希节点数据类型

我们将尝试制作一个通用映射，而不对键和值的数据类型施加任何限制。此外，每个哈希节点都需要知道它在链表中指向的下一个节点，因此还需要一个下一个指针。

我们计划保留在哈希图中的函数如下： 

• get(K key) ：如果HT（Hast Table ）中存在该键，则返回该键对应的值
• getSize()：返回 HT 的大小
• add()：向 HT 添加一个新的有效键、值对，如果已经存在则更新该值
• remove()：删除键、值对
• isEmpty()：如果大小为零则返回 true

ArrayList<HashNode<K, V>> Bucket = new ArrayList<>();

实现辅助函数来获取键的索引，以避免其他函数（如 get、add 和 remove）中的冗余。该函数使用内置的java函数生成哈希码，我们将哈希码压缩HT的大小，使得索引在HT的大小范围内

get（）

get 函数仅将键作为输入，如果该键存在于表中，则返回相应的值，否则返回 null。步骤是：  

• 检索输入的key，找到HT中的索引
• 遍历 HT 对应的链表，如果找到该值则返回该值，否则如果完全遍历该链表而不返回，则意味着该值不存在于表中，无法获取，因此返回 null

remove（）

• 使用辅助函数获取输入键对应的索引
• 链表的遍历和get()类似，但是这里的特殊之处是在查找的同时还需要删除key，会出现两种情况
• 如果要删除的键位于链表的头部
• 如果要移除的钥匙不在头部而是在其他地方

add（）

现在来看看整个实现中最有趣和最具挑战性的功能。这很有趣，因为当负载因子高于我们指定的值时，我们需要动态增加列表的大小。  

• 就像删除步骤直到遍历和添加一样，两种情况（在头点或非头点添加）保持不变。
• 接近尾声时，如果负载系数大于 0.7
• 我们将数组列表的大小加倍，然后在现有键上递归调用 add 函数，因为在我们的例子中，生成的哈希值使用数组的大小来压缩我们使用的内置 JVM 哈希码，因此我们需要获取新的索引现有的钥匙。理解这一点非常重要，请重新阅读本段，直到您掌握 add 函数中发生的情况为止。

如果对应于特定存储桶的链表往往变得太长，Java 在其自己的哈希表实现中会使用二叉搜索树。 

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)，因为它不依赖于哈希表中存储的项目数量。

size 复杂度

时间复杂度：O(1)
空间复杂度：O(1)