해시 테이블 시간복잡도

자료구조	접근	탐색	삽입	삭제
해시 테이블	O(1)	O(1)	O(1)	O(1)
HashMap	해시테이블과 같지 않을까?
HashSet

 

해시테이블 - 삽입, 삭제 : O(1)

key의 해시값을 배열의 크기로 나눠 index를 얻고

key.hashCode() % SIZE;

해당index의 LinkedList에 삽입,삭제

 

LinkedList의 삽입,삭제는 O(1) 이므로

 

해시테이블 - 접근 : O(1)

key의 해시값으로 index얻고, 해당 index의 LinkedList에서 접근

 

LinkedList의 접근은 O(n) 이지만

원소가 배열의 각 인덱스마다 LinkedList에 흩어져 있으므로 O(1)

 

실제로 (배열의 크기)와 (원소 개수)를 가지고 적절히 비교해서

배열의 크기를 늘려주는 작업을 해준다.

if (size >= table.size() * LOAD_FACTOR) {
	resize(); // 배열의 크기를 늘려줌
}

 

이를 통해 각index의 LinkedList의 크기는 전체 원소 개수에 비하면 매우 작아진다.