Почему я не могу добавить новую запись в массив связанного списка для моей хэш-таблицы?

Question

Я пытаюсь создать простую хеш-таблицу, чтобы узнать больше о хешировании, и для этого я использую массив LinkedList.

Ниже приведен код, который я использую:

public class HashTable {

protected LinkedList<Entry>[] myTable;

  public HashTable(int capacity) {
    if(capacity < 0)
        throw new IllegalArgumentException();

    myTable = new LinkedList[capacity];
  }

  public void put(String key, Integer value) {
    int index = hash(key);
    //System.out.println(index);

    //if(myTable[index] == null) {
        myTable[index] = new LinkedList<Entry>();
        Entry entry = new Entry(key, value);
        myTable[index].add(entry);
    //}
  }

  public boolean containsKey(String key) {
    int index = hash(key);
    //System.out.println(index);

    for(Entry e : myTable[index]) {
        System.out.println(e.getKey()); // to check which entries are stored
        if(e.getKey().equals(key)) {
            return true;
        }
        }

    return false;
  }

  public Integer get(String key) {
      int index = hash(key);
       //System.out.println(index);

    for(Entry entry : myTable[index]) {
        if(entry.getKey().equals(key)){
            return entry.getValue();
        }
    }

    return null;
  }


  public int getCapacity() {
    return myTable.length;
  }


  public int hash(String item) {
      return item.hashCode()%(this.getCapacity());
  }


  public static void main(String[] args) {
      HashTable hashTable = new HashTable(10);
      hashTable.put("something", 20);
      hashTable.put("new", 21);
      hashTable.put("amazing", 100);

      System.out.println(hashTable.containsKey("something"));
  }

}

Для вышеуказанного ввода я получаю следующий вывод:

удивительно
ложно

Я не могу понять, почему я не могу добавитьновые записи в связанном списке по индексу.Я просто храню только одну запись с индексом 0 для указанных выше входных данных, а не другие.

Буду признателен за любую помощь.

Answer 1

обновите ваш хеш-код ниже.он должен работать.

  public int hash(String item) {
    return (this.getCapacity() - 1) & item.hashCode();
  }

Здесь мы выполняем побитовую операцию И с фактическим хеш-кодом ключа и емкостью таблицы.это обеспечит внутреннюю границу емкости таблицы.

ПРИМЕЧАНИЕ: Один и тот же хэш может быть создан для более чем одного ключа.вам нужно разработать логику, чтобы справиться с этой ситуацией.

Answer 2

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

Используйте следующий код для помещения элемента в хеш-таблицу.

public class HashTable {

protected LinkedList<Entry>[] myTable;

  public HashTable(int capacity) {
    if(capacity < 0)
        throw new IllegalArgumentException();

    myTable = new LinkedList[capacity];
  }

  public void put(String key, Integer value) {
    int index = hash(key);
    //System.out.println(index);

    if(myTable[index] == null) {
        myTable[index] = new LinkedList<Entry>();
    }
    Entry entry = new Entry(key, value);
    myTable[index].add(entry);

  }

  public boolean containsKey(String key) {
    int index = hash(key);
    //System.out.println(index);

    for(Entry e : myTable[index]) {
        System.out.println(e.getKey()); // to check which entries are stored
        if(e.getKey().equals(key)) {
            return true;
        }
        }

    return false;
  }

  public Integer get(String key) {
      int index = hash(key);
       //System.out.println(index);

    for(Entry entry : myTable[index]) {
        if(entry.getKey().equals(key)){
            return entry.getValue();
        }
    }

    return null;
  }


  public int getCapacity() {
    return myTable.length;
  }


  public int hash(String item) {
      return item.hashCode()%(this.getCapacity());
  }


  public static void main(String[] args) {
      HashTable hashTable = new HashTable(10);
      hashTable.put("something", 20);
      hashTable.put("new", 21);
      hashTable.put("amazing", 100);

      System.out.println(hashTable.containsKey("something"));
  }

}

Метод hashCode () также будет генерировать отрицательные значения.

Вы получите ArrayIndexOutOfBoundsExcception при доступе к хеш-таблице (т.е. при использовании myTable [index]).

Для обработки отрицательных индексов используйте

public int hash(String item) {
      return Math.abs(item.hashCode()%(this.getCapacity()));
}