Skip to content

Latest commit

 

History

History
271 lines (218 loc) · 12.5 KB

8.md

File metadata and controls

271 lines (218 loc) · 12.5 KB
Raw

Map의 구현체들에 대해서 설명해주세요.

Map이란?

  • key-value 구조로 구성된 데이터를 저장하는 자료구조

  • 데이터 검색에 최적화되어 있다.

  • key는 중복 저장될 수 없지만, 값은 중복 저장될 수 있다.

  • 구현 클래스로는 HashMap, LinkedHashMap, Properties, TreeMap이 있다.

  • 해시맵은 Hash Table을 이용해 만들어진 Map의 구현체이며, Java Collections Framework API이다.

  • 특정 key는 해시 함수를 거쳐 bucket(저장 공간) 접근할 수 있는 index로 변환된다.

  • 해당 index에 맞는 bucket에 key-value를 저장한다.

장점

  • key가 해시 함수를 통해 bucket의 위치를 가리키는 index로 변환되므로, 값 검색에 있어 다른 ArrayList, LinkedList대비 빠른 성능을 보임.
  • key는 nullable하게 유지할 수 있다.

단점

  • bucket은 배열의 개념이므로, 일정 수준의 데이터가 쌓이면 bucket을 resizing하는 작업이 필요한데, 이때 지연시간이 소요된다.
    • 여기서의 resizing이란, bucket이 가득 차게 되면, 배열을 2배 크기로 늘리는 작업이다.
  • 데이터 저장을 위해 메모리를 많이 사용한다.

언제 사용하는가?

  • key를 이용한 데이터 저장과 접근이 필요한 경우
  • 메모리보다 성능이 우선인 경우
  • 대략적인 데이터 크기가 예상이 되는 경우
  • insert, delete 작업이 자주 일어나는 경우
import java.util.HashMap;

public class Sample {
    HashMap<Key, Value> hashMap = new HashMap<>();
    // 입력
    hashMap.put("cafe", "카페");
    
    // 조회
    String value = hashMap.get("cafe"); // 카페
    
    // 삭제
    hashMap.remove("카페");

    // key 값을 출력
    for (String key : hashMap.keySet()) {
        System.out.println(key);
    }
    
    // value 값을 출력
    for (String value : hashMap.values()) {
        System.out.println(value);
    }
}

TreeMap

  • 기본적으로 Red-black Tree를 이용해 만들어졌다.
  • HashMap과 달리 key값을 기준으로 오름차순으로 정렬된 key를 반환받을 수 있다.
    • 문자의 경우에는 unicode값을 정렬 기준으로 한다.
  • 정렬된 데이터를 조회하는 범위 검색의 경우에는 성능이 좋다.
  • HashMap 대비 필요한 메모리 양만 사용하므로, 상대적으로 메모리를 절약할 수 있다.

단점

  • 삽입이나 삭제 시, Node를 재배치하는 연산이 발생할 수 있다.
  • Map 구현체 중 검색 속도가 가장 느리다.

언제 사용하는가?

  • 데이터의 개수가 예측되지 않는 경우
  • insert, delete가 적을 때
  • 정렬된 key가 필요한 경우

LinkedHashMap

  • HashMap을 상속하여 만든 클래스이다.
  • 차이점은 Node객체를 Entry 객체로 감싸서, 입력된 키의 순서를 보존한다는 점이다.
  • HashMap과 달리 순서를 linked-list를 이용해서 관리하므로, 더 많은 메모리를 필요로 한다.
  • key나 값의 저장된 순서가 중요한 경우 유용하다.
import java.util.LinkedHashMap;

public class Example {
    LinkedHashMap<String, String> map = new LinkedHashMap<>();

    // key 값을 출력
    for (String key : map.keySet()) {
        System.out.println(key);
    }

    // value 값을 출력
    for (String value : map.values()) {
        System.out.println(value);
    }
}

// 저장된 순서대로 key, value값이 출력된다.

image

  • 구현된 로직을 살펴보면 HashMap과 달리 accessOrder라는 값이 있다.
  • accessOrder는 Entry에 access하는 mode를 나타낸다. true일 경우 입력된 순서 중에 access빈도 낮은 것들부터 접근하고, false일 경우 입력된 순서로 Entry에 접근한다.

Hashtable

  • HashMap과 같은 동작을 하는 클래스이다.
  • 기존 코드와의 호환성을 위해 남겨진 것으로, HashMap을 사용하는 것이 권장된다.
  • 비유하자면 ArrayList - Vector의 관계와 유사하다.
  • 장점으로, thread-safe 하다. 따라서, multi-thread 환경에서 데이터 무결성을 보장한다.

어떻게 thread-safe하게 유지하는지?

  • Hashtable의 경우 Map 전체에 @synchronized 어노테이션을 이용해 lock을 걸어 운용한다. 이로 인해 성능상의 오버헤드가 많이 발생하게 된다.
  • 그러나 ConcurrentHashMap의 경우, 버킷 단위로 동기화를 진행하기 때문에 다른 bucket을 이용하는 쓰레드 간에는 별도의 lock이 필요 없다.

