해시 테이블
-
[Data Structure] 해시 테이블알고리즘 & 자료구조 2021. 1. 25. 16:13
해시 테이블은 '연결 리스트의 배열' 이다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해보자 각 값들은 '해시 함수' 라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결리스트로 이어진다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 '연결 리스트의 배열' , 즉 '해시 테이블' 이 된다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ' 이름의 가장 첫 글자' 인 경우를 생각해보자 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며. 각 포인터는 그 알파벳을 시작하는 이름들을 저장하는 연결 리스트를 가리키게 된다. 만약 해시 함수가 이상적이라면, 각 바구..