조심해야할 점: peek이 O(1)이지 poll이 O(1)인 것이 아니다!!! add(E e): O(logn) clear: O(n) contains: O(n) offer(E e): O(logn) peek: O(1) poll: O(logn) remove: O(n + logn) size: O(1)

특징: redblack tree 기반 ceilingEntry: O(logn) ceilingKey: O(logn) clear: O(n) containsKey: O(logn) containsValue: O(logn) entrySet: O(n) firstEntry: O(logn) firstKey: O(logn) floorEntry: O(logn) floorKey: O(logn) get: O(logn) higherEntry: O(logn) higherKey: O(logn) keySet: O(n) lastEntry: O(logn) lastKey: O(logn) lowerEntry: O(logn) lowerKey: O(logn) pollFirstEntry: O(logn) pollLastEntry: O(logn) p..

add(E e): O(logn) addAll(): O(mlogn) (m이 들어오는 set element 개수) ceiling(): O(logn) clear(): O(n) contains(): O(logn) first(): O(1) floor(): O(logn) higher(): O(logn) last(): O(1) headSet: O(m + logn) (먼저 찾는데 logn 찾고 가져오는데 m) lower(E e): O(logn) pollFirst(): O(logn) pollLast(): O(logn) remove(): O(logn) size(): O(1)

특징: stack으로 사용하고자 할때 Stack보다 빠르고 queue로 사용하고자 할때 LinkedList보다 빠르다. remove나 contains를 제외하고는 모든 오퍼레이션을 상수 시간에 할 수 있다. size(): O(1) isEmpty(): O(1) getFirst(): O(1) getLast(): O(1) set(): O(n) iterator(): O(1) listIterator(): O(1) add(E e): O(1) (amortized time) add(int index, E e): O( index 오른쪽 배열 크기) (amortized time) remove(): O(n) removeFirst(): O(1) removeLast(): O(1) peek(): O(1) element(): O(..

중요: 같지 않은 key들이 같은 hashCode를 가지게 하면 해시 충돌이 일어나기 때문에 속도가 느려질 수밖에 없다. 따라서 hashCode가 겹치지 않도록 해주어야 한다. get: O(1) put: O(1) remove: O(1) size: O(1) clear: O(n) containsKey: O(1) containsValue: O(1) getOrDefault: O(1)

특징: 내부적으로는 HashMap을 사용한다. add하는 값을 key로 사용한다. 중요: HashMap은 hashCode() method를 이용해서 key에 대한 해시코드를 구한다. 해시테이블은 이 코드를 해싱 함수를 이용해 버킷에 맵핑한다. Object 객체에서 구현되어 있는 hashCode()는 참조값을 사용한다. Constructor - HashSet(int initialCapacity): 초기 수용량을 줄 수 있다. 너무 크게 하면 iteration 시간이 비효율적이게 된다. add(E e): O(1) clear(): O(n) contains(Object o): O(1) isEmpty(): O(1) iterator(): O(1) remove(Object o): O(1) size(): O(1) sp..