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

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

// 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());
	}
}