Java - 编写自己的 HashMap - "put"方法

Question

我一直致力于编写自己的 HashMap 一段时间了。一切都很顺利，直到我停止编写“put”方法。我不确定是否是我的 rehash 方法导致测试用例失败，或者它是否是我实际的 put 方法。我使用的测试用例来自 JUnit 库。我用来存储 map 值的数据结构是 MyMapEntry 对象的数组(它实现了 Entry 类，我将提供它的代码)。我已经包含了与此问题相关的所有代码。

入门级:

class MyMapEntry implements Entry<K,V>{

    private K key;
    private V value;

    public MyMapEntry(K k) {
        key = k;
    }

    public MyMapEntry(K k, V v) {
        this(k);
        value = v;
    }
    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V v) {
        V oldValue = value;
        value = v;
        return oldValue;
    }

    public boolean equals(MyMapEntry bob) {
        return key.equals(bob.key);
    }

}

put方法:

@Override
public V put(K key, V value) {
    for (int i = 0; i < entryArray.length; i++) {
        MyMapEntry entryInArray = entryArray[i];
        if (entryInArray != null) {
            if (entryInArray.getKey().hashCode() == entry.getKey().hashCode()) {
                entryInArray.setValue(value);
                return value;
            }
        }
    }
    if (entryArray[index] != null) { // Rehash if there is a collision
        rehash();
        index = entry.hashCode() % size;
    }
    entryArray[index] = entry;
    actualSize++;
    return value;
}

这是我编写的重新哈希算法。我不完全确定它写得正确:

private void rehash() {
    entryArray = Arrays.copyOf(entryArray, entryArray.length * 2);
    MyMapEntry[] tempArray = Arrays.copyOf(entryArray, entryArray.length);
    Arrays.fill(entryArray, null);
    for (int i = 0; i < tempArray.length; i++) {
        MyMapEntry entry = tempArray[i];
        if (entry != null) {
            int index = entry.hashCode() % tempArray.length;
            entryArray[index] = entry;
        }
    }
    size = entryArray.length;
}

这是实际构建我创建的数据结构的测试方法:

public HashMapAPlus<MyDumbyData, String> buildReHashHashMap(int l){
    HashMapAPlus<MyDumbyData, String> bob = new HashMapAPlus<>(l);
    MyDumbyData d = new MyDumbyData("Bobby", Color.red);
    bob.put(d,  "Love ya");
    d = new MyDumbyData("Ralph", Color.blue);
    bob.put(d,  "Snake");
    d = new MyDumbyData("Blake", Color.black);
    bob.put(d,  "Something");
    d = new MyDumbyData("Roman", Color.white);
    bob.put(d,  "Something else");
    d = new MyDumbyData("Sam", Color.magenta);
    bob.put(d,  "Nothing much");
    d = new MyDumbyData("Victor", Color.cyan);
    bob.put(d,  "Something more");
    d = new MyDumbyData("Nick", Color.yellow);
    bob.put(d,  "Don't know");
    d = new MyDumbyData("Frank", Color.orange);
    bob.put(d,  "Not sure");
    d = new MyDumbyData("Aaron", Color.green);
    bob.put(d,  "Not at all");
    d = new MyDumbyData("Brit", Color.red);
    bob.put(d,  "Not sure what");
    return bob;
}

“MyDumbyData”应该代表每个测试用例的 HashMap 中的每个键。这是类代码:

public class MyDumbyData {
    private String name;
    private Color color;

    public MyDumbyData(String n, Color c) {
        name = n;
        color = c;
    }

    public String getName() {
        return name;
    }

    public Color getColor() {
        return color;
    }

    public boolean equals(MyDumbyData dd) {
        return name.equals(dd.getName()) && color.equals(dd.getColor());
    }

    public int hashCode() {
        return name.hashCode() + color.hashCode();
    }

    public String toString() {
        return name+": "+color.toString();
    }
}

最后，这是失败的测试用例:

@Test
public void testAddGet1() {
    HashMapAPlus<MyDumbyData, String> bob = this.buildReHashHashMap(10);
    assertEquals(10, bob.size());
    MyDumbyData d = new MyDumbyData("Bobby", Color.red);
    assertEquals("Love ya", bob.get(d));          // This is where the first assertion error is.
    d = new MyDumbyData("Ralph", Color.blue);
    assertEquals("Snake", bob.get(d));
    d = new MyDumbyData("Blake", Color.black);
    assertEquals("Something", bob.get(d));
    d = new MyDumbyData("Roman", Color.white);
    assertEquals("Something else", bob.get(d));
    d = new MyDumbyData("Sam", Color.magenta);
    assertEquals("Nothing much", bob.get(d));
    d = new MyDumbyData("Victor", Color.cyan);
    assertEquals("Something more", bob.get(d));
    assertNull(bob.getLinkedListArray());
    assertNotNull(bob.getMapEntryArray());
}

请注意，如果第一个断言错误发生的行被注释掉，则测试用例通过。

如果我提供了太多代码，我深表歉意。只是所有这些代码都用于最终结果。

感谢所有帮助- 鲍勃

Answer 1

不幸的是，您需要查看很多错误:

1. 哈希码的本质是，您不能假设即使在重新哈希后也不会发生冲突。允许两个不相等的对象返回相同的哈希码。
2. 您的 put 实现正在迭代所有映射条目。使用哈希值的全部目的是使用它们来索引数组。
3. 没有什么可以阻止哈希码的实现返回负值。您对 % 的使用不能保证返回正值。

实际上我还可以看到很多其他问题。但我建议您采用不同的方法来构建和调试代码。您陷入了编写所有代码然后构建一个测试所有内容的复杂测试用例的陷阱。相反:

• 从非常简单的测试用例开始(例如，获取不存在的键的空值、放置获取值、覆盖值)
• 一旦这些工作正常，就可以构建更复杂的情况(哈希码冲突、重新哈希等)。
• 确保每个测试都测试一件事。
• 确保每个测试都设置自己的数据
• 先解决简单的问题，然后再担心复杂的用例。
• 每次进行更改时都运行全套测试。