-
효율적인 탐색을 위한 자료구조
Key를 Value에 대응
간단한 해시테이블의 구현: 연결 리스트, 해시 코드 함수를 이용
1. Key 값의 해시 코드를 계산: int 혹은 long을 반환
- Key의 값은 무한한 데 비해 int, long은 유한하기 때문에 서로 다른 두 개의 Key가 같은 해시 코드를 가리킬 수 있음
2. 해시 코드를 이용해 배열의 인덱스를 구함
- hash(key) % arrayLength 같은 방식
3. 배열의 각 index에는 Key-Values로 이루어진 연결 리스트가 존재
Key와 Value를 해당 index에 저장하고, 서로 다른 Key들이 같은 해시 코드를 가리키거나, 서로 다른 해시 코드들이 같은 index를 가리키는 경우 연결 리스트에 연결
Key에 해당하는 Value를 찾기 위한 과정
1. 주어진 Key로부터 해시 코드를 계산
2. 해시 코드를 이용해 index를 계산
3. index에 존재하는 연결 리스트에서 해당 Key에 대응하는 Value를 탐색
탐색 시간은 충돌 발생 빈도가 최악인 경우 (모든 Key에 대해 충돌이 발생하는 경우) O(n)이지만, 해시 함수는 충돌을 최소화하도록 구현하기 때문에 일반적으로 O(1)의 시간 복잡도를 보임
References