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で接続可能なエントリを制限するのではなく、接続リスト資料構造を用いてチェーン形式で接続される.
フィルタ処理

キーのハッシュ値を計算します.

ハッシュ値に対応するリストインデックスを求める.

同じハッシュ値(

など)を持つキーがある場合は、(競合)リストに接続します.

接続リストの形式のため、特定のハッシュ値に競合が発生しても、フィルタを使用して値を検索できます.
フィルタ処理は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=(ハッシュテーブルに入力されたキー数/ハッシュテーブルの合計インデックス数)

のロードパラメータ値に基づいて、ハッシュ関数を書き換えるかどうか、およびハッシュテーブルサイズを調整するかどうかを決定する.

でパラメータ値をロードすると、ハッシュ・テーブルのパフォーマンスの程度がわかります.

オープン選別方式を用いると、1個程度の負荷係数が発生する.

ふるい分け方式を用いると、負荷係数<=1(オープン選別よりも優れた性能)が示される.

のロードパラメータを下げると、ハッシュ・テーブルのパフォーマンスが向上します.

負荷係数の例

負荷仕様が0.75に達した場合、既存容量を2倍に設定します.

テーブルの初期容量を10とすると、10∧0.75=7.510*0.75=7.0∧0.75=7.5
すなわち,7番目のキー値を格納すると,容量が2倍になる.

の結果、既存の容量(10)が容量(20)を増加させた.

容量が増加すると、既存のデータがハッシュ関数に再配置され、ハッシュテーブルが再ソートされる.

Created on Dec 1, 2021

作文