java - Java哈希表实现

Question

在我的哈希表实现中，我的哈希函数只取我传递的项目的值，调用 hashCode（从 Object 类继承），并取模内部数组的大小。这个内部数组是一个 LinkedLists 数组。现在，如果我的 LinkedList 变得太长（并且我的效率开始从 O(1) 下降到 O(n)），我认为简单地增加数组的大小是有意义的。但这就是我的问题所在，因为我说过我对传递的项目进行哈希处理并取模数组的大小（刚刚改变）。如果我继续，哈希值会不会指向数组中的不同索引，从而失去引用哈希表中项目的能力？我怎么能解决这个问题？

Answer 1

您需要每个项目的实际哈希值，以便您可以将它们放入调整大小表中的正确哈希链中。（否则，正如您所观察到的，这些项目可能最终会出现在错误的链上，因此无法定位。）

有两种方法可以解决这个问题：

• 您可以在将每个项目添加到新表时简单地重新计算其哈希值。

• 您可以为散列链中的每个项目保留原始散列值的副本。这就是标准 JavaHashMap实现所做的……至少在我看过的版本中。

（后者是时间与空间的权衡，如果你的项目有一个昂贵的方法，它可能会hashcode带来很大的回报。但是，如果你在哈希表的生命周期内摊销，这种优化不会改变“大 O”复杂性任何公共 API 方法……假设您的哈希表调整大小是指数级的；例如，您每次大约将表大小加倍。）

Answer 2

package com.codewithsouma.hashtable;

import java.util.LinkedList;

public class HashTable {

    private class Entry {
        private int key;
        private String value;

        public Entry(int key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    LinkedList<Entry>[] entries = new LinkedList[5];

    public void put(int key, String value) {
        var entry = getEntry(key);
        if (entry != null){
            entry.value = value;
            return;
        }

        getOrCreateBucket(key).add(new Entry(key,value));
    }

    public String get(int key) {
        var entry = getEntry(key);
        return  (entry == null) ? null : entry.value;
    }

    public void remove(int key) {
       var entry = getEntry(key);
       if (entry == null)
           throw new IllegalStateException();

      getBucket(key).remove(entry);
    }

    private LinkedList<Entry> getBucket(int key){
        return entries[hash(key)];
    }

    private LinkedList<Entry> getOrCreateBucket(int key){
        var index = hash(key);
        var bucket = entries[index];
        if (bucket == null) {
            entries[index] = new LinkedList<>();
            bucket = entries[index];
        }
        return bucket;
    }

    private Entry getEntry(int key) {
        var bucket = getBucket(key);
        if (bucket != null) {
            for (var entry : bucket) {
                if (entry.key == key) return entry;
            }
        }
        return null;
    }

    private int hash(int key) {
        return key % entries.length;
    }

}