ハッシュ関数
例えば、ある会の会員名簿には100人ほどの会員の名前が並んでいるが、それはこの世に存在する人名のごく一部である。その場合、一様性はほぼ全ての典型的な部分集合に対して成り立てばよいのであって、全ての可能なエントリ全体の集合に対して成り立たせる必要はない。
言い換えれば、典型的な m 個のレコードの集合を n 個のバケットにマッピングする場合、1つのバケットに対応するレコード数が m/n より大きくなる可能性をなるべく小さくすればよい。特に m が n より小さい場合、一部のバケットだけが1つまたはせいぜい2つのレコードを格納するようにすべきである。理想的な完全ハッシュ関数では、各バケットには最大でも1つのレコードしか格納されない。しかし、n が m よりずっと大きくても、衝突を完全に無くすことはできない(誕生日のパラドックスを参照)。
ハッシュ関数を評価する場合、ハッシュ値の分布の一様性はカイ二乗検定で評価できる。
良いハッシュ関数は、考えられる入力範囲が出力範囲全体になるべく一様に分布するようにマッピングを行う。つまり、出力範囲のそれぞれのハッシュ値はほぼ同じ確率で生成されるべきである。このような条件があるのは、異なる入力が同じハッシュ値にマッピングされてしまう「衝突」が発生すると、ハッシュに基づく各種技法のコストは衝突発生回数と共に増大するためである。あるハッシュ値が他のハッシュ値より生成されやすいなら、参照操作で衝突しているエントリ間でどれが探しているエントリかを調べる作業が基本的に大きな部分を占めることになる。
注意しなければならないのは、「一様分布」が必要なのであって「無作為」である必要はないという点である。よい無作為化関数はハッシュ関数にも適していることが多いが、ハッシュ関数が無作為化関数である必要はない。
ハッシュテーブルには可能な入力のうちのごく一部が格納されているということが多い。
入力の出現確率が一様でない場合や、独立性がない場合は、上のような単純な方式ではうまくいかない。例えば、あるスーパーマーケットの利用者は地理的に近い場所に集中しているため、電話番号の先頭数桁は同じになってしまう。その場合、(z × n) ÷ N の式では元の数値の上の桁が残るため、衝突が多発する。一方、z mod n の式では、末尾側の桁が残るため、この場合のハッシュ値の分布はこちらの方がよい。
多くの場合ヒューリスティクスを利用して、汎用のハッシュ関数よりも特定用途で衝突を削減できるハッシュ関数を設計できる。例えば、入力が FILE0000.CHK、FILE0001.CHK、FILE0002.CHK などのファイル名で、多くの場合このような一連の番号が名前に含まれているとする。すると、ファイル名から番号部分 k を抜き出し、k mod n をハッシュ値とすれば、ほぼ最適な結果が得られる。言うまでもないが、特定の入力に最適化したハッシュ関数は、それ以外の分布を示す入力に対しては非常に悪い結果を生じる。