🌳

HashMap & TreeMap

HashMap vs Hashtable

unsynchronized 되있다는 것과 null을 key와 value로 가질 수 있다는 점만 빼면 Hashtable 과 같다.

xxx 내부 구현에 차이 있음

Hashtable is now considered obsolete

synchronization을 제공하고 싶으면 Hashtable 대신 concurrentHashMap을 사용하자

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

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배)

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

rehash

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

HashMap의 기본 구현은 synchronized 되어 있지 않음

Collections.synchronizedMap 메서드로 래핑 하여 synchronized 기능을 제공할 수 있음
→ 대신 ConcurrentHashMap이 더 좋은 선택임

fail-fast한 iterator를 제공함

HashMap의 Fields

TreeMap은

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를 제공해야함

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

💡

HashMap, HashSet은 HashTable의 구현을 바탕으로 함

→ 내부적으로 equals 메소드를 기반으로함 → null을 key로 가질 수 있음 (항상 null 체크를 함)

반면 TreeMap, TreeSet은 RbTree의 구현을 바탕으로함

→ 내부적으로 compareTo 메소드를 기반으로함 → null을 key로 가질 수 없음


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);
        }
    }
}

리플렉션을 사용해 hashMap의 capacity를 확인해보자!


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

실행 결과


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;
	....

}


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);
    }
}