[TOC]
해시테이블(Hash Table)은 해시함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 key와 value를 저장하는 자료구조이다.
구조
- 키(key): 고유한 값으로 해시 함수의 입력값이 된다. 다양한 길이의 값이 들어올 수 있으며, 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해두어야 하므로 해시 함수로 값을 바꾸어 저장하게 된다.
- 해시함수(Hash Function): key를 hash로 바꿔주는 역할을 한다.단, 서로 다른 key가 같은 hash가 되는 해시 충돌(Hash Collision) 확률을 줄이는 것이 중요하다.
- 해시(Hash): key는 hash function을 사용해 만들어진 결과물로, 저장소에서 value와 매칭되어 저장된다. 변환된 값을 배열의 색인(index)과 같이 사용하게 된다.
- 데이터(Value): 저장소에 최종적으로 저장되는 값으로 색인(index)과 매칭되어 저장된다.
특징
- 저장, 삭제, 검색 과정 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어, 데이터를 다루는 작업이 매우 빠르다.
- 해시 충돌이 발생할 수 있으며, 데이터 저장 전 저장공간을 미리 만들어놔야하기 때문에 공간 효율성이 떨어진다.
- 해시함수의 의존도가 높아, 해시 함수가 복잡하면 해시값을 만들어내는데 많은 시간이 소요된다.
저장, 삭제, 검색 과정
Hash Table에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수에 key 값을 넣어 해시값을 만들게 된다. 이후 만들어진 해시값과 일치하는 index를 찾아 저장/삭제/검색한다.
기본적으로 저장/삭제/검색 작업들의 시간복잡도는 O(1)이다. 하지만 해시 충돌이 발생한 경우, 저장소의 모든 index 혹은 value(데이터)를 찾아봐야 하므로 O(n)이 딘다.
DHT(Distributed Hash Table, 분산 해시테이블)는 해시 테이블을 활용해, key-value 쌍 방식으로 데이터를 검색하는 분산형 데이터베이스이다. DHT는 P2P 환경에서 데이터를 분산하여 저장할 때 사용한다.
데이터 저장 과정
-
임의의 해시 테이블이 있다고 가정한다. 테이블 범위는 0 ~ n, 호스트는 m(단, m < n)명이며, 각 호스트들은 공유해야 할 데이터를 가지고 있다.
-
각 해시테이블의 인덱스에 호스트의 IP 주소를 넣는다. 정해진 해시테이블의 인덱스 안에 호스트의 주소를 할당하기 위해, 호스트의 IP주소를 해싱하여 해싱한 결과값을 (n+1)로 나눈 나머지 값을 인덱스로 한다. (가칭:
index1)(이 호스트들은 자신 다음에 있는 호스트 중 가장 가까이에 있는 호스트의 IP주소를 알게 된다.)
-
해시 테이블에 인덱스에는 호스트의 IP주소 외에도, 데이터의 위치를 저장한다. 각 호스트의 공유해야 하는 파일 역시 IP주소를 해싱하여 인덱싱했던 것처럼 동일한 방식으로 해싱한다. (가칭:
index2)(여기서 나온 해시값을 그대로 해시테이블에 인덱싱한다. 예를 들어 해시값이 5라면, 해시 테이블의 인덱스 5에 있는 호스트가 해당 해시값(데이터의 위치)를 기억한다.)
데이터 검색 과정
특정 호스트 A가 x 데이터을 찾는 경우, 가장 가까운 호스트 B에게 x 데이터 위치를 보유 중인지 확인한다. B도 없을 경우, B는 가장 가까운 호스트 C, ..., 이렇게 반복 후, 최종적으로 x파일 위치 데이터를 알고 있는 호스트가 있으면, 해당 호스트가 A에게 x 데이터 위치를 알려준다.
Copyright © 2022 Song_Artish