航海99第2週-ハッシュ表理論整理

Today I learned
2022/01/19
回顧録

1/18

航行99、アルゴリズム1週目
教材:Pythonアルゴリズムインタビュー
第10章ハッシュ表

1.理論

ハッシュ・テーブルは、キーと値に基づいてデータを格納します.PythonにはDickShownerがあるので、わざわざする必要はありませんが、Pythonでコードを書くのが簡単で、把握しやすいという利点があります.
上の画像では、文字列(John smith...)データはハッシュ関数によって数値に変わります.変更された値(ハッシュ)を配列(bucket)のキーとして価値を格納します.従って、データを瑞称する過程で、配列を順次閲覧する必要がなく、ハッシュ関数で生成されたハッシュ値によってデータを迅速に検索することができる.ディックシャナに似たkey−value構造.
鍵:データ*ex John Smith,Lisa Smithを入力
値(value):保存するデータ*ex)521-8976、521-1234
ハッシュ関数:キーをハッシュに変更する関数
*上記の画像では、文字列データはhash関数を介して数値列データに変更されます.
ex) John Smaith -> 02
ハッシュ(Hash):入力データを固定長の数字列に変換した結果*上の画像の00~15はハッシュである.
すなわち、ハッシュ関数により入力文字列の入力データを数値列に変更し、その数値をキー値として配列に格納する.(Pythonハッシュ関数では環境ごとに出力が異なるためhashlibのsha 1とsha 256も書き込まれる)

# Hash Table
class HashTable:
    def __init__(self, table_size):
        self.size = table_size
        self.hash_table = [0 for a in range(self.size)]
        
    def getKey(self, data):
        self.key = ord(data[0])
        return self.key
    
    def hashFunction(self, key):
        return key % self.size

    def getAddress(self, key):
        myKey = self.getKey(key)
        hash_address = self.hashFunction(myKey)
        return hash_address
    
    def save(self, key, value):
        hash_address = self.getAddress(key)
        self.hash_table[hash_address] = value
        
    def read(self, key):
        hash_address = self.getAddress(key)
        return self.hash_table[hash_address]
    
    def delete(self, key):
        hash_address = self.getAddress(key)
        
        if self.hash_table[hash_address] != 0:
            self.hash_table[hash_address] = 0
            return True
        else:
            return False


#Test Code
h_table = HashTable(8)
h_table.save('a', '1111')
h_table.save('b', '3333')
h_table.save('c', '5555')
h_table.save('d', '8888')
print(h_table.hash_table)
print(h_table.read('d'))

h_table.delete('d')

print(h_table.hash_table)
 

質問:ハッシュ競合
スケジュールに致命的な問題がある.入力データをハッシュ値に変換するとき、2つのデータは異なる文字列であるにもかかわらず、同じ数値に変換されることがあります.この問題をハッシュ衝突と呼ぶ.
ハッシュ競合を解決する代表的な方法は、オープンハッシュとクローズハッシュである.

オープンハッシュ

https://jinyes-tistory.tistory.com/11

閉ループハッシュ

https://jinyes-tistory.tistory.com/12