Myhashmapがhashmapを継承し、ハッシュ関数をオーバーライドします

Question

ハッシュマップを拡張するクラスmyhashmapを持っていて、次に関数ハッシュをオーバーライドして定数を返すと、マップの挿入と参照がどのように影響を受けますか？

Answer 1

ハッシュ関数で定数値を返すことには意味がありません。これを行うと、hashMapは単純なリンクリストに変わります。

tab[i = (n - 1) & hash]ここでnはマップのサイズです。 ハッシュ値が定数より大きい場合、結果は常に一定になり、get/put関数はO（N）時間かかることになります。

Answer 2

全くありません。 Myhashmapで上書きできるのは、Myhashmapの場合はhashCode()となります。これにより、Myhashmapのパフォーマンスには影響しません。一方、HashSet<Myhashmap>とMap<Myhashmap, ?>はかなり恐ろしい動作をします。

これを理解するには、HashSet（またはHashMapですが、原則は同じです）の基本的な機能を理解する必要があります。そのハッシュに応じてバケットにObject Sを配布することで、両方の仕事：今、この実装はoversimplistic維持され、実際のコードでは使用すべきではないながら

List<T>[] buckets = new List<>[bucketnum]; 

void add(T t){ 
    List<T> l = buckets[t.hashCode() % buckets.length]; 
    if(!l.contains(t)) 
     l.add(t); 
} 

は、それはかなり明確に一つのことを示していますHashSetがあるため、高速でそれはバケツを使用します。しかし、hashCode()メソッドが定数を返すようにすると、すべての値が単一のバケットに挿入されるHashSetになります。すなわち、HashSet/-MapがListと比較してオーバーヘッドを導入するため、を離れて投げて、Listを使用してください。ランタイムはまったく変わらないでしょうし、悪い場合もあります。例えば。 HashSet/-Mapは、特定の負荷係数に達した場合にバケット番号を増やします。追加のリソースが必要です。

EDIT：
これは深さにもう少し行くと、それはHashSet/-Map秒の異なる実装を示して、それは興味深いですが、それは、データ構造をハッシュする上記導入のちょうど拡張だとして、それは、理解する必要はありませんし、脚注として考慮する必要があります。実際には別のオプションがあります：Collision resolution。この場合、特定のハッシュバケットを共有するオブジェクトを格納するためのListは存在しません。代わりに、アルゴリズムは特定のパターンで使用可能なバケットを検索します。これは..

例えば：

T[] buckets; 

boolean add(T t){ 
    int index = t.hashCode() % bucketnum; 

    for(int i = 0; i < bucketnum; i++){ 
     if(buckets[(i + index) % bucketnum] == null){ 
      buckets[(i + index) % bucketnum] = t; 
      return true; 
     } 
    } 

    return false; 
} 

このコードは衝突ハッシュに対応する線形衝突戦略を使用する等、線形二次することができた（二つのオブジェクトa、b、その結果a.hashCode() % bucketnum == b.hashCode() % bucketnum）。この実装では少し異なる動作が示され、異なる負荷係数が必要ですが、適切なハッシュ関数が必要です。そうしないと、パフォーマンスはバケットリスト手法よりもさらに悪くなります。