자료구조) 해쉬 테이블(1/2) - 해쉬테이블이 무엇인가?

Hash Table?

해쉬테이블은 (키-밸류)쌍으로 저장하는 구조이다. 조금 더 정확하게 얘기하자면 (키-밸류)에서 해슁함수를 통한 키값인 해쉬값 위치에 해쉬테이블 주소를 두고 키와 밸류를 저장하는 것을 말한다. 

(키-밸류)쌍으로 저장하기 때문에 삽입, 삭제, 검색이 모두 O(1)로 정말 빠르다. 하지만 그만큼 공간을 많이 차지하게 되어서 공간과 시간을 맞바꾼 자료구조로 볼 수 있다. 

파이썬에는 딕셔너리 구조가 해당된다.

그래서 파이썬에서는 특별하게 해쉬 테이블을 구현할 필요는 없다. 그래도 조금 더 해쉬테이블을 톱아보자

Direct Address Table

해슁 함수를 통한 해쉬 테이블이 있기 전에는 Direct Address Table(직접 주소화 테이블)이 있었다. 

직접 주소화 테이블은 키와 밸류가 있을때, 키의 숫자 대로 테이블에 저장하는 것을 의미한다.  

이 방식은 키의 숫자의 차이들이 어마어마 할때 불필요한 메모리 낭비를 초래할 수 있고,

숫자가 아닌 다양한 형태의 키를 사용하지 못한다는 단점이 있다. 

 

Hash Funtion & Hash Table

그래서 나오게 된 것이 해슁함수를 통한 해쉬 테이블이다. 

해슁테이블에 필요한 단어를 먼저 살펴봐보자

• 해쉬 : 임의의 값을 고정 길이로 변환하는 것
• 해쉬 테이블 :키값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해슁 함수 : 키값에 대한 산술 연산으로 데이터의 위치를 찾을 수 있게 하는 함수
• 해쉬값, 해쉬 주소 : 해싱함수를 통한 변환된 키값, 이를 기반으로 테이블에서 해당 키에 대한 데이터 위치를 일관성 있게 알 수 있다. 
• 슬롯 : 한개의 데이터를 저장할 수 있는 공간으로 해쉬 테이블을 구성하고 있으며, 키-밸류 데이터를 저장할 수 있는 각각의 공간이다.  

해쉬 테이블의 과정을 봐보자

(키-밸류)가 존재할때, 해슁 함수 h에 키를 넣어 일관된 길이의 해쉬값 h(k)를 얻을 수 있다. 해쉬테이블에 h(k)의 위치가 있고, 거기에다 밸류를 저장하게 된다.

결국 정리했을때

(키-밸류) -> 해쉬 함수 => (h(키),밸류)

(h(키),밸류) -> 해쉬테이블[....., 밸류,...]이며,

해쉬테이블.index(밸류) = h(k) 라는 얘기이다. 

 

간단한 예시를 만들어 보자

해쉬 함수는 굉장히 다양한데, 가장 간단한 방법으로 Division 방법이 있다. 

Division 방법은 키를 숫자로 나눈 나머지를 해쉬값으로 사용하는 것이다. 특히 10이하의 자연수를 사용할때 나머지의 자릿수가 같기 때문에 hash 함수로 적합하다. 

def hash_funtion(key):
	if type(key) == str : #키가 문자열일 경우 문자열의 첫번째를 아스키 코드로 만들어서 사용
    	key = ord(key[0])
	hash_key = key % 10
    return hash_key

데이터를 저장할 해쉬 테이블을 만든다.

hash_table = list([0 for i in range(10)])

해쉬 테이블에 데이터를 저장해보자

def save(key, value):
	hash_key = hash_function(key)
    	hash_table[hash_key] = value

해쉬 테이블에서 데이터를 불러와보자

def load(key) :
	hash_key = hash_funtion(key)
    return hash_table[hash_key]

 

이런 해쉬테이블의 장점은 검색, 삽입, 삭제의 속도가 O(1)로 정말 빠르다는 것이고, 해쉬는 키에 대한 데이터가 있는지 없는지 확인이 쉬우며, 중복 확인이 쉽다.  

단점으로는 일반적인 자료구조보다 더 많은 메모리를 필요로 하며, 여러키에 해당하는 주소가 충돌(collision)할 경우, 충동을 해결하기 위한 별도의 방법이 필요하다.

앞선 예시처럼, 만약 Andy와 And가 있다고 할때, 둘다 A이기 때문에 해쉬값이 같다.

 

이런 해쉬테이블은 자료 검색, 삭제, 추가가 빈번하게 일어날때, 중복 확인이 쉽기 때문에 캐쉬 구현할때 사용된다. 

 

다음에는 해쉬 충돌을 해결할 수 있는 방법은 뭐가 있는지, 좋은 해쉬함수란 무엇인지 알아보자