0. Hash Table

ハッシュテーブルは、キーと値のペアを構成する抽象データ型であり、キーを迅速に格納および取得できるテーブル型データ構造である.
その結果、キーを使用して値に直接アクセスできる構造になります.

0.0. Hash

ハッシュはハッシュ関数によって得られる値です.
ハッシュ関数
:各ハッシュ値に複数のキーを一致させるためのロールの関数

0.1. Hashing

ハッシュとは、キーと値をマッピングするプロセスです.
ハッシュの目的は「検索」です.簡単に言えば、すべてのコンテンツを分散し、キーに一致する値を検索するプロセスです.
したがって,ハッシュテーブルも検索アルゴリズムの役割を果たす.
また、ハッシュはデータ量に与える影響が小さく、パフォーマンスが速い.

クイックナビゲーション

クイック挿入

クイック削除

0.2. ハッシュたんさくほう

ハッシュ探索法は、データの内容と格納された要素を予め接続して、極めて短い時間で探索を行うアルゴリズムである.

Big-O性能の比較

ハッシュナビゲーション->O(1)O(1)O(1)

バイナリナビゲーション->O(logn)O(logn)O(logn)

リニアナビゲーション->O(n)O(n)O(n)

1.Hash Function-Hash関数

ハッシュ関数は、ハッシュテーブル内のbucket(=hash)に鍵をマッピングする.

検索/挿入/削除

に関係なく、ハッシュ関数は、キーによって格納された値に関連するハッシュ(インデックス)を返す.

ハッシュ関数の入力値は多様であり、出力値はデジタル形式である.

ハッシュ関数要件

入力値は同じであり、出力値も同じであるべきである.

I/O値が一定でない場合、適切なハッシュ関数ではありません.

入力値「aqua」が4を返すと、入力値「beige」は4を返すことができません.

ハッシュ関数は、特定の範囲内の数値を返さなければならない.

ハッシュ関数の入力データがそれぞれ異なる数値にマッピングされる場合、ハッシュ関数は完璧なハッシュ関数である.

ハッシュ関数が入力データに基づいて異なる数値を返す場合、これはハッシュ競合を最小化する.

1.1. デフォルトハッシュ関数

ハッシュ関数は、通常、整数値を文字列入力値に返します.
Pythonにおいて.encode法を用いて문자열 to 바이트 코드として符号化された例によって、ハッシュ関数の基本的知識が理解される.
まず、byte codeで特定の文字列を表します.

bytes_representation = "hello".encode()

for byte in bytes_representation:
    print(byte)
    
#
104 #'h'
101 #'e'
108 #'l'
108 #'l'
111 #'o'

ハッシュ関数を使用してすべてのバイトコード(整数値)の和を返す方法で、入力文字列に対応する特定のハッシュ値を作成します.

bytes_representation = "hello".encode()

sum = 0
for byte in bytes_representation:    
    sum += byte

print(sum)

上記のプロパティを持つハッシュ関数が作成されます.

def my_hashing_func(str, list_size):
    bytes_representation = str.encode()
    sum = 0

    for byte in bytes_representation:
        sum += byte
    
    print('sum', sum)
    print('list_size', list_size)
    print('sum % list_size', sum % list_size)

    return sum % list_size # a hash

生成されたハッシュ関数を使用します.

#리스트 값 None 초기화
my_list = [None] * 5 

#해시함수를 통과한 문자열의 해시값을 리스트의 인덱스로 하여 값(value) 입력
my_list[my_hashing_func('aqua', len(my_list))] = "#00FFFF" #value

#리스트에 입력된 값 확인(해시함수를 통한 값 검색)
print("========")
print(my_list[my_hashing_func('aqua', len(my_list))])

#업데이트된 리스트 확인
print("========")
print(my_list)

2.ハッシュ性能

O(1)O(1)O(1)時間の複雑さ内で検索,挿入,削除を行うことができる.

定数時間はハッシュ表サイズに関係なく同じ数の計算を処理する.

しかし、ハッシュ競合のため、すべてのbucketの値(重複)を検索する必要があります.

Created on Dec 1, 2021

作文