해시테이블 & DHT (Distributed Hash Table)

💡 해시 테이블 (Hash Table)

 

해시 테이블이란 해시 함수를 사용하여 변환한 해시를 색인으로 삼아 키와 데이터를 저장하는 자료구조이다. 이 해시 테이블은 쉽게 핸드폰으로 통화를 하기 위해, 단축번호를 설정하여 사용하는 것과 같다고 생각하면 된다. 김해시, 010-1111-2222, 단축번호 : 1 이라는 사람에게 전화를 걸기 위해 미리 사용자가 저장한 단축번호 1을 누르면 010-1111-2222 번호로 바로 통화를 할 수 있다. 이 과정처럼, 필요한 데이터의 키는 해시함수를 사용해 별도의 해시로 바꿔 주고, 해당하는 데이터를 함께 저장하는 자료구조이다.

 

 

✓ Hash Table의 구조

 

hash table은 키와 해시함수, 해시, 데이터로 이루어져있다.

 

- 키(key): 고유한 값으로 해시 함수의 입력값이 된다. 다양한 길이의 값이 들어올 수 있다. 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하므로 해시 함수의 값을 바꾸어 저장하게 된다. 

- 해시함수(hash function): 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌이라 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.

- 해시(hash): 키는 해시함수를 사용하여 만들어진 결과물로, 저장소에서 데이터와 매칭되어 저장된다. 변환된 값을 배열의 색인과 같이 사용하게 된다.

- 데이터(value): 저장소에 최종적으로 저장되는 값으로 색인과 매칭되어 저장된다.

 

 

✓ Hash Table의 특징

 

hash table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠르다는 장점이 있다. 다만, 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 해서 공간 효율성이 떨어진다. 또한 해시 함수의 의존도가 높다. 이 말은 해시 함수가 복잡하다면 해시 값을 만들어내는 데 많은 시간이 소요된다는 것을 의미한다.

 

1. 저장, 삭제, 검색 과정

hash table에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수에 키 값을 넣어 해시 값을 만들게 된다. 이후 만들어진 해시 값과 일치하는 색인을 찾아 저장하거나 삭제, 검색한다. 기본적으로 해당 작업들의 시간복잡도는 O(1)이다. 해시 함수를 거쳐 해시 값을 찾아내는데 걸리는 과정은 고려하지 않는다. 그러나 해싱 충돌이 발생할 경우 저장소의 모든 색인 혹은 데이터를 찾아봐야 하므로 O(n)이 된다.

 

2. 대표적인 해시 알고리즘

- Division Method: Number type의 키를 저장소의 크기로 나우어 나온 나머지를 색인으로 사용하는 방법이다. 이때 저장소의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋습니다. 예를 들어 key 값이 23일 때, 테이블 크기가 7이라면 index는 2가 된다.

- Digit Folding: 키의 문자열을 ASCII코드로 바꾸고 그 값을 합해 저장소에서 색으로 사용하는 방법이다. 만약, 이 때 색인이 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있다.

- Multiplication Method: 숫자로 된 Key 값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 사용한다. index = (KA mod 1)m

- Universal Hashing: 다중의 해시함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

 

 

💡DHT (Distributed Hash Table) - 분산 해시 테이블

 

분산 해시 테이블은 해시 테이블을 활용해, 키-값 쌍 방식으로 데이터를 검색하는 분산형 데이터베이스이다. DHT는 Peer-to-peer 환경에서 데이터를 분산하여 저장할 때 사용한다.

 

✓ DHT 에 데이터를 저장하는 방법

 

1. 다음과 같은 해시테이블이 있다고 가정하고, 이 해시 테이블의 범위는 0부터 7까지이다.

2. 테이블은 4명의 호스트가 사용하고, 호스트들은 각각 공유해야 할 데이터를 가지고 있다.

 

3. 각 해시테이블의 인덱스에 호스트의 IP 주소를 넣고, 정해진 해시테이블의 인덱스 안에 호스트 주소를 할당하기 위해 호스트의 IP 주소를 해싱하여, 해싱한 결과값을 8로 나눈 나머지 값을 인덱스로 한다. 이 호스트들은 자신 다음에 있는 호스트 중 가장 가까이에 있는 호스트의 IP 주소를 알게 된다.

 

 

4. 해시 테이블의 인덱스에는 호스트의 IP 주소 외에도, 데이터의 위치를 저장한다. 각 호스트는 공유해야 하는 파일 가지고 있었고, 이 파일들 역시 IP 주소를 해싱하여 인덱싱했던 것처럼 동일한 방식으로 해싱한다. 이렇게 나온 해시값을 그대로 해시테이블에 인덱싱한다. 가령, '기획서.hwp'의 해시값은 5이므로, 해시테이블의 인덱스 5에 있는 호스트인 789.0.5.4는 "기획서.hwp는 123.0.20.8에 있다라는 것을 기억하게 되는 것이다. 카카오톡.exe의 해시값은 7이지만 7번 인덱스에는 호스트가 없기 때문에, 가장 인접한 호스트인 101.0.234.5가 카카오톡.exe의 위치를 저장한다.

 

 

✓ DHT 에 데이터를 찾는 법 - 456.0.13.2 컴퓨터가 카카오톡 파일을 찾는다고 가정!

 

1. 456.0.13.2 는 자신의 가장 가까운 컴퓨터인 123.0.20.8 에게 카카오톡 파일이 어디 있냐고 물어본다.

 

2. 하지만 123.0.20.8은 가계부의 위치는 알지만 카카오톡의 주소는 모른다. 따라서 가장 가까운 컴퓨터인 789.0.20.8 에게 어딨냐고 물어본다.

 

3. 이 과정을 카카오톡이 어딨는지 알아낼때까지 반복한다.

4. 어딨는지 아는 컴퓨터가 나타나면 처음 질문했던 456.0.13.2에게 위치를 알려준다.