关于在Java中实现自己的HashMap的问题

Question

我正在做一项作业，我必须实现自己的HashMap。在赋值文本中，它被描述为一个列表数组，每当你想添加一个元素时，它在数组中的位置由它的哈希代码决定。在我的例子中，它是来自电子表格的位置，所以我只取columnNumber+rowNumber，然后将其转换为字符串，然后转换为int，作为哈希代码，然后将其插入数组中。当然，它是以节点（键、值）的形式插入的，其中键是单元的位置，值是单元的值

但我必须说，我不明白为什么我们需要一系列列表，因为如果我们最终得到一个包含多个元素的列表，它不会大大增加查找时间吗？那么，它不应该是一组节点吗

我还发现了Java中HashMap的这个实现：

public class HashEntry {
      private int key;
      private int value;

      HashEntry(int key, int value) {
            this.key = key;
            this.value = value;
      }     

      public int getKey() {
            return key;
      }

      public int getValue() {
            return value;
      }
}

public class HashMap {
  private final static int TABLE_SIZE = 128;

  HashEntry[] table;

  HashMap() {
        table = new HashEntry[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
              table[i] = null;
  }

  public int get(int key) {
        int hash = (key % TABLE_SIZE);
        while (table[hash] != null && table[hash].getKey() != key)
              hash = (hash + 1) % TABLE_SIZE;
        if (table[hash] == null)
              return -1;
        else
              return table[hash].getValue();
  }

  public void put(int key, int value) {
        int hash = (key % TABLE_SIZE);
        while (table[hash] != null && table[hash].getKey() != key)
              hash = (hash + 1) % TABLE_SIZE;
        table[hash] = new HashEntry(key, value);
  }
}

put方法首先查看表[hash]是否正确，如果表[hash]不是空的，如果其中的内容没有得到键，输入到方法put中，那么它会转到表[（hash+1）%table_SIZE]。但如果它是同一个键，它只会覆盖该值。那么这是正确理解的吗？是因为get和put方法使用相同的方法来查找数组中的位置，所以给定相同的键，它们会在数组中的相同位置结束吗

我知道这些问题可能有点基本，但我已经花了相当多的时间试图解决这个问题，为什么任何帮助都将不胜感激

编辑

因此，现在我已经尝试通过一个节点类自己实现HashMap，它只是 用一个键和一个对应的值构造一个节点，它还有一个getHashCode方法，我只是将这两个值连接在一起

我还构建了一个SingleLinkedList（以前作业的一部分），我将其用作存储桶

我的Hash函数就是hashCode%hashMap。长度

这是我自己的实现，你怎么看

package spreadsheet; 

public class HashTableMap {

  private SinglyLinkedListMap[] hashArray;
  private int size;


  public HashTableMap() {
    hashArray = new SinglyLinkedListMap[64];
    size = 0;  
  }


  public void insert(final Position key, final Expression value) {

      Node node = new Node(key, value); 
      int hashNumber = node.getHashCode() % hashArray.length;       
      SinglyLinkedListMap bucket = new SinglyLinkedListMap();
      bucket.insert(key, value);
      if(hashArray[hashNumber] == null) {
        hashArray[hashNumber] = bucket;
        size++; 
      }
      if(hashArray[hashNumber] != null) {
        SinglyLinkedListMap bucket2 = hashArray[hashNumber];
        bucket2.insert(key, value);
        hashArray[hashNumber] = bucket2;
        size++; 
      }
      if (hashArray.length == size) {
          SinglyLinkedListMap[] newhashArray = new SinglyLinkedListMap[size * 2];
      for (int i = 0; i < size; i++) {
          newhashArray[i] = hashArray[i];
      }
      hashArray = newhashArray;
    }
  } 

  public Expression lookUp(final Position key) {
      Node node = new Node(key, null); 
      int hashNumber = node.getHashCode() % hashArray.length;
      SinglyLinkedListMap foundBucket = hashArray[hashNumber];
      return foundBucket.lookUp(key); 
  }
 }

---

查找时间应该在O（1）左右，所以我想知道是不是这样？如果不是的话，在这方面我该如何改进呢

Answer 1

{}通常被称为bucket，是处理冲突的一种方式。当两个数据元素具有相同的哈希代码mod TABLE SIZE时，它们会发生冲突，但两者都必须存储

更糟糕的冲突是两个不同的数据点具有相同的key——这在哈希表中是不允许的，一个将覆盖其他数据点。如果只是将行添加到列，那么（2,1）和（1,2）都将有一个键3，这意味着它们不能存储在同一个哈希表中。如果不使用分隔符将字符串连接在一起，那么问题在于（12,1）与（1,21）——两者都有带分隔符（如逗号）的键“121”。所有键都是不同的

如果hashcode的mod TABLE_大小相同，则不同的键可以在相同的buck中着陆。这些列表是将两个值存储在同一个存储桶中的一种方法

Answer 2

必须有一些计划来处理哈希冲突，其中两个不同的键落在同一个桶中，数组的同一个元素中

最简单的解决方案之一是为每个bucket保留一个条目列表

如果你有一个好的散列算法，并且确保bucket的数量大于元素的数量，那么你应该得到大多数bucket都有零个或一个项目的结果，所以列表搜索应该不会花费太长时间。如果列表变得太长，是时候用更多的存储桶来重新存储数据了