java - Java - 编写自己的 HashMap

问题描述

一段时间以来，我一直致力于编写自己的 HashMap。一切都很顺利，直到我停止编写“put”方法。我不确定我的 rehash 方法是否是导致测试用例失败的原因，或者它是否是我的实际 put 方法。我使用的测试用例来自 JUnit 库。我用来存储地图值的数据结构是一个 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;
}

这是我写的rehash算法。我不完全确定它是否正确编写：

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”应该代表每个测试用例的哈希图中的每个键。这是类代码：

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

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

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

感谢所有帮助 - Bob

标签： javajunithashmap

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

哈希码的本质是你不能假设即使在重新散列之后也不会发生冲突。允许两个不相等的对象返回相同的哈希码。
您的put实现正在遍历所有地图条目。使用哈希的全部意义在于使用它们来索引数组。
没有什么可以阻止哈希码返回负值的实现。您对 % 的使用不能保证返回正值。

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

从非常简单的测试用例开始（例如，为不存在的键获取空值、获取值、覆盖值）
一旦这些工作构建到更复杂的情况（冲突哈希码，重新哈希等）。
确保每个测试都测试一件事。
确保每个测试都设置自己的数据
在担心复杂的用例之前先让简单的事情发挥作用。
每次进行更改时运行全套测试。

java - Java - 编写自己的 HashMap - “put”方法

问题描述

解决方案

推荐阅读