Java - Написание собственного HashMap - метод "put"

Question

Я уже некоторое время работаю над написанием своей собственной HashMap.Все шло хорошо, пока я не остановился с написанием метода «пут».Я не уверен, что мой метод 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;
}

Вот алгоритм перефразировки, который я написал,Я не совсем уверен, что он написан правильно:

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

Обратите внимание, что если строка, где возникает первая ошибка утверждения, закомментирована,контрольный пример успешно пройден.

Прошу прощения, если предоставил слишком много кода.Просто весь этот код используется для окончательного результата.

Мы ценим всю помощь - Боб

Answer 1

К сожалению, есть много ошибок, на которые нужно взглянуть:

1. Природа хэш-кодов заключается в том, что вы не можете предполагать, что не получите коллизию даже после перефразирования.Два неравных объекта могут возвращать один и тот же хэш-код.
2. Ваша реализация put выполняет итерацию по всей записи карты.Весь смысл использования хэшей состоит в том, чтобы использовать их для индексации массива.
3. Ничто не мешает реализации хэш-кода, возвращающего отрицательные значения.Использование% не гарантирует возврата положительного значения.

На самом деле я вижу много других проблем.Но я предлагаю вам использовать другой подход к созданию и отладке вашего кода.Вы попадаете в ловушку написания всего кода и создания единого сложного контрольного примера, который проверяет всеВместо этого:

• Начните с очень простых тестовых случаев (например, получение нулевых значений для несуществующих ключей, установка получения значения, перезапись значения)
• После того, как они работают, создайтеболее сложные случаи (столкновение хеш-кодов, перефразировка и т. д.).
• Убедитесь, что каждый тест проверяет одну вещь.
• Убедитесь, что каждый тест устанавливает свои собственные данные
• Получите простые вещи, прежде чем беспокоиться о сложных случаях использования.
• Запускайте полный набор тестов каждый раз, когда вносите изменения.