当我尝试在哈希映射中输入新密钥时，如何计算比较次数？

Question

我想创建一种方法来计算当我想在我的哈希映射中放置一个新的随机密钥时进行了多少次比较。我用来在地图中放置新键的代码如下：

public void put(int key, int value) { 
          int hash = (key % table.length);
          int initialHash = -1;
          int indexOfDeletedEntry = -1;

          while (hash != initialHash
                      && (table[hash] == DeletedEntry.getUniqueDeletedEntry()
                      || table[hash] != null
                      && table[hash].getKey() != key)) {
                if (initialHash == -1)
                      initialHash = hash;
                if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
                      indexOfDeletedEntry = hash;
                hash = (hash + 1) % table.length;
          }
          if ((table[hash] == null || hash == initialHash)
                      && indexOfDeletedEntry != -1) {
                table[indexOfDeletedEntry] = new HashEntry(key, value);
                size++;
          } else if (initialHash != hash)
                if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
                           && table[hash] != null && table[hash].getKey() == key)
                      table[hash].setValue(value);
                else {
                      table[hash] = new HashEntry(key, value);
                      size++;
                }
          if (size >= maxSize)
                resize();
    }

已删除条目的 class 如下：

public class DeletedEntry extends HashEntry {

    private static DeletedEntry entry = null;

    private DeletedEntry() {
          super(-1, -1);
    }

    public static DeletedEntry getUniqueDeletedEntry() {
          if (entry == null)
                entry = new DeletedEntry();
          return entry;
    }

}

此外，HashEntry class 有 2 个 int 变量，int key 和 int value。知道我如何计算比较吗？这就是我在主程序中所做的：

Random rand = new Random();
        int[] comparisons = new int[20]; 

        int key = 0;

        for (int k=0;k<20;k++){
            key = rand.nextInt(1000) + 1; 
        }

Answer 1

^{（我假设这是某种学习练习。因此使用或扩展现有 Map 实现的建议无关紧要。）}

简单的答案是每次 "compare" 按键时都会增加一个计数器。您可以内联执行该操作，或者您可以自己编写一个像这样的小辅助方法：

  private boolean compareKeys(int key1, int key2) {
      count++;
      return key1 == key2;
  }

然后更改您的代码以在每次比较键时使用此助手；例如

  while (hash != initialHash
              && (table[hash] == DeletedEntry.getUniqueDeletedEntry()
              || table[hash] != null
              && !compareKeys(table[hash].getKey(), key))) {

和

  if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
       && table[hash] != null 
       && compareKeys(table[hash].getKey(), key))

这个问题真的没有什么妙招。

Answer 2

你可以自己写CustomHashMap

在此 CustomHashMap 中，您可以实现一个新的 put() 方法来记录比较，然后 returns 该值。

public int put(int key, int value) { 
          int hash = (key % table.length);
          int initialHash = -1;
          int indexOfDeletedEntry = -1;
          int numberOfComparisons = 1;

          while (hash != initialHash
                      && (table[hash] == DeletedEntry.getUniqueDeletedEntry()
                      || table[hash] != null
                      && table[hash].getKey() != key)) {
                numberOfComparisons++;
                if (initialHash == -1)
                      initialHash = hash;
                if (table[hash] == DeletedEntry.getUniqueDeletedEntry())
                      indexOfDeletedEntry = hash;
                hash = (hash + 1) % table.length;
          }
          if ((table[hash] == null || hash == initialHash)
                      && indexOfDeletedEntry != -1) {
                table[indexOfDeletedEntry] = new HashEntry(key, value);
                size++;
          } else if (initialHash != hash)
                if (table[hash] != DeletedEntry.getUniqueDeletedEntry()
                           && table[hash] != null && table[hash].getKey() == key)
                      table[hash].setValue(value);
                else {
                      table[hash] = new HashEntry(key, value);
                      size++;
                }
          if (size >= maxSize)
                resize();
          return numberOfComparisons;
 }

当我尝试在哈希映射中输入新密钥时，如何计算比较次数？

How can i count comparisons are made when i try to enter a new key in a hash map?

java

dictionary

hash

hashmap

hashtable