ハッシュ(データ構造とアルゴリズムPython版)
3034 ワード
中国大学MOOC(慕課)で北京大学陳斌先生のデータ構造とアルゴリズム(python版)を学びました.以下は学習ノートです.
ハッシュ・リストには、データ・アイテムを保存するための複数のスロット(slot)があり、各スロットには一意の名前が付けられています.ハッシュ関数を使用して、特定のスロットにデータ・アイテムを配置します.データ・アイテムを検索するには、対応するスロットに存在するかどうかを検索するだけです.例えば、11個のスロットを含む空のリストであり、スロット名はそれぞれ0~10、データ項54,26,33,17,77,31に対応し、ハッシュ関数h(item)=item%11により対応するスロットに埋め込まれる.このグループのデータ項目の33,77対11の余剰はいずれも0であり,ここではハッシュ競合の問題がある.良いハッシュ関数は、衝突が最も少なく、計算の難易度が低く、データ項目を十分に分散する必要があります.任意の所与のデータ群の各項目を異なるスロットにマッピングできるハッシュ関数を完全ハッシュ関数と呼ぶ.完全なハッシュ関数を実現する方法の1つは,ハッシュリスト容量を拡大し,出現する可能性のあるすべての項目が異なるスロットを占有できるほど大きくすることであり,明らかにこの方法は空間を浪費しすぎて適用されない.
ハッシュ関数の設計
ハッシュ関数設計の核心は、ストレージ・プロシージャと検索プロシージャの計算負担にならないことです.
1.折りたたみ法
データ項目をビット別にいくつかのセグメントに分け、数のセグメントを加算し、ハッシュ・リストのサイズを余す.例えば、電話番号62767255に対して、2人の2人は62 767255の4つのセグメントに分けられ、4つのセグメントを加算して分散リストのサイズ(11)を求めます.(62+76+72+55)%11=1であるため、この電話番号62767255は1番スロットに対応する.
2.平方取中法
データ項目を平方演算した後、中間2桁の数をとり、ハッシュ・リストのサイズを余す.例:44をハッシュする:44² = 1936,中間2桁は93,h=93%11=5であり,5番スロットに対応している.
3.非数項については、ASCII値に変換
文字列の場合は、各文字をord()でASCII値を取得し、ハッシュします.この方法では、変位語に対して同じハッシュ値が返されます.この競合を回避するために、各文字のASCII値に文字列内の位置を乗算します.
競合解決
1.オープン・アドレス:競合するデータの空きスロットを探して保存
a.リニアプローブ:元のスロットにデータ項目があるので、後で順番に探して、空きスロットを見つけたら入れます.この方法では、競合を解決した後、データ・アイテムを検索するときに、ハッシュ値の場所にデータ・アイテムが見つからない場合は、検索が見つかるまで順番に検索したり、空きスロットが見つかったりします(検索に失敗しました).欠点:この方法の弊害は、同じスロットで競合するデータ項目が多い場合、この方法を使用すると、データ項目がスロット付近に集まり、後続のデータ項目の挿入に影響を与えることにある.改良:各プローブをジャンプモードに変更し、いくつかの溝を隔てて1回プローブします.
b.再ハッシュrehashing衝突データ項目再ハッシュnewhashvalue=rehash(oldhashvalue)
2.データネックレスchaining
本来1つのデータ項目しか収容できないスロットを,データ項目集合を収容するように拡張する.
ハッシュ・リストには、データ・アイテムを保存するための複数のスロット(slot)があり、各スロットには一意の名前が付けられています.ハッシュ関数を使用して、特定のスロットにデータ・アイテムを配置します.データ・アイテムを検索するには、対応するスロットに存在するかどうかを検索するだけです.例えば、11個のスロットを含む空のリストであり、スロット名はそれぞれ0~10、データ項54,26,33,17,77,31に対応し、ハッシュ関数h(item)=item%11により対応するスロットに埋め込まれる.このグループのデータ項目の33,77対11の余剰はいずれも0であり,ここではハッシュ競合の問題がある.良いハッシュ関数は、衝突が最も少なく、計算の難易度が低く、データ項目を十分に分散する必要があります.任意の所与のデータ群の各項目を異なるスロットにマッピングできるハッシュ関数を完全ハッシュ関数と呼ぶ.完全なハッシュ関数を実現する方法の1つは,ハッシュリスト容量を拡大し,出現する可能性のあるすべての項目が異なるスロットを占有できるほど大きくすることであり,明らかにこの方法は空間を浪費しすぎて適用されない.
ハッシュ関数の設計
ハッシュ関数設計の核心は、ストレージ・プロシージャと検索プロシージャの計算負担にならないことです.
1.折りたたみ法
データ項目をビット別にいくつかのセグメントに分け、数のセグメントを加算し、ハッシュ・リストのサイズを余す.例えば、電話番号62767255に対して、2人の2人は62 767255の4つのセグメントに分けられ、4つのセグメントを加算して分散リストのサイズ(11)を求めます.(62+76+72+55)%11=1であるため、この電話番号62767255は1番スロットに対応する.
2.平方取中法
データ項目を平方演算した後、中間2桁の数をとり、ハッシュ・リストのサイズを余す.例:44をハッシュする:44² = 1936,中間2桁は93,h=93%11=5であり,5番スロットに対応している.
3.非数項については、ASCII値に変換
文字列の場合は、各文字をord()でASCII値を取得し、ハッシュします.この方法では、変位語に対して同じハッシュ値が返されます.この競合を回避するために、各文字のASCII値に文字列内の位置を乗算します.
def hash(astring, tablesize):
sum = 0
for pos in range(len(astring)):
sum = sum + ord(asrting[pos])*(pos+1)
return sum % tablesize
競合解決
1.オープン・アドレス:競合するデータの空きスロットを探して保存
a.リニアプローブ:元のスロットにデータ項目があるので、後で順番に探して、空きスロットを見つけたら入れます.この方法では、競合を解決した後、データ・アイテムを検索するときに、ハッシュ値の場所にデータ・アイテムが見つからない場合は、検索が見つかるまで順番に検索したり、空きスロットが見つかったりします(検索に失敗しました).欠点:この方法の弊害は、同じスロットで競合するデータ項目が多い場合、この方法を使用すると、データ項目がスロット付近に集まり、後続のデータ項目の挿入に影響を与えることにある.改良:各プローブをジャンプモードに変更し、いくつかの溝を隔てて1回プローブします.
b.再ハッシュrehashing衝突データ項目再ハッシュnewhashvalue=rehash(oldhashvalue)
2.データネックレスchaining
本来1つのデータ項目しか収容できないスロットを,データ項目集合を収容するように拡張する.