HashMap実装：--- hashcode

Question

template<class KEY, class VALUE> 
unsigned int HashMap<KEY, VALUE>::hashCode(KEY key) 
{ 
    unsigned int k = key & 0xffffffff; //error: no match for ‘operator&’ in ‘key & 4294967295u’ 
    k += ~(k<<9); 
    k ^= (k>>14); 
    k += (k<<4); 
    k ^= (k>>10); 
    return k; 
}; 

ご覧のとおり、オブジェクトのビットを操作してhashCodeを実装しようとしています。明らかに、ビット演算子はユーザ定義のオブジェクトに簡単には適用できません。

私は、任意の種類のオブジェクトのいくつかのビットを取って、そのメモリ位置を与え、私が望むようにビットを操作したいと思います。次に、ビットをintとして再解釈し、ビット単位の演算子をintに適用します。

これはいい考えですか？そして、どのようにして、与えられたメモリ位置のANY TYPEのオブジェクトからビットを取ることができますか？

ありがとうございます！

Answer 1

を実装するのは簡単です型の平等の定義。 2つの文字列は等しいかもしれません（両方とも"hello world"が含まれていますが、異なるポインタを持っているため異なるポインタを持っているかもしれません）ハッシュキーの実装では、2つの等しいオブジェクトに対して異なるハッシュキーが返されます。

つまり、ハッシュテーブルを壊すと、ユーザーはテーブルに入れたオブジェクトを見つけることができなくなります。

Answer 2

それは良い考えではありません。

オブジェクトのメンバーの詳細を知らなければ、実際にどのビットがハッシュに有益であるかわかりません。たとえば、アラインメントの問題により、実際のデータメンバー間にメモリのギャップが存在する可能性があります。ギャップは初期化されないため、ガベージデータがいっぱいです。または、データメンバがchar配列文字列の場合、ヌルターミネータを過ぎたすべてのバイトはガベージであり、ハッシュに寄与すべきではありません。

C++で簡単なリフレクションを実装する方法は、ここで本当に必要なもの（つまり、すべての構造体のメンバーとタイプを見つけることができる）を使用するマクロを使用していますが、上から外れたオープンソースのものはわかりません私の頭の。私は自分のコードベースに仕事をしています（テンプレートにはあなたが望むもの、つまり任意の構造体のハッシュ関数を作成していますが、共有できません）。

Answer 3

私は、そのメモリが与えられた場合、どのタイプのオブジェクトでもビットを取って、ビットを操作したいと思っています。

ここで言いたいのは、データ構造の基礎となるビット表現を一連のビットとして操作したいということです。

このアプローチは、プリミティブ型でのみ機能します。 int、charsなど

例では、KEYは何でも構いません。基礎ビットは構造体のサイズと同じくらいですので、and操作は本当に役立ちません。

さらに、KEYは、派生クラスであり、基礎となる構造の一部である仮想ポインタのアドレスなどに当たることがあります。

いずれにしても、コードは（たとえあなたがそのようにして、SOの専門家があなたを導くことができたとしても）私の意見では複雑すぎるでしょう。

最善のアプローチは、hash object.Thisの各メンバーになるには、アプローチが、少なくともJavaで続くと、それは尊重していないので、いいえ、それは、ひどいアイデアだ