[Java] Collection에 대해 알아보기(4) - Map

Erin Lee·2024년 3월 7일

Map Interface

Collection Inteface의 하위 인터페이스가 아닌 컬렉션 인터페이스이다.
Key와 Value의 매핑 데이터 구조
Key는 최대 하나의 Value 값에만 매핑이 가능
Key 값으로 들어오는 데이터는 중복이 불가하고 Value 값 중복을 허용한다.
순서가 없다.

Map Interface 구조

Map Inteface는 Sorted Map 인터페이스와 HashMap 클래스가 상속받으며 SortedMap 인터페이스는 TreeMap 클래스가 상속받아 구현하고 HashMap 클래스는 LinkedHashMap이 상속하는 계층 구조이다.

HashMap

Map 인터페이스를 구현하며 HashTable 기반 구조이다.

동기화가 구현되지 않음
null 값을 허용함

HashTable

key-Value 매핑 구조로 데이터가 저장된다.
null 값이 허용되지 않음
내부적으로 동기화 구현
인덱스 기반 배열 구조
데이터의 저장 순서를 유지하지 않음

HashTable 동작 원리

HashTable은 Key-Value 형태의 데이터가 배열 구조안에 저장되며 이때 Key-Value 한 쌍을 Bucket이라고 한다.

HashTable에서 데이터를 추가하거나 검색 작업시에 해시 함수(Hash Function)가 사용된다.

Hash Function

해시 함수란 데이터의 Key값을 가지고 Hash Table 배열의 저장할 인덱스를 추출하는 함수이다.

이때 추출된 인덱스는 Key의 Hash라고 하며 해당 인덱스에 해당 Key값과 Value 값이 저장된다.

값을 조회할 때도 Key 값을 통해 추출되는 인덱스로 조회하여 해당 인덱스에 저장된 Key 값을 먼저 비교하고 동일하다면 Value 값을 추출해온다.

HashTable 동기화

HashTable 클래스는 내부 코드를 살펴보면 객체, 메서드마다 synchronized 키워드를 사용함으로써 동기화를 구현한다.

예시로 HashTable의 put() 메서드 코드를 가져왔다.

Oracle Docs는 HashMap과 HashTable이 동기화 유무와 null값 허용 차이점만 제외하면 거의 동일하다고 한다.

HashMap 동기화

Collections.synchronizedMap()

Collections.synchronizedMap(HashMap 타입의 참조변수);

HashSet vs HashMap

HashSet	HashMap
데이터 형태가 객체 자체이다. *HashSet의 내부 코드를 보면 데이터를 객체 자체로 받고 있지만 실질적으론 Map의 자료구조를 따라가 객체 자체를 Key 값으로 받고 Value 값은 Object 객체를 넣어 Key-Value 형태로 map.put() 메서드를 통해 추가된다.	데이터 형태가 Key-Value 형태이다.
중복이 허용되지 않는다.	Key는 중복이 허용되지 않지만 Value는 가능하다.

HashSet의 add() 메서드를 보면 받아오는 인자값은 HashSet 객체 하나지만 map.put() 메서드를 통해 Key-Value 형태로 데이터를 보낸다.

ConcurrentHashMap

ConcurrentHashMap은 ConcurrentMap 인터페이스를 구현하며 Map의 데이터 구조를 구현하고 내부적으로 동기화 처리가 되는 클래스이다.
HashTable의 데이터 구조 기반이다.
HashMap의 synchronizedMap() 메서드와 HashTable도 모두 동기화 처리를 해줄 수 있지만 ConcurrentHashMap은 더 특정 범위에 동기화 처리가 가능하다.

ConcurrentHashMap 동기화

HashTable은 synchronized 키워드를 사용함으로써 해당 메서드에 수행되고 있다면 다른 스레드는 절대 해당 메서드를 사용할 수 없다.

이것이 왜 문제가 될까!? 쉬운 예시로 이해해보자
방 안에 화장실을 여러 사람이 사용하게 되면 문제들이 발생할 수 있기 때문에 동기화 작업을 통해서 순서대로 화장실을 이용할 수 있도록 하여 쾌적해졌다.
하지만 출근 준비 시간 같이 바쁜 시간에는 화장실을 여러명이 같이 쓰되 한명은 세면대에서 세수를 하고 한명은 샤워기로 머리를 감게 하면 좀 더 효율적으로 서로의 출근 준비 시간을 좀 더 효율적으로 사용할 수 있게된다.

즉, 동기화 작업을 큰 범위로 묶는 것이 아닌 작은 범위로 필요한 곳에만 적용시켜서 스레드들이 수행할 수 있게 하는 것이 더 좋은 방법이 될 수 있다.

그렇게 해서 이러한 부분을 개선시킨 방법이 ConcurrentHashMap의 동기화 방법이다.

ConcurrentHashMap put() 메서드의 동기화 작업을 정리해봤다.

//ConcurrentHashMap put() 메서드를 통해 동기화 방식 정리
//https://yeoonjae.tistory.com/entry/Java-ConcurrentHashMap%EC%97%90-%EB%8C%80%ED%95%B4-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90%EC%9E%91%EC%84%B1%EC%A4%91 참고

public class ConcurrentHashMap {
    
    //1. ConcurrentHashMap에 key, value 데이터를 추가하면 putVal 메서드로 넘김
    public V put(K key, V value) {
        return putVal(key, value, false);
    }
    
    
    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        
        //key나 value가 null값이면 에러 처리 -> null을 허용하지 않음
        if (key == null || value == null) throw new NullPointerException();
        
        //HashTable과 마찬가지로 hashcode 함수를 통해 hash 생성
        int hash = spread(key.hashCode());

        int binCount = 0;

        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh; K fk; V fv;

            if (tab == null || (n = tab.length) == 0)
                tab = initTable();

            // 새로운 데이터를 삽입하기 전에 hash값을 통해 해당 bucket이 비어있는지 확인
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                //비어있으면 새로운 데이터 노드 생성하여 삽입
                if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
                    break;                   // no lock when adding to empty bin
            }

            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else if (onlyIfAbsent 
                     && fh == hash
                     && ((fk = f.key) == key || (fk != null && key.equals(fk)))
                     && (fv = f.val) != null)
                return fv;

            //만약 null이 아니라면 synchronized 블럭을 사용하여 lock을 건다.    
            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;
                                //그리고 HashTable과 같이 새로운 값으로 대치시킨다.
                                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);
                                    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;
                            }
                        }
                        else if (f instanceof ReservationNode)
                            throw new IllegalStateException("Recursive update");
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

}