[JAVA] Map 정리(HashMap , TreeMap , Red-Black Tree )

 

컬렉션 프레임웍의 구성요소 Map 인터페이스에서 

HashMap 의 내부코드를 간단히 살펴 보고

HashMap과 TreeMap의 성능 차이

TreeMap 의 Red-Black Tree를 알아보자.

 

 

Map 인터페이스

HashMap

HashMap 과 TreeMap

TreeMap의 Red-Black Tree

 

 

 

 

Map 인터페이스 

 

- 컬렉션 프레임웍의 멤버이다. 

- 키(Key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합 

- key는 문자열, 정수형, Object 객체형 등의 다른 데이터 형이 될 수 있고, Key 값을 사용자가 직접 입력한다. 

- 순서는 유지되지 않으며, 키는 중복을 허용하지 않고, 값은 중복을 허용한다.  예) 우편번호, 지역번호(전화번호)
- 구현 클래스 :

 

 

• HashMap, Hashtable 
• TreeMap
• LinkedHashMap
• ...

 

 

HashMap 과 Hashtable

 - 둘이 거의 유사하다.

 - 보통 매개변수가 없는 생성자를 사용하지만 데이터가 많은 경우 초기에 크게 지정하는 것을 권장한다. 

- Hashtable 과 HashMap의 관계(1) 는 Vector 와 ArrayList의 관계와 같아서 Hashtable 보다는 HashMap의 사용을 권한다. 

  해싱(Hasing) 을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다. 

* (1) Vectors나 Hashtable 과 같은 기존(구버전)의 컬렉션 클래스들은 호환을 위해 설계를 변경해 두어 남겨 두었다.  

 

- 해싱 : 해시함수(hash function) 을 이용해서 데이터를 해시테이블(hash table) 에 저장하고 검색하는 기법 

- 컬렉션 클래스 : hashset, hashMap, hashtable

 

HashMap  구조 

1. 해시 테이블에 해시값에 해당하는 노드를 연결한다.

2. Linked List의 모습을 가지고 있다.

 

https://sabarada.tistory.com/57

 

Node.class 

• Map의  내부 인터페이스 Entry 를 상속 받는다. 

  /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

 

- Map.Entry 인터페이스의 메서드

 

메서드	설명
boolean equals(Object o)	동일한 Entry인지 비교한다.
Object getKey()	Entry의 Key 객체를 반환한다.
Object getValue()	Entry의 value 객체를 반환한다.
int hashCode()	Entry 의 해시코드를 반환한다.
Object setValue(Object value)	Entry 의 value 객체를 지정된 객체로 바꾼다.

 

 

Put()

아래와 같은 코드처럼 HashMap의 put() 메서드가 실행되는 내부 코드를 살펴보면,

우선 key 값을 이용하여 hash() 코드를 생성하고 putVal() 함수를 호출하는 것을 확인 할 수 있다.

 

•  h = key.hashCode = Object 클래스의 hashcode 메서드
•  >>> 16 오른쪽으로 16번 unsigned right shift 
•  ^  = XOR 연산 

 

putVal(int hash, K key, V value, boolean onlyfAbsent, boolean evict)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

 

putVal() 내부 코드의 부분을 살펴 보면

 

처음 Node로 구성된 배열의 테이블 참조변수가 Null 값일 경우 resize() 함수를 통해 생성하고 

생성된 테이블의 인덱스에 값(Node) 가 존재하지 않을 경우 newNode를 통해서 값을 넣어준다. 

 

* new Node() 함수에서 Node 객체가 생성된다

 // Create a regular (non-tree) node
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

 

이처럼 HashMap 은 해시된 값의 인덱스를 가지는 배열에 Node 의 값을 연결하여 데이터를 관리 하기 때문에 

더 빠른 연산속도를 가질 수 있다. 

 

 

TreeMap 

-  자료구조의 이진 검색 트리를 사용해 멤버 객체를 관리한다. 

- 정렬 순서는 숫자 >  알파벳 대분자 > 알파벳 소문자 > 한글 순서

- 중위 순회 : 왼쪽 자식 노드 -> 부모노드 -> 오른쪽 자식 노드 

 - 검색과 정렬에 적합한 컬렉션 클래스이다. 

 - 검색과 정렬 외에는 HashMap이 TreeMap 보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 

 - 아래의 코드와 출력결과를 통해 HashMap 이 TreeMap보다 더 빠른 성능을 가지고 있음을 알 수 있다.

 

public class TreeMapTest {
    public static void main(String[] args) {
        Map<Integer, String> treeMap = new TreeMap<>();
        Map<Integer, String> hashMap = new HashMap<>();

        System.out.println("=============");
        System.out.println("hashMap put :" + add(hashMap));
        System.out.println("hashMap get :" + access(hashMap));

        System.out.println("=============");
        System.out.println("treeMap put :" + add(treeMap));
        System.out.println("treeMap get :" + access(treeMap));



    }
    public static long add(Map map) {
        long start = System.currentTimeMillis();
        for(int i=0; i<100000; i++) map.put(i, "value");
        long end = System.currentTimeMillis();
        return end - start;
    }


    public static long access(Map map) {
        long start = System.currentTimeMillis();
        for(int i=0; i<100000; i++) map.get(i);
        long end = System.currentTimeMillis();
        return end - start;
    }
}

 

 

 

 

 

 

 

 

 - 이 둘의 가장 큰 차이점은 TreeMap 의 경우 Key의 값이 정렬 된다는 것이다. 

package chapter11;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapTest2 {
    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        Map<Integer, String> map2 = new TreeMap<>();
        putItem(map);
        putItem(map2);
    }

    public static void putItem(Map map) {
        map.put(1, "value");
        map.put(9, "value");
        map.put(3, "value");
        map.put(7, "value");
        map.put(8, "value");
        map.put(23, "value");
        map.put(33333, "value");
        map.put(63434, "value");
        map.put(52, "value");
        System.out.println(map.getClass().getName() + " : " + map.keySet().toString());
    }
}

 

 

 

 

- 이처럼 단위 검색이나 정렬이 필요한 경우에는 TreeMap 을 사용한다. 

- TreeMap의 logN의 복잡도를 보장하기도 한다.

 

출처 : https://zeddios.tistory.com/237

 

 

Red-Black Tree

 

기본 이진탐색은 값이 한쪽으로 몰릴 경우 최악의 최악의 경우 O(트리의 높이=h)만큼의 탐색시간을 가질 수 있다.

TreeMap의 경우에는 balanced binary search tree 이기 때문에 항상 logN 의 출력 결과를 보장한다. 

 

Red-Black Tree 는 아래에서 자세히 설명 되었다. 

 

https://zeddios.tistory.com/237

알고리즘 ) Red-Black Tree

 

 

 

 

참고 : 

http://onlineqa.com/java-core-collections-explained-java-collections-framework/

https://zeddios.tistory.com/237

https://aroundck.tistory.com/5945

https://sabarada.tistory.com/57?category=826240 

[자료구조] 코드로 알아보는 java의 Hashmap