2

このプログラムを実行すると

public class MyHashMapOperationsDebug {

    public static void main(String[] args) {
        MyHashMap hashMap = new MyHashMap();//MyHashMap is replica of HashMap
        for (int i=1;i<=11;i++)
        hashMap.put(i, i+100);
        }
}

そしてMyHashMap.java持っています 

void addEntry(int hash, K key, V value, int bucketIndex) {  //replica of HashMap's addEntry method  

Entry<K,V> e = table[bucketIndex];
**System.out.println("bucketIndex : " + bucketIndex);**
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

出力： 

bucketIndex : 7  
bucketIndex : 14  
bucketIndex : 4  
bucketIndex : 13  
bucketIndex : 1  
bucketIndex : 8  
bucketIndex : 2  
bucketIndex : 11  
bucketIndex : 11  
bucketIndex : 2  
bucketIndex : 8

サイズ 16 のマップに 11 個のキーしか格納されていない場合でも、一部のキーが同じバケットに移動するのはなぜですか? たとえば、インデックス 2 のバケットと 11 にはそれぞれ 2 つのキーがあります

編集: 以下の入力を読んだ後 1 つの質問: Java の HashMap と Integer が使用されている場合、上記の場合の複雑さはどうなりますか。O(1) ですか？

4

4 に答える 4

1

上記の場合、Java の HashMap と Integer を使用した場合の複雑さはどのくらいになるでしょうか。O(1) ですか？

はい。このInteger.hashcode()メソッドは、Integerそれ自体の値を返します。これは、可能なハッシュ値の空間全体に均一に分散されます。

したがって、ハッシュ テーブルのパフォーマンスは最適になります。すなわちO(1)、get事業およびO(1)（償却）put事業について。HashMapまた、一意のキーは 2^32 個しか存在しないため、それを超えるスケーリングの問題を考慮する必要はありません。

于 2013-07-07T12:02:19.373 に答える
0

たとえば、インデックス 2 のバケットと 11 にはそれぞれ 2 つのキーがあります。これは hashCollision のためです。HashMap は、すべての n 要素に対して Hash Collision がある場合、ルックアップで O(n) のパフォーマンスを提供できます。それはハッシュアルゴリズムの悪い設計です。

実際、これらの衝突を回避するために、余分なスペースが割り当てられていると言えます。ハッシュ手法により、多くの衝突が発生しないことが保証され、そのためには明らかに追加のバケットが必要になるためです。

しかし同時に、衝突を完全に回避することはできません。ハッシュ手法が各バケットに 1 つのエントリしかない場合、多くのスペースが必要になるからです。したがって、実際には hashCollision を制限内で使用することをお勧めします。

于 2013-07-07T10:26:14.237 に答える
0

o(1) ハッシュ関数を設計するために事前に鍵の分布を知ることは非常に困難です。キーの配布がわかっている場合でも、キーが同じスロットにマップされる場合があります。したがって、負荷率が特定の割合に移動したら、再ハッシュを行う必要があります。マップ サイズが 16 で、キーが 17 個ある場合、衝突が発生します。したがって、この状況では、マップを再ハッシュして潜在的な衝突を除去する何らかのメカニズムが必要です。

ハッシュマップの検索操作は漸近的に O(1) ですが、o(n) に移動することもできます。

于 2013-07-07T10:26:54.067 に答える