ConcurrentHashMap이란?

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {

    public V get(Object key) {}

    public boolean containsKey(Object key) { }

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) {
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }
}

ConcurrentHashMap이 구현된 코드이다. 우선 get 메서드에서는 synchronized 키워드가 없다. put 메서드의 일부만 synchronized가 존재한다. 해당 코드에서 ConcurrentHashMap에서 read는 여러 쓰레드가 lock 없이 사용 가능하고, write의 경우에는 특정 bucket단위의 lock을 사용한다는 것을 확인할 수 있다.

해시 함수란?

  • 임의 길이의 메세지를 입력받아 고정 길이의 해시값을 출력하는 함수이다. 같은 입력에 대해서는 항상 같은 출력이 나오게 된다.

해시 충돌이란

  • 서로 다른 값을 해시함수에 통과시켜 얻어낸 해시값이 동일한 경우를 말한다.
  • hashMap의 경우에는 hashCode()함수의 반환값을 해시 bucket의 index로 사용하는데, 이 반환값이 int이다.
  • int는 최대 2^32 크기의 정수이므로, 입력받는 객체 수가 2^32보다 많으면 무조건 해시 값이 겹쳐 해시 충돌이 발생하게 된다.
  • 해시함수를 이용한 자료구조에서는 2^32크기의 배열을 유지하면 메모리 효율이 떨어지므로, 실제 해시함수의 표현 정수 범위(N)보다 작은 크기(M)의 배열을 쓴다.
  • 따라서 해시함수를 사용하는 associative array 구현체에서는, int index = X.hashCode() % M; 와 같이 해시 함수의 결과값을 M으로 나눈 나머지를 사용한다.

해시 충돌을 해결하는 방법?

해시 충돌이란, 결국 해시함수를 잘 설계하여도 메모리를 효율적으로 사용하기 위해서 불가피한 문제라는 결론에 이르게 된다. 이를 어떻게 해결할 수 있을까? 크게 2가지 방법이 있다.

Open Addressing(개방 주소법)

  • 해시 충돌 해결을 위해 추가적인 메모리를 사용하지않고 빈 bucket을 이용하는 방법이다.

  • Linear Probing : 현재의 버킷 index로부터 고정 step만큼 이동하며 빈 버킷에 데이터를 저장하는 방식

  • Quadratic Probing : step을 1씩 늘린 후, 제곱하여 저장하는 방식이다.(step + 1) ^ 2

    • 예를 들어, 처음 충돌이 발생하면 1^2, 그다음은 2^2, 3^2, 4^2만큼 옮기는 방식이다.

  • Double Hashing Probing : 해시된 값을 한번 더 해시하여 해시의 규칙성을 없애는 방식이다.

Seperate Chaining(분리 연결법)

  • 동일 버킷으로 접근시 Linked List 형식의 추가 메모리를 사용하여 데이터를 연결하여 관리한다.
  • 단 chaining된 데이터의 수가 많아지면, 캐시 효율성이 감소하고, 이에 따라 값 조회가 최대 O(N)타임의 시간복잡도를 보일 수 있다.

Java의 hashMap은 분리 연결법을 사용한다.

  • 삭제 효율성이 우수하다.

    • Open Addressing의 경우 데이터를 삭제할 때 인덱스를 탐색해야 하는데, 여러 단계로 Probing이 이루어진 경우 삭제 효율성이 떨어진다.
    • hashMap은 삭제 작업이 빈번하게 일어난다.

  • 데이터가 많을 때는 Seperate Chaining이 빠르다.

    • Open Addressing의 경우 해시 버킷이 일정 수준 이상 찼다면, 해시 충돌이 더욱 빈번해진다.
    • Seperate Chaining의 경우 해시충돌이 발생하지 않게 잘 조정한다면 효율성을 유지할 수 있기 때문이다.

  • 만약 해시함수 값이 균등 분포 상태라고 한다면, get() 메서드 호출에 대한 기댓값은 E(N/M)이다.

  • 그러나 Java8에서는 데이터의 개수가 많아지면 Seperate Chaining에서 linked-list 대신 트리를 사용하므로 기댓값이 E(log N/M)이 된다.

보조 해시 함수란?

index = X.hashCode() % M 에서 M값이 소수일 때 index가 균등 분포에 가장 가까워질 수 있다. 그러나 앞서 설명한 버킷의 개수(M)은 크기가 2배로 늘어나는 resizing 과정을 거치므로, M이 2의 배수가 된다. 따라서 별도의 보조 해시 함수가 필요하다.

  • 보조 해시 함수의 목적은 key의 해시값을 변형하여 충돌 가능성을 줄이는 것이다.

Q & A

어떻게 hashMap은 key값을 null로 유지할 수 있는가?

// hash() 메서드
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 실제 hashMap의 hash() 메서드를 살펴보면, key가 null인 경우 결과값으로 0을 반환한다. 0 또한 하나의 index로 사용 가능하므로, hashMap의 key는 nullable합니다.

hashMap의 key를 null로 유지하면 장점이 있는가?

  • 장점이라기 보다는, null값도 하나의 key로써 사용할 수 있다는 것을 알고 계시면 될 것 같다.

References