ハッシュ表

Pythonのdictionaryデータ構造(key,value)などのデータ構造
データがどこに格納されるか(index)は、keyとkeyを入力値として演算するhash関数によって決定される.
たとえば、10グリッドのテーブルがある場合、キー%10(10以外)に基づいてデータの保存方法を決定する方法がある場合があります.このindex=key%10がhash関数です.
また、インデックスが競合(入力データがex:key=4の場合、入力データがkey=14の場合)を指定すると、競合(Collision)が発生し、これを防止するCollision Resolutionメソッドがあります.
つまりハッシュテーブル

Table(list)

Hash function

Collision Resolution Method

構成.

Hash Function

HashFuncはkeyをindexにマッピングする過程で1:1の試合(完璧なhashfunc)を衝突なく行うのが理想的だが、現実的には非常に困難である.
次にUniversal Hashfuncです.

Pr(f(x)==f(y)) = 1/m (m = table의 크기)

つまり,衝突が発生する確率がテーブルの大きさに反比例するHashFuncである.
これも設計が困難であり,pr(f(x)=f(y))=c/mを用いて,一定定数cを有するc−universal hashfuncを用いた.

HashFuncのタイプ

インデックスが数字の場合:除算、乗算、mid-square、抽出など
インデックスがstringの場合:additive(=sum(key[i])、rotation...

良好なHashFunc条件

less collision

fast computation

一般的に、この2つの性質には取引関係があります.

Collision Resolution Method

CRMのタイプ

オープン・アドレス(競合が発生した場合は周辺空のインデックスに格納)
1)Linear probeging:インデックスを移動しながら空のインデックスを検索する方法
2)象限検出:k=f(key)の場合、インデックスをどのようにスキップするか:k+1^2、k+2^2、k+3^2
3)Double hashing:2つのHashFuncを使用して2つのインデックスを作成する方法

Chaining:接続リストをインデックス内で作成および管理する方法

Cluster

テーブル内のキーが特定の部分に傾く現象
例えば、ハッシュテーブルが線形プローブに従う場合、key=4,14,24,34...入力したデータを続行すると、競合が発生し続け、インデックスに対応するスロット(4、5、6、7...)が発生します.鍵を合わせた.
クラスタが大きいほど衝突発生率が高くなり、すなわち計算時間が長くなるため、クラスタ発生のHashFuncを低減することが必要となる.

パフォーマンス評価

So why use hash table?

ハッシュ・テーブルは、非常に高速な「平均」挿入/削除/参照演算を提供するためです.
ハッシュ・テーブルのパフォーマンスは、[Load Factor=n/m](n=テーブルに格納されているアイテムの数、m=テーブルサイズ)および[競合比率=競合回数/n]によって、時間およびパフォーマンスの評価を実行できます.
通常、Load Factorが1に近いほど、(Table Full)クラスタが大きいか多いほど、スロットごとの回数が多くなるため、実行時間が長くなります.
ただし、m>=2 n、すなわち、テーブルが少なくとも50%の空きスロットを保持している場合、計算クラスタの平均サイズはO(1)(一定時間)であってもよい.
この場合、挿入／削除／閲覧の平均時間はO(1)である.
ビッグデータや重要なデータを処理したり、高速演算が必要な企業はhashテーブルを使用します.

Pythonコード

class HashTable:
    def __init__(self,size):
        self.size = size
        self.hashTable = [0 for i in range(self.size)]
    
    def hashFunction(self,key): # 키값을 해시테이블의 크기로 나눈 division h.f. 사용
        return key % self.size 
    
    # Open Addressing - Linear probing 에서의 삽입/탐색/삭제 연산

    # 가장 기본적으로, 키값을 인덱스로 변환하여 슬롯을 찾고, 슬롯에 key값이 없으면 key가 삽입될 슬롯 return 혹은
    # Linear probing으로 슬롯 한칸씩 내려가면서 key값이 있으면 그 슬롯을 return  
    def findSlot(self,key): # 키값을 h.f.에 입력해 해시테이블에 저장될 인덱스를 출력하는 함수
        i = self.hashFunction(key)
        start = i
        while (self.hashTable[i] != 0) and (self.hashTable[i][0] != key):
            i = (i+1) % self.size # 한 슬롯씩 내려가다 끝 슬롯 다음이 첫 슬롯이 될 수 있게 나머지 연산을 돌림 
            if i == start : # 테이블을 돌아 원래 슬롯에 돌아왔다는 것은, 테이블이 꽉 찼다는 뜻
                i = None 
                return i
        return i
    
    def set(self,key,value=None):
        i = self.findSlot(key)
        if i == None:
            print("Hash Table is full! Expand table size!")
            return None
        if self.hashTable[i] != 0: # key가 들어간 슬롯이 이미 있어 value값만 업데이트될 때,
            self.hashTable[i] = (key,value)
        else:                      # 아예 빈 슬롯에 key와 value를 추가하는 케이스
            self.hashTable[i] = (key,value)
            return key

    def search(self,key):
        i = self.findSlot(key)
        if i == None:
            print("Hash Table is full! Could not find key!")
            return None
        if self.hashTable[i] == 0:
            print("Could not find key!")
            return None
        else:
            return self.hashTable[i][1] # key값이 들어있는 슬롯의 데이터 읽기

    # collision 발생해서 슬롯이 밀렸던 경우를 고려해서 나머지 슬롯에 있는 값들을 이동시켜야 한다
    def remove(self,key):
        i = self.findSlot(key)
        if self.hashTable[i] == 0 : return None
        j = i
        while True: 
            self.hashTable[i] = 0 # 슬롯 내 데이터를 삭제
            while True: # 밀려서 set된 슬롯들을 찾고, 이동시키는 과정
                j = (j+1) % self.size
                if self.hashTable[j] == 0: # 삭제한 i 슬롯 다음 슬롯이 비었다면, 적어도 i 슬롯의 데이터로 인해 collision이 발생하지 않았다는 뜻. 옮길 게 없다
                    return print('Remove Complete!')
                k = self.hashFunction(self.hashTable[j][0]) # 테이블이 비었다면 j에 있는 데이터가 원래 들어갈 슬롯은 k
                if (k<=i<=j) or (j<k<i) or (i<j<k) : # k 슬롯에 갔어야할 데이터가 밀려 i를 넘어 j 슬롯에 들어간 모든 경우
                    self.hashTable[i] = self.hashTable[j] # 빈 슬롯이 된 i 슬롯에 j 슬롯 데이터를 이동
                    break
            i = j # i를 j로 바꿔 j 슬롯을 비우고 다음 슬롯을 확인하는 while 반복



hT = HashTable(10)   # 10칸짜리 빈 테이블 생성(0만 들어가있으면 빈 슬롯으로 간주)
hT.set(3,'aaaa')     # hashFunction(3) = 3 -> HashTable[3]에 (3,'aaaa') 저장
hT.set(5,'bbbb')
hT.set(13,'cccc')    # HashTable[3]에 입력값이 있으므로 findSlot함수에 의해 그 다음 비어있는 칸 [4]에 저장됨
print(hT.hashTable)  # [0, 0, 0, (3, 'aaaa'), (13, 'cccc'), (5, 'bbbb'), 0, 0, 0, 0]
print(hT.search(5))  # bbbb
hT.remove(3)	     # Remove Complete!
print(hT.hashTable)  # [0, 0, 0, (13, 'cccc'), 0, (5, 'bbbb'), 0, 0, 0, 0]
		     # (3,'aaaa') 가 삭제된 [3] 슬롯에 (13,'cccc') 데이터를 옮김