[Blockchain] 해시 테이블(Hash Table)이란?

해시 테이블은 해시 함수를 돌린 해시를 색인(index)로 사용해 키와 데이터를 저장하는 자료구조입니다. 키(key)값은 해시 함수를 돌려 출력된 해시를 사용하고 키에 해당하는 데이터(value)와 함께 저장합니다. 해시 테이블은 핸드폰 단축 번호와 동일한 원리를 가지고 있습니다. 010-1111-1111, A, 단축번호 1번으로 저장된 연락처에 전화를 걸기 위해서는 미리 저장된 1번만 누르면 됩니다. 

 

 

 

해시 테이블 구조

 

해시 테이블은 키(Key)와 해시함수(Hash Function), 해시(Hash), 데이터(Value)로 구성됩니다.

• 키(Key) : 해시 함수의 입력값입니다. 고유한 값을 가지고 있으며, 다양한 길이가 입력될 수 있지만 해시 함수로 해싱한 결과값이 최종 저장됩니다.
• 해시함수(Hash Function) : 키(Key)를 해시(Hash)로 변환해주는 역할을 담당합니다. 다양한 길이의 키(Key)를 고정된 길이의 해시(Hash)로 변경해 저장소를 효율적으로 운영합니다. 서로 다른 키(Key)가 동일한 해시값을 가지는 해시 충돌(Hash Collision)을 주의해야 합니다. 
• 해시(Hash) : 키(Key)값을 해시 함수를 돌려 반환된 최종 결과물입니다. 데이터에 매칭되며, 데이터를 검색하는 인덱스 역할을 담당합니다.
• 데이터(Value) : 저장소에 저장되는 값이며, 해시와 함께 매칭됩니다.

 

해시 테이블 시간복잡도

 

 

 

해시 테이블을 사용한 저장/삭제/검색 로직은 평균적으로 O(1)의 시간복잡도를 가집니다. 즉, 데이터를 다루는데 매우 빠른 성능을 보입니다. 보통 O(N Log N) 정도만 되도 준수한 성능을 보이는데, O(1)은 알고리즘에서 이상적인 시간복잡도입니다.

하지만 해시 테이블에도 단점은 존재합니다. 해시 충돌(Hash Collision)이 발생할 가능성을 배제할 수 없고, 데이터가 저장되기 전 미리 저장소를 생성해야 하기 때문에 공간 복잡도는 올라가게 됩니다. 또한 키(Key)를 변환하는 해시 함수에 대한 의존도가 높습니다. 즉, 해시 함수가 복잡하게 설계되면 해시 테이블의 성능이 크게 떨어집니다.

 

해시 테이블 작동 순서

 

① 해시 함수(Hash Function)에 키(Key)값을 넣고 해시(Hash)를 출력합니다.

② 해시(Hash) 값과 매칭되는 색인(Index)를 찾아 데이터를 저장/삭제/검색 합니다.

③ 만약 해시 충돌이 발생하는 경우 저장소의 모든 색인을 참조해야 하므로 시간복잡도는 O(N)이 되어 버립니다. 

④ 일반적인 경우 해시 테이블의 시간복잡도는 O(1)입니다.

 

 

 

해시 테이블 알고리즘

 

Division Method

Number 타입 키(Key)를 저장소 크기로 나눕니다. 이렇게 나온 결과를 색인(Index)로 사용해 데이터를 저장/검색/삭제하는 방법입니다. 저장소의 크기를 소수(Prime Number)로 지정하고 2의 제곱수와 먼 값을 사용합니다. 예를 들어 Key가 23, 테이블의 크기가 7이라면 Index는 2가 됩니다. 

 

Digit Folding

키(Key) 문자열을 ASCII 코드로 변경한 값을 합해 저장소의 색인(Index)로 사용하는 방법입니다. 만약 색인(Index)이 저장소 크기를 넘어가는 경우 Division Method를 사용합니다. 

 

Multiplication Method

Number 타입의 키(Key) K와 0과 1사이의 실수 A, 2의 제곱수 m을 사용해 인덱스(Index) = (KA mod 1)m 으로 사용합니다. 

 

Universal Hashing

여러개의 해시 함수(Hash Function)을 생성해 특정 장소에 저장해두고 랜덤으로 해시함수를 선택해 해시값을 만들어 사용하는 방식입니다.

 

해시 충돌 방지 방법

 

해시 테이블을 사용할 때 주의해야 할 점이 바로 해시 충돌(Hash Collision)입니다. 서로 다른 값을 입력했지만 동일한 결과를 낼 수 있기 때문입니다. 해시 충돌을 방지 하기 위한 방법으로는 개방 연결법과 분리 연결법을 사용할 수 있습니다. 

① 개방 연결법

해시 충돌이 발생한 경우 배열(ArrayList)를 사용합니다.

• Linear Probing : 해시 충돌이 발생할 경우 선형 탐색을 통해 다음 빈 셀에 새 키를 배치합니다.
• Quadratic Probing : 기존 해시 값에 임의의 2차 다항식의 연속값을 추가하면서 해시 충돌을 방지합니다.
• Double Hashing Probing : 해시값에 현재 주소를 더해 새로운 주소를 얻습니다. 

 

 

② 분리 연결법

해시 테이블의 셀마다 Linked List에서 사용되는 Node 객체를 저장합니다. 해시 충돌이 발생하면 Linked List의 다음 노드로 계속해서 추가해가면서 데이터를 저장합니다. 데이터를 검색할 때는 인덱스에 해당하는 list를 순차적으로 검색하면서 탐색하게 됩니다.  

 

 

 

[Blockchain] DAG(Directed Acyclic Grpah) 란?

 

[Backtracking] 백준 15651 N과 M 3단계 Node.js 구현하기

 

[Algorithm] DFS Tree 순회 알고리즘