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

Question

我正在进行一项任务,我必须实现自己的HashMap.在赋值文本中,它被描述为一个列表数组,每当你想要添加一个元素时,它最终在数组中的位置由其hashCode决定.在我的例子中,它是电子表格中的位置,所以我刚刚使用了columnNumber + rowNumber,然后将其转换为String,然后转换为int,作为hashCode,然后我将其插入到Array中.它当然以节点(键,值)的形式插入,其中键是单元格的位置,值是单元格的值.

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

我也发现了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]中查找是正确的,如果那不是空的,如果那里没有得到密钥,则在put方法中输入,然后移动到表[ (hash + 1)%TABLE_SIZE].但如果它是相同的键,它只是覆盖该值.这是正确理解的吗？是不是因为get和put方法使用相同的方法来查找数组中的位置,给定相同的键它们最终会在数组中的相同位置？

我知道这些问题可能有点基本,但我花了很多时间试图解决这个问题,为什么任何帮助都会非常感激!

编辑

所以现在我尝试通过Node类自己实现HashMap,它只是构造一个带有键和相应值的节点,它还有一个getHashCode方法,我只是将这两个值相互连接起来.

我还构建了一个SinglyLinkedList(前一个任务的一部分),我将其用作存储桶.

而我的Hash函数就是hashCode%hashMap.length.

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

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

您必须有一些计划来处理哈希冲突,其中两个不同的键落在同一个桶中,即阵列的相同元素.

最简单的解决方案之一是保留每个存储桶的条目列表.

如果你有一个好的散列算法,并确保桶的数量大于元素的数量,你最终应该有大多数桶有零个或一个项目,所以列表搜索不应该花费很长时间.如果列表变得太长,则需要重新使用更多存储桶来传播数据.