为什么我无法在哈希表的链表数组中添加新条目？

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 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（）也会生成负值。

访问哈希表时（即使用myTable [index]时），您将获得ArrayIndexOutOfBoundsExcception。

处理负指数使用

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

Answer 2

将您的哈希代码更新为以下。它应该工作。

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

这里我们使用密钥和表容量的实际哈希码进行按位AND运算。这将确保表容量的内部界限。

注意：可能会为多个密钥生成相同的哈希。你需要详细说明处理这种情况的逻辑。