태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
2019.01.11 16:36


[Map] HashMap vs. TreeMap vs. LinkedHashMap


big O, big o notation, entryset, hashmap vs linkedhashmap, hashmap vs treemap, Hierarchy, insertion order, key comparable, Keys, LinkedHashMap, o log n, o(1), orderedmap, Performance, red black tree structure, sortedmap, string comparable, Time Complexity, TreeMap, values, [Map] HashMap vs. TreeMap vs. LinkedHashMap


-

HashMap

    Key 는 equals 와 hashCode 가 구현되어 있어야 한다.

    O(1) time complexity



-

TreeMap ( SortedMap )

    Key 가 Red-black tree structure 를 사용하여 ordering 되어 있는 형태의 Map

    Key 가 Comparable 을 구현해야 한다. 그래야 tree 에서 비교를 할테니... ( 참고로 String 은 Comparable 하다 )

    Key 가 정렬되어 있다는 의미는 keys() 나 entrySet() 을 가지고 왔을 때, Comparable.compare 에 의한 정렬결과 순으로 collection 이 구성된다는 것이다.

    Tree 를 사용했다는 것은 Key 가 ordering 된다는 것도 있지만, Hierarchy 가 있는 형태일 때 좋다는 것.

    O( log(n) ) time complexity



-

LinkedHashMap

    HashMap 과 동일하나 Insertion order 를 보장해준다.

    keys(), values(), entrySet() 등을 통해 collection 을 가지고 왔을 때 Insertion 순으로 collection 이 구성된다는 것이다.

    입력된 순서가 있기 때문에 removeEldestEntry() 류의 메소드를 통해 LRU Cache 등을 구성하기에도 괜찮다.

    O(1) time complexity


더보기



댓글을 달아 주세요


Posted by 돼지왕왕돼지