Algorithm | 자료구조 : Hash Table

Hash Table

 해시 테이블(Hash Table)은 자료의 탐색을 위한 알고리즘으로 탐색 키워드인 Key와 그에 대한 결과 값인 Value가 한 쌍으로 저장된 자료구조이다. 해시 테이블은 해싱(Hashing)을 통해 Key 값에 알맞은 Value를 찾아낸다.

Hashing?

 해싱은 Key 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해싱에서 자료를 저장하는 데 배열을 사용한다. 배열은 원하는 항목이 저장된 인덱스(index)를 알고 있을 경우 O(1)의 시간 복잡도로 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 배열의 인덱스는 0부터 시작하는 정수로 문자열인 Key를 통해 배열로 저장된 Value에 접근하기 위해서는 해시 함수(Hash Function)를 통해 Key에 알맞은 배열의 인덱스를 찾을 수 있다.

Hash Function

 해시 함수는 문자열을 받아서 숫자를 반환하는 함수로 문자열에 대해 숫자를 할당(Mapping)하는 함수이다.

 

 만약 "수박"이라는 문자열을 넣으면 7이 반환되는 해시 함수가 존재한다고 해보자. 이 때, 어떠한 상황에서도 해시함수는 "수박"을 넣어주면 7을 반환해야 한다. 그리고 "수박" 이외에 다른 문자열을 넣어 주었을 때 7을 반환해서는 안된다. 즉, 해시함수는 각각의 문자열에 대해 일관성이 존재해야 한다. 그렇지 않으면 충돌이 발생하여 탐색 시 오류가 발생하게 된다.

 

해시 테이블의 구조   출처 https://gongbu-ing.tistory.com

 위의 그림은 과일 가격표를 해시 테이블을 이용하여 표현한 것이다. "수박"을 입력하면 해시 함수는 7이라는 결과값을 내놓게 되고 이 해시 함수의 결과값을 이용하여 배열에 저장된 수박의 값(18000)을 한 번에 찾아낼 수 있다. 같은 원리로 "파인애플"은 5000, "오렌지"는 3000, "키위"는 1000, "포도"는 7000을 값으로 탐색할 수 있다.

---

Reference

 

· 해시-해시테이블-해싱 5분만에 이해하기 - https://www.youtube.com/watch?v=xls6jEZNA7Y

· 해싱(Hasing)의 기본 개념 - https://mattlee.tistory.com/62