ハッシュ・テーブル(1)-ハッシュ・テーブル/ハッシュ関数/ハッシュ競合
7574 ワード
0. Hash Table
ハッシュテーブルは、キーと値のペアを構成する抽象データ型であり、キーを迅速に格納および取得できるテーブル型データ構造である.
その結果、キーを使用して値に直接アクセスできる構造になります.
0.0. Hash
ハッシュはハッシュ関数によって得られる値です.
ハッシュ関数
:各ハッシュ値に複数のキーを一致させるためのロールの関数
0.1. Hashing
ハッシュとは、キーと値をマッピングするプロセスです.
ハッシュの目的は「検索」です.簡単に言えば、すべてのコンテンツを分散し、キーに一致する値を検索するプロセスです.
したがって,ハッシュテーブルも検索アルゴリズムの役割を果たす.
また、ハッシュはデータ量に与える影響が小さく、パフォーマンスが速い.
0.2. ハッシュたんさくほう
ハッシュ探索法は、データの内容と格納された要素を予め接続して、極めて短い時間で探索を行うアルゴリズムである.
Big-O性能の比較
1.Hash Function-Hash関数
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)時間の複雑さ内で検索,挿入,削除を行うことができる.
Reference
この問題について(ハッシュ・テーブル(1)-ハッシュ・テーブル/ハッシュ関数/ハッシュ競合), 我々は、より多くの情報をここで見つけました https://velog.io/@citizenyves/Hash-Table1-해시테이블해시함수해시충돌テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol