자료 구조 | 해시 테이블

연결 리스트나 트리에서 값을 검색할 땐 O(n) 또는 O(log n)의 시간이 걸린다. 이 시간을 단축해서 거의 O(1)에 가깝게 할 수 있을까?

 

학습 목표

해시 테이블의 원리와 구조를 설명할 수 있다.

 

해시 테이블

• 해시 테이블(hash table)은 자료 구조 중 하나로 연결 리스트의 배열을 사용해 데이터를 저장한다.
• 각각의 데이터는 해시 함수를 통해 고유한 인덱스를 생성하고, 이를 활용해 값을 저장하거나 검색하게 된다.
• 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

쉬운 예시를 보자.

 

사진 출처 cs50

예시에서는 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 '이름의 가정 첫 글자'이다. 이 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리킨다.

 

해시 함수

1. Division Method(나눗셈 법): 입력 값을 테이블의 크기로 나누고 그 나머지를 테이블의 주소로 사용한다(주소 = 입력 값 % 테이블의 크기).
2. Digit Folding(자릿수 접기): 각 자릿수를 더해 테이블의 주소로 사용한다. 문자열을 키로 사용하는 해시 테이블에 잘 어울린다(문자를 아스키 코드로 바꿔 주소로 변환).

이 외에도 다양한 해시 함수가 있다.

 

해시 함수의 시간 복잡도

해시 함수가 이상적이라면 , 즉 각각의 키 값이 해시 함수에 의해 고유한 인덱스를 가져 바로 접근할 수 있다면 검색시간은 O(1)이 된다. 하지만 데이터 충돌이 발생한 경우 O(n)까지 증가할 수 있다.

 

 

참고 자료

[자료구조] 해시테이블(HashTable)이란?

 

[자료구조] Hash Table (해시 테이블)

---

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)