Asuka Matseli Asuka Matseli - 7 months ago 11
Java Question

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

I want to make a method to count how many comparisons are made when i want to put a new random key in my hash map . The code I used to put new keys in the map is the following :

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();
}


The class for the deleted entry is the following :

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;
}

}


Also , HashEntry class has 2 int variables , int key and int value .
Any Idea how i can count the comparisons ?
This is what I've done in my main:

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

You can write your own CustomHashMap which extends HashMap

In this CustomHashMap you can implement a new put() method that keeps count of the comparisons and then returns that value.

public class CustomHashMap extends HashMap {

/*
*Put constructors here
*/

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;
    }
}
Comments