https://ratsgo.github.io/data structure&algorithm/2017/10/25/hash/
해쉬 함수 (hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.
이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 **해싱(hashing)**라고 합니다.
해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문에 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 **해시충돌(collision)**이 발생하게 됩니다.
해시충돌이 발생할 가능성이 있음에도 해시테이블을 쓰는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다. 예컨대 해시함수로 하드디스크나 클라우드에 존재하는 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑합니다. 이러한 방식으로, 해시 테이블은 메모리를 효율적으로 사용하면서도 높은 성능을 제공합니다.
해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근할 수 있으며, 색인은 계산이 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적입니다. 다시 말해 해시는 데이터 액세스(삽입, 삭제, 탐색)시 계산복잡성을 O(1)을 지향합니다.
해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 **해시테이블(hash table)**이라고 합니다. 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot)이라고 합니다. 해시테이블의 기본 연산은 삽입, 삭제, 탐색(search)입니다.
보통의 경우 Direct-address table보다는 “해시테이블 크기(m)가 실제 사용하는 키 개수(n)보다 적은 해시테이블”을 운용합니다. 다뤄야할 데이터가 정말 많고, 메모리 등 리소스 문제도 생기기 때문입니다. 이 때 n/m을 load factor(α)라고 합니다. 해시테이블의 한 버킷에 평균 몇 개의 키가 매핑되는가를 나타내는 지표입니다. Direct-address table의 load factor는 1 이하이며, 1보다 큰 경우 해시충돌 문제가 발생합니다.
현재 가장 널리 사용되는 암호학적 해시 함수 중 하나. 주로 보안 분야에서 데이터 무결성 검증, 디지털 서명, 블록체인 등 다양한 용도로 사용됨.
https://velog.io/@ham3798/SHA-256-해시-알고리즘에-대하여
import hashlib
def sha256_hash(data):
sha256 = hashlib.sha256()
sha256.update(data.encode('utf-8'))
return sha256.hexdigest() # 해시 값을 16진수 문자열로 반환
# 사용 예시
data = "Hello, World!"
hash_value = sha256_hash(data)
print(f"SHA-256 hash: {hash_value}")
# SHA-256 hash: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f
chaining은 해시테이블의 크기를 유연하게 만들고, open addressing은 해시테이블 크기는 고정시키되 저장해 둘 위치를 잘 찾는 데 관심을 둔 구조입니다. 이뿐 아니라 해시함수를 개선하는 접근도 있습니다.
Chaining: