問題を解決するためのハッシュマップを実装するアルゴリズムを記述しました。誰かがエントリーを見つけるための平均ホップ数を計算するための一般的な公式を私に与えることができるかどうか疑問に思っていますか？私の報告書のちょうど一部です:) 私自身のハッシュコード関数を作成しました。私はそれの品質を測定しようとしています。ハッシュマップの平均ホップ数
衝突の扱いについて：そのインデックスに2つの以上の要素のハッシュコードは、ハッシュテーブル内の同じインデックスにマップする場合、私が構築され、「リンクリスト」私は意味、「ホップ」と
。したがって、ハッシュ表の索引 'i'にマップされる4つの要素がある場合、索引 'i'には4つの要素のリンクされたリストが含まれます。この意味での「ホップ」は、そのリンクされたリストを通って「歩いている」か「ホッピングしている」。
本質的に、マップの各インデックスに別のデータ構造があります。
完全に明示的にするために、リストを使用して衝突を処理するハッシュテーブルのリストに沿った「ホップ」の数は、テーブル内のハッシュ衝突の数と同じです。これは、hash(item) % size of tableが提供されるデータと同じ値。テーブルのスペアスロットを使用するハッシュテーブルの場合、テーブルから削除された衝突アイテムも寄与します。
たとえば、テーブルサイズが2の累乗で増加しても、ハッシュ関数の上位ビットに違いがあった場合、外部ハッシュの衝突がなくてもテーブルに多くの衝突が発生します。出力する。 1つのテクニック（IIRCはSunの実装で使用されるもの）は、素数をテーブルサイズとして使用する方法と、ビットミキシング関数を使用して、最下位のnビットをインデックスとして使用する前に、提供されたハッシュ関数の出力を処理する方法です。
したがって、衝突の回数は、データ内で見つかった提供されたハッシュ関数の値の広がり（すべてが衝突した場合、テーブル実装は何もできません）、与えられたテーブルサイズの選択ロード・ファクタ、および提供されたハッシュの出力を表索引に変換する方法について説明します。
パフォーマンスは、ハッシュ関数の品質とデータの分布によって異なります。大きな代表的なデータセットを選択し、パフォーマンスを測定します。
これは最大値にも依存します。ハッシュテーブルの負荷係数 –
はい。私は要素のルックアップを実行するときに平均ホップ数を計算する方法を探しています。 –
がJava HashMapのドキュメントを参照してください：
この実装は、ハッシュ関数が複数のバケットで適切に要素を分散すると仮定すると、基本的な操作（getおよびput）に一定時間のパフォーマンスを提供します。
つまり、格納しているアイテムに実装されているハッシュ関数の品質によって異なります。
私は自分のhashCodeを計算しており、その品質を測定しようとしています。 –
私自身のhashCodeを計算しており、その品質を測定しようとしています。
ハッシュテーブルを忘れて、intタイプの範囲でハッシュ値の分布を分析するだけです。理想的には、ハッシュ値を一様に分散させたいと考えています。重要なピークは潜在的な問題を表します。
さらに、実際のアプリケーションで使用されるキーの分布を考慮する必要があります。例えば、ハッシュ関数は、多くの分散を与えないように「類似の」キーをハッシュすることができる。アプリケーションが多くの類似の鍵を使用すると、多くの衝突が発生します。
あなたは「ホップ」の数を測定/ /推定値を計算しようとすると、初期HashMapサイズ、キー挿入のオーダーなので、上のリサイズとの効果のようなものの効果に遭遇します。
サンプル入力セットSを取り、Sのすべての要素のハッシュ値を計算し、計算値をセットHに挿入します。/| H |あなたが期待しなければならない平均的な衝突です。これはあなた自身のハッシュ関数、その品質に依存します。
ハッシュマップを実装しましたか、使用しましたか？ –
Javaのハッシュマップクラスの「カスタム」バージョンを実装しました。 –
興味深いことに、あなたは何を改造しましたか？ –