[자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점

 

[자료구조 Java] 해시 테이블 (1) - 해시 테이블 및 해시 충돌(Hash Collision)

[자료구조 Java] 해시 테이블 (2) - 체이닝(Chaining), 선형 조사법(Linear Probing), 이차 조사법(Quadratic Probing), 이중 해싱법(Double Hasing)

[자료구조 Java] 해시 테이블 (3) - 시간 복잡도, 장점과 단점

[Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까?

 

해시 테이블의 평균, 최악의 case에서 갖는 시간 복잡도를 알아보고 이를 바탕으로 해시 테이블이 갖는 장점과 단점에 대해 알아보자

 

시간 복잡도

 

빅오 표기법	평균	최악
탐색	O(1)	O(N)
삽입	O(1)	O(N)
삭제	O(1)	O(N)

 

해시 테이블은 탐색에 특화 된 자료구조로 탐색 시 평균 O(1)의 시간 복잡도를 갖는다. 이는 배열에서 index를 아는 상태에서의 접근하는 것과 동일한 시간 복잡도를 보인다. 하지만 주의해야 할 것은 평균 O(1)이라는 시간 복잡도는 해시 충돌이 일어나지 않는 이상적인 상황을 고려한 것이다. 해시 충돌이 일어날 수록 시간 복잡도는 최악인 O(N)에 수렴한다. 만약 수정된 Chaining방식을 이용하여 해시 충돌된 엔트리들을 Red-Black Tree로 연결한다면 최악의 경우라도 O(logN) (밑은 2)의 시간복잡도를 갖게 된다.

 

해시 테이블 장점과 단점

 

장점

• 해시 충돌이 없는 상태에서 배열, 리스트 같은 선형적인 구조는 물론 트리와 구조보다 빠른 탐색
• 해시를 사용하기에 해시 값을 알아도 key를 예측하기 어려움

단점

• 해시 충돌 발생 시 탐색이 시간 복잡도 O(N)에 점점 수렴함
• 정렬이나 순차적인 메모리 저장이 필요한 경우 적합하지 않음
• 해시 함수의 성능에 따라 해시 테이블 전체 성능이 크게 영향을 받는다.

 

 

다음: [Java] 자바 Collection Framework의 HashMap은 어떤 해시 충돌 알고리즘을 사용할까?