2016-05-03 4 views
3

私は、ハッシュマップに新しいランダムキーを入れたいときに何回比較を行うかを数えるメソッドを作りたいと思っています。私はマップに新しいキーを置くために使用されるコードは以下の通りです:ハッシュマップに新しいキーを入力しようとすると、何の比較が行われますか?

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

削除されたエントリのクラスは以下の通りです:

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クラスは、2つのint型の変数、int型のキーを持っていますint値です。 どのように私は比較を数えることができますか? これは私が私のメインでやったものです:

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

     int key = 0; 

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

何の比較? HashMapクラスのバイトコードを計測するためのJavaエージェントの作成を見てください。 – Roman

+0

新しいキーを入れようとすると、@Romanの比較が行われる –

+0

@AsukaMatseliあなた自身で 'HashMap'を手動で実装していますか?' Java'はすでに実装されていますか? –

答えて

1

あなたは比較のカウントを保持し、その値を返す新しいput()メソッドを実装することができ、このCustomHashMapでは、独自のCustomHashMap

を書くことができます。

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

OPコードをもう一度見てみると、それはおそらく完全にカスタムの実装です –

+0

@StephenC fixed –

2

(私は、これはいくつかの種類の学習運動であると仮定している既存のMap実装を使用するか、延長するしたがってアドバイスは無関係です。)

簡単な答えは、キーを「比較」するたびにカウンターを増やすことです。あなたは、インラインを行うことができ、またはあなたは、このような小さなヘルパーメソッドを自分で書くことができる:

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)) 

本当にこの問題に対する巧妙な解決策はありません。

関連する問題