자료 구조 | 해시 테이블

연결 리스트나 트리에서 값을 검색할 땐 O(n) 또는 O(log n)의 시간이 걸린다. 이 시간을 단축해서 거의 O(1)에 가깝게 할 수 있을까? 학습 목표 해시 테이블의 원리와 구조를 설명할 수 있다. 해시 테이블 해시 테이블(hash table)은 자료 구조 중 하나로 연결 리스트의 배열을 사용해 데이터를 저장한다. 각각의 데이터는 해시 함수를 통해 고유한 인덱스를 생성하고, 이를 활용해 값을 저장하거나 검색하게 된다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 쉬운 예시를 보자. 예시에서는 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 '이름의 가정 첫 글자'이다. 이 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름..

2021.03.01