如何为Java中的HashMap写一个put方法？

Question

我一直在为我的 HashMap 代码编写一个 put 方法，但我似乎无法理解问题所在。

我的说明如下：

如果给定键已存在于 HashMap 中，则应将旧值替换为新值。如果发生冲突，应使用线性探测来查找下一个 "open" 数组索引。如果一个额外的元素将被添加到 map 并且加载因子大于或等于 MAX_LOAD_FACTOR，那么在识别 bucket 以尝试存储额外元素之前应该重新散列 map。

因此，我不确定是我的 put 方法没有正常工作，还是我的 rehash 方法。因此，我要 post 他们两个。希望它有意义。

public class HashMap<K,V>
{
private final double MAX_LOAD_FACTOR = 0.75;
private HashEntry[] elementData;
private final HashEntry REMOVED = new HashEntry(null, null);
private int size;

public HashMap()
{
    this.elementData = new HashMap.HashEntry[10];
    size = 0;
}
public void put(K key, V value)
{
int hash = hashFunction(key);
    if (!containsKey(key))
    {
        if(loadFactor() >= MAX_LOAD_FACTOR)
        {
            rehash();
        }
        while(elementData[hash] != null)
        {
            hash = (hash + 1) % elementData.length;
        }
        elementData[hash] = new HashEntry(key, value);
        size++;
    }
    else
    {
        while(elementData[hash] != null || (elementData[hash] != REMOVED && !elementData[hash].getKey().equals(key)))
        {
            hash = (hash + 1) % elementData.length;
        }
            elementData[hash].value = value;
    }
}
 private int hashFunction(Object key)
{
    return Math.abs(key.hashCode()) % elementData.length;
}
private double loadFactor()
{
    return (double) size / elementData.length;
}
private void rehash()
{
    HashEntry[] oldElementData = elementData;
    elementData = new HashMap.HashEntry[2 * oldElementData.length];
    size = 0;
    for (int i = 0; i < oldElementData.length; i++)
    {
        HashEntry current = oldElementData[i];
        if(current != null)
        {
            put(current.getKey(), current.getValue());
        }
    }
}
 public class HashEntry
{
    private K key;
    private V value;

    public  HashEntry(K key, V value)
    {
        this.key = key;
        this.value = value;
    }
    public K getKey()
    {
        return key;
    }
    public V getValue()
    {
        return value;
    }
 }
}

记下任何有帮助的想法。谢谢。

Answer 1

我发现我的问题是在重新散列后需要重新分配散列，因此我创建了这个。

public void put(K key, V value)
{
    int hash = hashFunction(key);
    if (!containsKey(key))
    {
        if(loadFactor() >= MAX_LOAD_FACTOR)
        {
            rehash();
        }
        hash = hashFunction(key);
        while(elementData[hash] != null && !elementData[hash].equals(REMOVED))
        {
                hash = (hash + 1) % elementData.length;
        }
        elementData[hash] = new HashEntry(key, value);
        size++;
    }
    else
    {
        while(elementData[hash] != null && (!elementData[hash].equals(REMOVED) && !elementData[hash].getKey().equals(key)))
        {
            hash = (hash + 1) % elementData.length;
        }
            elementData[hash].value = value;
    }
}

就是这样

如何为Java中的HashMap写一个put方法？

How to write a put method for a HashMap in Java?

java

hash

hashmap

hashcode