해시(hash) 테이블

해시 테이블이란?

여러가지 물건들이 있는데, 이걸 일렬로 세워놓지 말고 바구니 몇개 만들어서 바구니 A, 바구니 B, …에 넣어두자는거다.

key, value 쌍으로 자료를 저장하는 자료구조중 하나.
key → 해시값 → index

해시 함수를 사용하여 key를 해시값으로 매핑하고, 이 해시값을 index 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하고 검색하는 자료구조.

해시 함수(hash function)란, 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.

이 때 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)이라고 한다.

시간 복잡도

O(1) ~ O(N) 로 가능한데, O(1)이 가능한 이유는 각각의 key와 value가 1:1 매핑되어있다면 바로 원하는 key로 value에 접근이 가능하기 때문이다. (딕셔너리와 유사)

그렇다면 O(N)이 나오는 이유는 무엇일까?

해시 함수는 해시값의 개수보다 대개 많은 키값을 해시값으로 변환하는데, 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내거나 인덱스가 같아지는 해시 충돌(collision)이 발생하게 됨. 그러기 시작하면 O(N)이 걸리게 된다.

해싱 충돌의 해결 방법

Chaining

링크드리스트를 생각하면 된다.

데이터의 개수가 n이고 해시테이블이 쓰는 배열의 크기가 m이라고 할 때, 링크드 리스트들의 평균 길이(한 버킷에 매핑되는 키의 평균 개수)는 n/m(=α)이다. 따라서 이 경우에 해시테이블의 각 연산은 평균적으로 O(n/m)이 걸린다라고 할 수 있다. 공간을 많이 줄수록 시간복잡도가 줄어듬.

	평균	최악
삽입(head)	O(1)	O(1)
삭제	O(α)	O(n)
탐색	O(α)	O(n)

탐색,삭제의 시간복잡도는 버킷당 요소 개수의 평균 α가 좌지우지하는 구조다. 최악의 경우 한 버킷에 모든 데이터가 들어있어 O(n)이 될 수 있다. 하지만 보통의 경우 데이터의 개수가 해시테이블 크기의 두 세배쯤(α가 2~3)만 되어도 탐색, 삭제는 O(1)에 가까워진다.

• 장점 : 간단하게 구현이 가능하며 삭제 작업이 간단하다. 그리고 해시 테이블의 확장이 필요없다.
• 단점 : 공간이 적거나 데이터의 수가 많아지면 그만큼 연결되는 리스트가 많아지고 효율성이 떨어진다.

나머지 방법들

• Open Addressing(개방 주소법) : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용한다. 해당 키 값에 저장되어있으면 다음 주소에 저장하는 방식. 보통 고정적인 크기의 배열을 사용
  • 선형 탐사 : 정해진 고정 폭으로 옮겨 해시값의 중복을 피함
  • 제곱 탐사 : 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함

내 생각

딕셔너리랑 크게 차이가 있는지는 모르겠다. 해시테이블이 딕셔너리를 구현하는데 쓰는 방법중 하나라고 한다.

만약 데이터의 개수가 예측 가능한 상황이고 메모리 공간이 충분하다면, 해시를 쓰는게 좋은 것 같다. 데이터의 개수가 엄청 많거나 예측할 수 없는 상황이라면.. O(log n)인 이진 트리쪽이 더 안정적이고 효율적일듯.

SHA256이 해싱 알고리즘이라고 한다!

SHA-256은 메시지, 파일, 혹은 데이터 무결성 검증에 널리 사용되는 암호화 해싱 알고리즘(함수)입니다. SHA-256은 넓게는 SHA-2 패밀리에 속하고 변환하기를 원하는 문자들을 256 bit 길이의 key로 변환합니다. SHA-256을 사용하면 문자가 조금만 바뀌어도 해시값이 완전히 변합니다.

참조

https://ratsgo.github.io/data structure&algorithm/2017/10/25/hash/

https://www.youtube.com/watch?v=Vi0hauJemxA

https://gyoogle.dev/blog/computer-science/data-structure/Hash.html

https://mangkyu.tistory.com/102