[JAVA] HashMap 에 대하여

필자는 Map 인터페이스를 구현하고자 할 때 보통 HashMap을 사용한다. 

근데 그 이유를 모르고 써서 이번에 알아보려고 한다.

 

1. 부모 클래스 - AbstractMap.java

AbstractMap은 디자인 패턴 중에 템플릿 패턴을 사용하였으며, 자바 이팩티브 저자가 말하길 SkeletonMap과 같이 Skeletonxxx 와 같은 네이밍이 더 적절하다고 생각했지만 이미 다른 곳에서 Abstract으로 썼기에 그렇게 사용했다고 한다.

 

2. 인터페이스 - Map, Clonable, Serializable

1. Map

컬렉션 인터페이스 중 하나로서 해쉬 형태의 추상클래스로서 역할을 한다.

다른 컬렉션 인터페이스와 차이점이 있다면 inner interface인 Entry가 있다는 것이다.

Entry인터페이스를 구현한 이유는 자바의 정석의 말을 빌리자면 List<K> key; List<V> value; 이런식으로 구현하여 관리하는 것보다 클래스를 구성하여 객체 단위로 다루는 것이 더 안정성도 있고 좀 더 객체지향적인 코드를 작성할 수 있기 때문이라고 한다.

 

그리고 또 재밌는 구성 중 하나가 많은 부분이 default method로 구성되어 있다는 것이다.  이렇게 구현한 이유는 람다(lambda)를 도입하면서 이에 대한 호환성을 맞추기 위해 디폴트메소드로 변환하였다고 한다.

 

2. Clonable

Object.clone() 메소드를 사용하기 위해 추가한 추상클래스다

 

3. Serializable

• 자바 시스템 내부에서 사용되는 Object 또는 Data를 외부의 자바 시스템에서도 사용할 수 있도록 byte형태로 데이터를 변환하는 기술

참고

https://nesoy.github.io/articles/2018-04/Java-Serialize

 

 

3. 내부 구조

This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes.

이 부분에서 상당히 흥미로웠다. 평상시에는 리스트 형식인 자료구조로 저장하고 있다가 일정 크기가 넘어서면 트리구조로 변하게 된다는 것이다!!

 

양이 많아지면 TreeNode 형태를 쓰는 이유

The added complexity of tree bins is worthwhile in providing worst-case O(log n) operations when keys either have distinct hashes or are orderable

시간 복잡도가 로그 형태로 유지할 수 있기 때문에 빠르다.

 

그럼 왜 적을 때는 TreeNode를 안 쓸까?

reeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.

일반 리스트 형식보다 저장공간을 많이 사용되기 때문이다.

 

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 기본 크기

    static final int MAXIMUM_CAPACITY = 1 << 30; //최대 크기

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static final int TREEIFY_THRESHOLD = 8; // 트리로 변하는 시점
 
    static final int UNTREEIFY_THRESHOLD = 6; // 리스트 형식으로 변환되는 시점

    static final int MIN_TREEIFY_CAPACITY = 64;// Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts between resizing and treeification thresholds.

 

 

1. 생성자

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

1. loadfactor는 무엇일까?

간단히 말하자면 현재 Map이 얼마까지 채워져 있는 상태인데 그에 대한 기준을 설정하는 것이다.

해쉬맵이란 것이 일정 갯수가 넘어가면 그에 대한 효율이 잘 나오지 않기 때문에 그에 대한 기준점을 설정해주는 것이다.

https://stackoverflow.com/questions/61341274/why-is-loadfactor-in-hashmap-is-set-to-0-75-by-default

why is loadFactor in HashMap is set to 0.75 by default?

그리고 0.75라는 기준점은 이 컬렉션을 만드신 대단한 개발자분들이 검토한 끝에 설정한 값이다. 

 

2. 리스트 to 트리 ( treeifyBin)

 

    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

 

1. TreeNode

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
    }

HashMap 안에 있는 static 클래스로  LinkedHashMap을 상속받아 구현되어 있다.

위와 같이 변환되어 있는 작업이 있으므로 크기가 6~8에서 계속 왔다갔다 거리면 자원을 많이 먹을 것 같다.

 

 

시간의 여유가 생긴다면 2편을 만들겠습니다.