해시테이블이란 키를 입력값으로 해시함수를 사용하여 변환한 해시값을 색인으로 삼아 키와 데이터를 저장하는 자료구조이다.
키는 해시함수를 사용해 별도의 해시로 바꿔주고, 해당하는 데이터를 함께 저장하는 구조이다.
해시테이블의 특징
저장, 삭제, 검색 과정
: 해시테이블에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수에 키 값을 넣어 해시값을 만들게 된다. 이후 만들어진 해시값과 일치하는 색인을 찾아 저장하거나, 삭제, 검색한다.
해시함수를 거쳐 해시값을 찾아내는데 걸리는 과정은 고려하지 않지만, 해시 충돌이 발생할 경우 저장소 모든 색인 혹은 데이터를 찾아봐야 하므로 O(n)이 된다.
대표적인 해시 알고리즘
DHT(분산 해시테이블)은 해시 테이블을 활용해, 키-값 쌍 방식으로 데이터를 검색하는 분산형 데이터베이스이다.
DHT는 P2P환경에서 데이터를 분산하여 저장할 때 사용한다.
다음과 같은 해시테이블이 있고, 해시테이블의 범위는 0~7이라고 가정한다.
그리고 이 테이블을 4명의 호스트가 사용한다.
호스트들은 각각 공유해야할 데이터를 가지고 있다.
이제 각 해시테이블의 인덱스에 호스트 IP 주소를 넣는다.
정해진 해시테이블의 인덱스 안에 호스트의 주소를 할당하기 위해, 호스트의 IP주소를 해싱하여, 해싱한 결과값을 8로 나눈 나머지 값을 인덱스로 한다.
이 호스트들은 자신 다음에 있는 호스트 중 가장 가까이에 있는 호스트의 IP주소를 알게 된다.
해시 테이블에 인덱스에는 호스트의 IP주소 외에도, 데이터의 위치를 저장한다.
각 호스트는 공유해야 하는 파일을 가지고 있었다.
이 파일들 역시 IP주소를 해싱하여 인덱싱 했던 것처럼 동일한 방식으로 해싱한다.
이렇게 나온 해시값을 그대로 해시테이블에 인덱싱한다.
가령, ‘기획서.hwp’의 해시값은 5이므로, 해시테이블의 인덱스 5에 있는 호스트인 789.0.5.4는 “기획서.hwp는 123.0.20.8에 있다” 라는 것을 기억하게 되는 것이다.
카카오톡.exe.의 해시값은 7이지만, 7번 인덱스에는 호스트가 없기 때문에, 가장 인접한 호스트인 101.0.234.5가 카카오톡.exe 의 위치를 저장한다.
