簡単で分かりやすいデータ構造のハッシュ表

Hash表はハッシュ・テーブルと呼ばれ、ハッシュ・リストとも呼ばれる.ハッシュ・テーブルは、関数マッピングの思想に従い、Key:Valueの方法でデータを格納する比較的特殊なデータ構造である.ハッシュ・テーブルの最大の特徴は、検索するデータに素早く位置決めすることができ、クエリの時間的複雑さはO(1)に近いことである.
ハッシュ・テーブルの設計原理
もし私たちがデータを持っているなら、あるエンジニアの年収状況

2017 -- 100000
2018 -- 130000
2019 -- 140000
2020 -- 200000

これらのデータが普通のチェーンで保存されている場合、2019年の収入状況を調べたら、チェーンの初期ノードからチェーン全体を巡回して、2019を見つけてから対応するデータを取り出す必要があります.このような検索の時間的複製度はO(n)であり、私たちが順番に保存して二分割検索を使用する場合でも、時間的複雑度はO(logn)である.もし私たちが年、つまりkey値を知ることができれば、直接に対応する収入データを取り出すことができます.時間の複雑さはO(1)です.そして、もしデータをハッシュ・テーブルに格納すれば、このような検索を実現することができます.ハッシュテーブルの原理は複雑ではない.つまり、Keyに基づいて格納位置を計算し、その空間にデータを入れ、照会時もKeyに基づいて格納位置を計算し、直接に対応する値を取り出すことである.
ハッシュ関数
Keyに基づいて、格納位置の計算規則を計算します.ハッシュ関数と呼びますか?それともこの例を使って、一番簡単なハッシュ関数H(x)＝xを取ります.

1.        2020   array[]
2.   H(x) = x       ，        。
   array[2017] = 100000
   array[2018] = 130000
   array[2019] = 140000
   array[2020] = 200000
3.   2019      ，  H(x) = x        ，      array[2019]

上記の例では、簡単なハッシュ・テーブルを実現したが、多くの空間が浪費されていることが明らかになり、2020の配列は4つの空間しか使用できない.以下、このハッシュ・テーブルを改良する.保存が必要なデータを観察することによって、新しいハッシュ関数H(x)＝x−2000を選択する.

1.        20   array[]
2.   H(x) = x - 2000       ，        。
   array[2017 - 2000] = array[17] = 100000
   array[2018 - 2000] = array[18] = 130000
   array[2019 - 2000] = array[19] = 140000
   array[2020 - 2000] = array[20] = 200000
3.   2019      ，  H(x) = x - 2000        ，      array[19]

この例では,空間の浪費は最適化前より大幅に減少することが見られた.ここから、適切なテーブルサイズおよびハッシュ関数が、データの特徴に従って選択されることが、ハッシュ・テーブルというデータ構造の実現の鍵であることが分かる.
いくつかの共通のハッシュ関数を紹介します.

     
                  。
H(x) = x % p
        s, p      s     

     
       
H(x) = a * x + b
            a=1,b=0   a=1,b=-2000

   
      18560 55632，  key     ，       
18 + 56 + 0 = 74 
55 + 63 + 2 = 120 -->> 20(     )
          ，         ，             

     
       ，                     。
333 * 333 = 110889 ->> 08
444 * 444 = 197136 ->> 71
        key 

     
               key   
1125699 1123399 1158299
        ，          ，             key 
256 233 582
        200
56 33 382

衝突
ハッシュ・テーブルがさらに解決する問題の一つは、衝突であり、ハッシュ関数を選択した後、同じkeyを計算する可能性がある.例えばH(x)＝x%5というようなアルゴリズムは、6と11で1を計算し、このとき衝突が生じる.衝突を解決しないと、ハッシュ・テーブルは構築できない.衝突を解決する方法は以下のいくつかあります.

     
              ，       key          ，        ，      。

     
              
H(x) = x % 5
    : {5, 6, 8, 12, 11}
  Key: { 0, 1, 3, 2, 1}
     [0, 1, 2, 3, 4, 5, 6, 7 .....]
        [5, 6, 12, 8, 11]    11   ，     1         ，                  ，        ，      4     11

               ，              key   ，        。
                   

締め括りをつける
ハッシュテーブルは、迅速なクエリの必要性を解決しましたが、もしデザインが間違っていたら、相当な空間的浪費を引き起こし、実際の状況に応じて設計する必要があります.