해시 테이블, DHT

• Hash Table이란 키를 입력값으로 해시함수(hash function)을 사용하여 변환한 해시(hash)값을 색인으로 삼아 키와 데이터를 저장하는 자료 구조 입니다

해시함수를 사용하여 변환한 해시를 색인으로 삼는 Key-value 구조

hash table에서 저장, 삭제 검색 과정 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루다 작업이 빠르다

다만, 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 해서 공간 효율성을 떨어진다 

 

해시 함수가 복잡해지면 해시값을 만들어내는데 많은 시간이 소요되 해시 함수가 중요

 

Hash Table 구조 

- Key :  다양한 길이의 값이 들어올 수 있음, 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야함 

 

- Hash Fuction : Key를 hash로 바꿔주는 역할을 함, 서로 다른 키지만 같은 해시가 되는 해시 충돌 위험이 있음

 

- Hash : 해시 함수를 사용하여 만들어진 결과물, 저장소에 데이터와 매칭되어 저장  

 

- data : 저장소에 최종적으로 저장되는 값으로 색인(index)와 매칭되어 저장

 

 

대표적인 해시 알고리즘 

- Division Method :

Number type의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인으로 사용하는 방법 

저장소의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋음

예를 들어, Key값이 23일때 테이블의 크기가7이면 index는 2 

 

- Digit Folding

키(key)의 문자열을 아스키코드로 바꾸고 그 값을 합해 저장소에서 색인으로 사용하는 방법 

 

- Multiplication Method

숫자로된 Key 값 K와 0~1 사이의 실수 A, 보통 2의 제곱수인 M을 사용하여 다음과 같이 계산

index = (KA mod 1)m

 

- Universal Hashing

다수의 해시 함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시 값을 만드는 방법 

 

해시 충돌 해결 방안 

개방 연결법

• Linear Probing
• Quadratic Probing
• Double Hashing Probing

분리 연결법

 

 

DHT(Distributed Hash Table)

- DHT는 해시 테이블을 활용해, K-V 쌍 방식으로 데이터를 검색하는 분산형 데이터베이스

- DHT는 P2P 환경에서 데이터를 분산하여 저장할때 사용

 

DHT 저장 방식

1. 해시 테이블범위가 0~7 까지 

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

3.  각 해시테이블의 인덱스에 호스트 IP주소를 삽입, 정해진 해시 테이블의 인덱스 안에 호스트의 주소를 할당하기 위해 호스트의 IP주소를 해싱 해싱한 결과값을 8로 나눈 나머지 값을 인덱스로 한다 

 

4. 이후 호스트들은 자신 다음에 있는 호스트 중 가장 가까이에 있는 호스트의 IP주소를 알게 됨

 

5. 해시 테이블에 인덱스에 호스트의 IP주소 외에도, 데이터의 위치를 저장 

각 호스트는 공유해야 하는 파일을 가지고 있음 

이 파일들 역시 IP주소를 해싱하여 인덱싱한거 처럼 동일한 방식으로 해싱

 

 

이렇게 나온 해시값을 그대로 해시테이블에 인덱싱

'기획서.HWP'의 해시 값은 5이므로, 해시 테이블의 인덱스5에 있는 호스트인 789.0.5.4는 기획서가 123.0.20.8에 있는것을 기억하게 되는 겁니다!

 

 

DHT 데이터 검색 방식 

 

458.0.13.2 컴퓨터가 카카오톡.exe를 찾는다고 가정 

1.456.0.13.2는 자신의 가장 가까운 컴퓨터인 123.0.20.8에게 요청 

 

2. 456.0.13.2는 자신의 가장 가까운 컴퓨터인 123.0.20.8 에게 요청 

 

3. 123.0.20.8 은 가계부.csv 위치는 알지만 카카오톡 위치 주소는 모르기 때문에 자신의 가장 가까운 컴퓨터인 789.0.20.8에게 카카오톡 위치를 물어본다 

 

4. 789.0.20.8 또한 모르기 떄문에 위와 같이 가까운 컴퓨터에게 요청 

 

 

5. 101.0.234.5 는 카카오톡.exe 위치를 알기에 처음 요청했던 456.0.13.2에게 카카오톡 위치를 알려줌