HashMap & TreeMap

• 일정한 순서를 보장하지 않음

• Hash Function이 잘 구현 되어있다면
• basic operations (get and put)에대한 O(1) performance를 제공함

• Iteration의 시간복잡도는 O(N + C)임
• N - 전체 원소 수
• C - capacity

• capacity - bucket의 용량 (default - 16)

• load factor - bucket을 늘리는 시점을 결정하는 비율 (default - 0.75)
• 즉, HashMap을 default 로 생성한다면 12개의 bucket이 채워진 시점에 capacity를 늘림 (약 2배)

package collection;

import java.lang.reflect.Field;
import java.util.HashMap;
import java.util.Map;

public class MapStudy {

    static class MyKey {

        int key;

        public MyKey(int key) {
            this.key = key;
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof MyKey)) {
                return false;
            }
            return key == ((MyKey) obj).key;
        }

        @Override
        public int hashCode() {
            return key;
        }
    }


    public static void main(String[] args) throws Exception {

        Map<MyKey, String> hashMap = new HashMap<>();
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);

        hashMap.put(new MyKey(1), "val1");
        hashMap.put(new MyKey(1), "val2");

        for (int i = 0; i < 16; i++) {
            hashMap.put(new MyKey(i), "val" + i);
            Object[] table = (Object[])tableField.get(hashMap);
            System.out.println("put: " + i + " capacity : " + table.length);
        }
    }
}

 

put: 0 capacity : 16
put: 1 capacity : 16
put: 2 capacity : 16
put: 3 capacity : 16
put: 4 capacity : 16
put: 5 capacity : 16
put: 6 capacity : 16
put: 7 capacity : 16
put: 8 capacity : 16
put: 9 capacity : 16
put: 10 capacity : 16
put: 11 capacity : 16
put: 12 capacity : 32
put: 13 capacity : 32
put: 14 capacity : 32
put: 15 capacity : 32

Process finished with exit code 0

 

• load faction의 threshold를 넘어가는 시점에 rehash가 발생한다.

• rehash
• 내부 테이블의 구조를 새로운 capacity로 재 설정하는 일
• 모든 원소에 대한 hashcode( )%capacity를 다시 계산하고 공간 배치를 다시함

• HashMap의 기본 구현은 synchronized 되어 있지 않음
• Collections.synchronizedMap 메서드로 래핑 하여 synchronized 기능을 제공할 수 있음
• → 대신 ConcurrentHashMap이 더 좋은 선택임
 

• fail-fast한 iterator를 제공함

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

	....
/* ---------------- Fields -------------- */
transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

transient int size;

transient int modCount;

int threshold;

final float loadFactor;
	....

}

• Red-Black tree 기반의 NavigableMap (SortedMap) 구현체임

• key의 natural order (Comparable) 혹은 생성자로 부터 전달받은 Comparator에 의해 정렬됨

• containsKey, get, put and remove 연산에 대한 log(n)의 시간 복잡도를 제공함

• 역시 synchronized 되어 있지 않으며 동기화 기능을 사용하고 싶다면
• Collections.synchronizedSortedMap으로 래핑하여야함

• 역시 fail-fast한 iterator 제공함

• Comparator를 가져야함
• Key가 Comparable을 구현하였다면 그것을 사용함
• 그렇지 않다면 생성자에 Key의 comparator를 제공해야함

package collection.map;

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapStudy {

    public static void main(String[] args) {


        Comparator<MyKey> myKeyComparator = (a,b) -> (a.key-b.key);

        TreeMap<MyKey, String> treeMap = new TreeMap<>(myKeyComparator);

        treeMap.put(new MyKey(1), "val 1");
        treeMap.put(new MyKey(2), "val 2");

        treeMap.entrySet().forEach(System.out::println);
    }
}

 
• 때문에 null을 key 값으로 활용할 수 없음 (value 는 가능)