ハッシュテーブル(2)-hash colisionハッシュ競合
11193 ワード
0. Hash Colision
ハッシュ関数がすべての入力に対して常に異なるハッシュ値を付与できる場合が理想的である.
しかし,すべてのデータを理解しなければ,このような完璧なハッシュ関数を記述することは不可能である.
ハッシュ競合(hash colision)は、鍵を収容できる場所がない場合に発生する概念である.
以上のように、B及びCのキー値がハッシュ関数を通過すると、同じハッシュ値4が与えられる.これがハッシュ衝突です.
一方,ハッシュテーブルの最も重要な目的は,ハッシュ競合を最小化するハッシュ関数を作成することである.
Pythonコードでハッシュ競合が発生した場合を実現する.# 길이가 5인 리스트 생성
hashtable = [None] * 5
print(hashtable)
# [None, None, None, None, None]
# 해시함수
def hash_function(key):
return key % len(hashtable)
print(hash_function(10))
print(hash_function(20))
print(hash_function(31))
#
0
0
1
# 해시테이블에 데이터를 삽입
def insert_hash(hashtable, key, value):
hash_key = hash_function(key)
hashtable[hash_key] = value
insert_hash(hashtable, 10, 'A') # 해시함수로 계산되어 0번째 인덱스에 A가 삽입됨
print(hashtable)
# ['A', None, None, None, None]
insert_hash(hashtable, 23, 'B') # 3번째 인덱스에 B가 삽입됨
print(hashtable)
# ['A', None, None, 'B', None]
# 현재 0번째 인덱스에 A, 3번째 인덱스에 B가 저장되어있음
# 아래와 같이 해시함수를 통해 계산된 0번째 인덱스에 'Collision' 값을 삽입할 경우, 충돌이 발생한다.
# 그리고 'A'값은 'Collision'으로 대체(충돌)된다.
insert_hash(hashtable, 20, 'Collision')
print(hashtable)
# ['Collision', None, None, 'B', None]
ハッシュ競合による問題を解決するために最も代表的な2つの方法を理解する.
まず、Chainingメソッドです.
1. Chaining
フィルタは、ハッシュ・テーブルで同じハッシュ値に競合した場合に、次のキー値をその位置にあるパケットに接続する方法です.
すなわち、フィルタリングは、bucketで接続可能なエントリを制限するのではなく、接続リスト資料構造を用いてチェーン形式で接続される.
フィルタ処理
# 길이가 5인 리스트 생성
hashtable = [None] * 5
print(hashtable)
# [None, None, None, None, None]# 해시함수
def hash_function(key):
return key % len(hashtable)
print(hash_function(10))
print(hash_function(20))
print(hash_function(31))
#
0
0
1# 해시테이블에 데이터를 삽입
def insert_hash(hashtable, key, value):
hash_key = hash_function(key)
hashtable[hash_key] = value
insert_hash(hashtable, 10, 'A') # 해시함수로 계산되어 0번째 인덱스에 A가 삽입됨
print(hashtable)
# ['A', None, None, None, None]
insert_hash(hashtable, 23, 'B') # 3번째 인덱스에 B가 삽입됨
print(hashtable)
# ['A', None, None, 'B', None]# 현재 0번째 인덱스에 A, 3번째 인덱스에 B가 저장되어있음
# 아래와 같이 해시함수를 통해 계산된 0번째 인덱스에 'Collision' 값을 삽입할 경우, 충돌이 발생한다.
# 그리고 'A'값은 'Collision'으로 대체(충돌)된다.
insert_hash(hashtable, 20, 'Collision')
print(hashtable)
# ['Collision', None, None, 'B', None] フィルタは、ハッシュ・テーブルで同じハッシュ値に競合した場合に、次のキー値をその位置にあるパケットに接続する方法です.
すなわち、フィルタリングは、bucketで接続可能なエントリを制限するのではなく、接続リスト資料構造を用いてチェーン形式で接続される.
フィルタ処理
接続リストの形式のため、特定のハッシュ値に競合が発生しても、フィルタを使用して値を検索できます.
フィルタ処理はPythonコードで行います.
# 2차원 리스트 생성
chain_hash_table = [[] for _ in range(10)]
print(chain_hash_table)
# [[], [], [], [], [], [], [], [], [], []]
# 해시함수 및 해시 값 확인
def chain_hash_func(key):
return key % len(chain_hash_table)
print(chain_hash_func(10))
print(chain_hash_func(21))
print(chain_hash_func(39))
#
0
1
9# extend 방식으로 체이닝하는 함수
def chain_insert_func(chain_hash_table, key, value):
hash = chain_hash_func(key)
chain_hash_table[hash].extend(value)
chain_insert_func(chain_hash_table, 10, 'A')
chain_insert_func(chain_hash_table, 25, 'B')
print(chain_hash_table)
# [['A'], [], [], [], [], ['B'], [], [], [], []]# 20(key)에 해당하는 해시가 중복된 해시더라도 체이닝을 통해 리스트가 연결되어 값이 추가된다.
chain_insert_func(chain_hash_table, 20, 'C')
print(chain_hash_table)
# [['A', 'C'], [], [], [], [], ['B'], [], [], [], []]
2. Open Addressing
オープン選別は1つのbucketが1つのentryにしか入らない形式です.
この方法はハッシュ競合が発生すると,空の配列スロットが発見されるまで配列の位置を探索する.
すなわち,配列の空白空間を検出(証明)しながらハッシュ衝突を回避する方法である.
チェニンとは異なり,オープンアドレス法には固定的な記憶空間がある.
4. Python Dictionary
Pythonの資料型では,スケジュールからなる資料型がディックシャーナである.
また,Python内部ではオープンアドレス方式を用いてハッシュ競合を解決している.
オープンウェアを使用する場合、空き地がなければ、時間がかかる場合があります.
そのため、Pythonは負荷係数を小さく設定して、性能の低下の問題を解決します.
3. Load Factor
負荷係数は、ハッシュ・テーブルがどれだけ満たされているかを測定する指標です.
load factor=(ハッシュテーブルに入力されたキー数/ハッシュテーブルの合計インデックス数)
Pythonの資料型では,スケジュールからなる資料型がディックシャーナである.
また,Python内部ではオープンアドレス方式を用いてハッシュ競合を解決している.
オープンウェアを使用する場合、空き地がなければ、時間がかかる場合があります.
そのため、Pythonは負荷係数を小さく設定して、性能の低下の問題を解決します.
3. Load Factor
負荷係数は、ハッシュ・テーブルがどれだけ満たされているかを測定する指標です.
load factor=(ハッシュテーブルに入力されたキー数/ハッシュテーブルの合計インデックス数)
すなわち,7番目のキー値を格納すると,容量が2倍になる.
Reference
この問題について(ハッシュテーブル(2)-hash colisionハッシュ競合), 我々は、より多くの情報をここで見つけました https://velog.io/@citizenyves/Hash-table2-hash-colision-해시충돌テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol