TreeMap 과 HashMap
- Average 로 보면 HashMap 은 put, get 모두 O(1) 이다.
하지만 collision 이 매번 발생하는 Worst 의 경우에는, put, get 모두 O(n) 이다.
- TreeMap 는 key,val 에서 key 를 중심으로 key,val entry 가 정렬이 되며,
중복된 key 로 put 을 할 경우 당연히 덮혀 씌워진다.
내부적으로 Red-Black tree (balanced tree) 구조로 저장이 되며,
Average/Worst 모두 put,get 에 대해 O(logn) 이다.
Comments
Post a Comment