[자료구조] 해시테이블
August 06, 2022
구현
간단한 해시테이블을 구현하기 위해선, 연결리스트와 해시코드 함수만 있으면 됩니다.
다음과 같은 순서로 구현할 수 있으며, 충돌을 조심해야합니다.
- 키의 해시코드 계산하기
- 배열의 인덱스 구하기.
- 키와 값을 해당 인덱스에 저장하기.
이 때 충돌이란 서로 다른 두 개의 키가 같은 해시코드를 가리키거나 같은 인덱스를 가리키는 경우를 말합니다.
int와 long은 유한하기 때문에 발생하며 연결리스트로 구현해 대비합니다.
충돌이 자주 발생한다면 탐색시간은 O(N)이 됩니다. 충돌을 최소화시킨다면 탐색시간은 O(1)입니다.
균형 이진 탐색 트리
균형 이진 탐색 트리를 사용해 구현한다면 탐색시간이 O(logN)이 됩니다. 또한 큰 배열을 미리 할당할 필요가 없기 때문에 잠재적으로 적은 공간을 사용합니다. 그리고 키의 집합을 순차로 접근한다는 특징이 있습니다.
ArrayList와 가변 크기 배열
Java에서의 동적 가변 크기 기능이 내재되어 있는 자료구조로 ArrayList를 사용합니다.
접근시간은 O(1)이고 배열이 가득차면 배열의 크기를 두 배로 늘립니다. 크기를 늘리는건 O(n)이지만 자주 발생하지 않아 시간복잡도에 영향을 미치지 않습니다.
StringBuilder
문자열을 이어붙일 때에는 두 개의 문자열을 읽어들인 뒤 문자를 하나한 새로운 문자열에 복사해야 합니다.
O(x + 2x + ... + nx) = O(n^2)
StringBuilder가 이 문제를 해결해줍니다. 단순하게 가변크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게끔 해줍니다.
용어
충돌에 대해 이야기하기 전 간단히 용어를 정리합니다.
Bucket
테이블의 크기이며 해시함수의 결과 범위입니다.
Slot
한 버킷에 저장될 키값의 개수입니다.
Load Factor
load factor는 간단히 부하율이라고 생각하면 됩니다. 전체 버킷에서 사용중인 버킷의 비율을 말하며 100%에 가까울수록 성능이 낮습니다.
충돌
서로 다른 key값이 같은 해시값을 가질 때 충돌이 발생했다고 합니다. 해시 충돌이 일어난다면 탐색의 효율은 O(1)에서 O(N)로 증가하게 되며 해결 방법 중 두가지를 소개합니다.
1.Seperated Chaining
Java에서 사용하는 방식이며 충돌한 해시값의 슬롯을 LinkedList에 추가합니다. 메모리의 한계가 없다면 데이터를 모두 저장할 수 있다는 장점이 있습니다. 최악 시간복잡도가 O(n)이 되며 트리를 구성해 시간을 줄입니다.
2.Open Addressing
충돌 시 빈 공간을 알아서 찾아내 저장합니다. 포인터를 사용하지 않아도 돼 구현이 간편하다는 장점이 있습니다.
Linear probing
탐색을 통해 빈 slot이 나올 때 위치가 결정됩니다.
삽입 또는 검색연산은 NIL을 탐색하거나 NIL이 아닌 것을 탐색하는 선형적인 탐색을 거칩니다. 삭제연산은 slot을 빈 slot으로 만드는 대신 삭제표시로 대체합니다. 검색이 멈추는 경우를 방지하기 위함입니다.
구현이 쉽지만 한 번 충돌나면 집중적으로 충돌이 발생한다는 단점이 있습니다.
References
- 게일 라크만 맥도웰 지음. 코딩인터뷰 완전분석 프로그래밍 인사이트, 2017
- https://ryu-e.tistory.com/87
- https://github.com/WeareSoft/tech-interview/blob/master/contents/datastructure.md
