【Pythonデータ構造とアルゴリズム】ハッシュテーブル

2018-7-23家に帰って、2週間滞在して帰ります～bjは大きい毛が残って、金はかわいそうです～
ハッシュ・テーブルを話す前に、さまざまなデータ構造を整理して、彼らの特徴を見る必要があります.
Array配列の線形構造--メモリは連続pythonが持つarrayモジュールであり、同じタイプの基本的な数値と文字しか格納できません.
Listリスト--[1,2,3,a]線形構造は各要素にindexインデックスを割り当て、データ項目は異なるタイプであってもよい.リストで固定長を実現し、すべてのpythonデータ型の配列Arrayをサポートできます.
LinkedListシングルチェーンテーブルチェーン構造--メモリは不連続で、一つ一つ直列になっているので、次のnodeノードにポインタを向ける必要があります.ノードnodeにはポインタnextが含まれ、次のnodeの位置を保存し、valueプロパティに値を保存する必要があります.append操作はO(1)であるがfind,removeはO(n)であり,removeは先に検索する必要があるが,単一チェーンテーブルの検索は最初から最後まで必要であり,検索してから終了するので時間的複雑度が高い.
CircularDoubleLinkedListループデュアルチェーンテーブルは、シングルチェーンテーブルよりもprevポインタが1つ多い.ノードnodeを削除する必要がある場合は,その前後のノードを互いに指さすだけでよいが,この時間複雑度はO(1)である.Emmmmmが値を削除する場合、または値がどのノードにあるかを巡回しなければならないのは欠点です.
Double Ended Queue両端キューは先進的な先出し構造である.FIFOはキューを最初から削除し、末尾に要素を追加する必要がある.上記のいくつかのデータ構造により実現できる.LinkedListのpopleft法もappend法もO(1)である.
Stackスタックは先進的な後出構造で、LIFOは柱に物を刺すようにいっぱいになっていて、一番上の1つから1つしか出せません.1つのデータ構造で末尾から要素を容易に増減できるだけでよい――CDLL
ハッシュ表
前述したサイクル両端チェーンテーブルremove動作時間複雑度はO(1)であるが,find動作の時間複雑度はO(n)である.arrayはindexでfindできますが、中間要素を削除するには他の要素を移動する必要があります.
ハッシュテーブルはこの問題を解決するために現れた.配列内の各要素に を与え、迅速に見つけます.
それは1つのハッシュ関数を通じて1つの要素が配列のどの位置に置くべきかを計算します.もちろん、1つの特定の要素に対して、ハッシュ関数は計算するたびに同じようにしなければなりません.そして、範囲は与えられた配列の長さを超えてはいけません.
1段の長さ、各点を番号付きの溝として考えることができます.各要素をハッシュ関数でマッピングして割り当てます.しかし、異なる要素マッピングの結果が同じである場合、すなわち、スロットのシーケンス番号が同じである場合、すなわちハッシュ競合が発生する.
解決方法1.リンク法-chainningは衝突した各スロットをチェーン構造にするが、ハッシュ関数が悪い場合、1つのスロットのチェーンが長すぎて検索が遅くなる.オープンアドレス法-open addressing collisinが発生した場合、方法によって次の使用可能なスロットを探します.ここでは、次のスロットを探す方法によって、1リニアプローブ(linear probing):1つのスロットが占有されると、次の利用可能なスロットh(k,i)=(h’(k)+i)%m,i=0,1,...,m−1②二次プローブ(quadratic probing):1つのスロットが占有されると、オフセット量h(k,i)=(h’(k)+c 1+c 2 i 2)%m,i=0,...,m−1③二重ハッシュ:hash結果h(k,i)=(h 1(k)+ih 2(k)%mを再計算
ハッシュ関数
選択したハッシュ関数は、各キーを可能な限り各スロットに割り当て、残りのキーが競合しないようにしなければならない.
マウントファクタ
再ハッシュ
簡易ハッシュテーブルADT実装
3つの最も一般的な操作:

add(key, value)
get(key, default)
remove(key)

class Slot(object):
    """     hash       
      ，        ，       
    1.     HashMap.UNUSED。           ，        UNUSED          
    2.      remove  ，    HashMap.EMPTY，              key
    3.      Slot   
    """
    def __init__(self, key, value):
        self.key, self.value = key, value

class HashTable(object):
    pass

実装ではslotにはunusedが使用されていない、使用されているが削除されているempty、使用されている3つの状態がある.なぜなら、削除や追加の操作にかかわるからです.