[Java] Collection - Map

Map이란 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스들을 구현하는데 사용되는 List형태의 조상

Map 인터페이스와 이 구현체들은 Collection에 속하지만 Map은 Collection이 아니다.

왜 그럴까? '엘리먼트들의 그룹' Collection 인터페이스의 기본 개념과 맞지 않는다.

Map은 java.util 패키지의 Map이라는 이름의 인터페이스로 선언되어 있고, 구현해 놓은 클래스들도 많이 있다

Map 인터페이스에 선언되어 있는 메소드

리턴 타입	메소드 이름 및 매개 변수	설명
V	put(L key, V value)	첫 번째 매개 변수인 키를 갖는, 두 번째 매개변수인 값을 갖는 데이터를 저장한다.
void	putAll(Map<? extends K, ? extends V> m)	매개 변수로 넘어온 Map의 모든 데이터를 저장한다.
V	get(Object Key)	매개 변수로 넘어온 키에 해당하는 값을 넘겨준다.
V	remove(Object Key)	매개 변수로 넘어온 키에 해당하는 값을 넘겨주며, 해당 키와 값은 Map에서 삭제한다.
Set<K>	KeySet()	키의 목록을 Set 타입으로 리턴한다.
Collection<V>	values()	값의 목록을 Cllection 타입으로 리턴한다.
Set<Map, Entru<K,V>>	entrySet()	Map 안에 Entry라는 타입의 Set을 리턴한다.
int	size()	Map의 크기를 리턴한다.
void	clear()	Map의 내용을 지운다.
boolean	isEmpty()	컬렉션이 비었는지 확인
boolean	containsKey(Object key)	해당 키의 지정 여부 확인
boolean	containsValue(Object value)	해당 값의 지정 여부 확인

Map의 "키" 목록은 ketSet() 메소드를 사용하면 Set 타입의 데이터를 얻을 수 잇고, "값" 목록은 values() 메소드를 통하여 Collection 타입의 데이터를 얻을 수 있다.

Map을 구현한 주요 클래스

Map 인터페이스를 구현한 클래스들은 매우 다양하고 많다. 그 중에서 HashMap, TreeMap, LinkedHashMap 등이 가장 유명하고, Hashtable라는클래스도 있다. Hashtable라는 클래스는 Map 인터페이스를 구현하긴 했지만 일반적인 Map 인터페이스를 구현한 클래스들과는 다르다. 이 두 종류의 다른 점을 간단하게 정리하자면..

 

- Map은 컬렉션 뷰를 사용하지만, Hashtable은 Enumeration 객체를 통해서 데이터를 처리한다.

- Map은 키, 값, 키-값 쌍으로 데이터를 순환하여 처리할 수 있지만, Hashtable은 이 중에서 키-값 쌍으로 데이터를 순환하여 처리할 수 있다.

- Map은 리터레이션을 처리하는 도중에 데어터를 삭제하는 안전한 방법을 제공하지만, Hashtable는 그러한 기능을 제공하지 않는다.

 

그런데 HashMap 클래스와 Hashtable 클래스는 다음과 같은 차이가 있다.

기능	HashMap	Hashtable
키나 값에 null 저장 가능 여부	가능	불가능
여러 쓰레드 안전 여부	불가능	가능

중요한 것은 Hashtable을 제외한 Map으로 끝나는 클래스들을 여러 쓰레드에서 동시에 접근하여 처리할 필요가 있을 때에는 다음과 같이 선언하여 사용해야만 한다.

Map m = Collection.synchronizeMap(new HashMap(...));

HashMap이란?

HashMap이란 Map인터페이스의 한종류로써 Key와 Value 값으로 데이터를 저장하는 형태를 가지고 있다.

hashMap 클래스는 다음과 같은 상속 관계를 가진다.

java.lang.Object - java.util.AbstractMap<K,V> - java.util.HashMap<K,V>

구현된 인터페이스는

Hashmap 클래스의 객체를 생성하기 위한 생성자

생성자	설명
HashMap()	16개의 저장 공간을 갖는 HashMap 객체를 생성한다.
HashMap(int initialCapacity)	매개 변수만큼의 저장 공간을 갖는 HashMap 객체를 생성한다.
HashMap(int initialCapacity, float loadFactor)	첫 매개 변수의 저장 공간을 갖고, 두 번째 매개 변수의 로드팩터를 갖는 HashMap 객체를 생성한다.
HashMap(Map<? extends K, ? extends V> m)	매개 변수로 넘어온 Map을 구현한 객체에 있는 데이터를 갖는 HashMap 객체를 생성한다.

대부분 HashMap 객체를 생성할 때에는 매개 변수가 없는 생성자를 이용하지만, HashMap에 담을 데이터의 개수가 많은 경우에는 초기 크기를 지정해 주는 것을 권장한다.

 

왜 지정해주는 것을 권장할까?

해시 버킷 개수의 기본 값은 16이고, 데이터의 개수는 임계점의 이를 때마다 해시 버킷의 개수의 크기를 두 배씩 증가시킨다. 버킷의 최대 개수는 2^30이다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있으므로, 해당 HashMap 객체에 저장될 데이터의 개수가 어느 정도인지 예측 가능한 경우에는 이를 생성자의 인자로 지정하면 불필요하게 Separate Chaining을 재구성하지 않게 할 수 있다.

capacity == bucket의 크기
한 HasgMap 객체에 저장된 데이터의 수 == capacity * load_factor
load_factor == 저장된 데이터의 수 / capacity , 버킷이 얼마나 찼을 때 resize를 하는 것이 좋은지에 관한 값

hashMap의 키를 클래스로 사용할때 

HashMap의 키는 기본 자료형과 참조 자료형 모두가 될 수 있다. 그래서 보통 int나 long과 같은 숫자나 String 클래스를 키로 많이 사용한다. 하지만 어떤 클래스를 만들어 그 클래스를 키로 사용할 때에는 Object 클래스의 hashCode() 메소드와 equals() 메소드를 잘 구현해 놓아야만 한다.

 

HashMap에 객체가 들어가면 hashCode() 메소드의 결과 값에 따른 버켓이라는 목록형태의 바구니가 만들어진다. 만약 서로 다른키가 저장되었는데, hashCode() 메소도의 결과가 동일하다면 이 버켓에 여러 개의 값이 들어 갈 수 있다. 따라서 get() 메소드의 결과가 동일하다면, 이 버켓에 여러 개의 값이 들어갈 수 있다. 따라서 get 메소드가 호출되면 gashCode()의 결과를 확인하고, 버켓에 들어간 목록에 데이터가 여러 개일 경우 equals() 메소드를 호출하여 동일한 값을 찾게 된다. 따라서, 키가 되는 객체를 직접 작성할 때에는 개발툴에서 제공하는 hashCode()와 equals()를 자동 생성해주는 기능을 사용하여 해당 메소드를 꼭 구현해 놓아야 한다.

 

HashMap 성능

HashMap은 초기 용량 16, 로드 팩터는 0.75가 디폴트 값이다. 즉, 이 2개의 값에 따라 성능이 좌우된다.

 

용량을 설정하는 기준

• 초기용량을 작게 설정한다면 공간 비용은 절감되지만 재할당빈도는 증가한다. (재할당은 비용이 매우 많이 드는 과정)
• 초기용량을 높게 설정하면 재할당 하는 과정은 별로일어나지 않겠지만 너무 과하게 설정하면 메모리 낭비를 할 수도 있다.

HashTable이란? 

해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소로 삼아 데이터를 key와 함께 저장하는 자료구조이다. 해시테이블은 Map 인터페이스를 구현하고 있다.

• 데이터를 해쉬 테이블에 담는 클래스, 내부에서 관리하는 해쉬 테이블 객체가 동기화 되어있으므로, 동기화가 필요한 부분에서는 이 클래스를 이용하자.
• 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

예를 들어 우리가 (Key, Value)가 ("John Smith", "521-1234")인 데이터를 크기가 16인 해시 테이블에 저장한다고 하자. 그러면 먼저 index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 array[index] = "521-1234" 로 전화번호를 저장하게 된다. <- Division Method ( 주소 = 입력 값 % 테이블의 크기)

어라훈 구조로 데이터를 저장하면 Key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를 저장/삭제/조회할 수 있다. 해시테이블의 평균 시간복잡도는 O(1)이다. 만약 크기가 16에 이르면 해시 버킷 개수의 크기를 2배 증가시킨다,

 

그런데 만약 해쉬값이 충돌이 일어나는 경우는 어떻게 될까? (해시 충돌)

 

만약 "John Smith"를 해시 함수를 돌려 나온 값과 "Mang Kyu"를 해시 함수를 돌려 나온 값이 동일하다면 어떻게 해야 할까? 해시 테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

Open Addressing

Separate Chaining

• 위의 그림에서 "John Smith"의 index가 152이고 하필 "Sandra Dee"의 index도 152로써 동일하다면 Open Addressing에서는 연속된 다른 bucket에 순차적으로 입력하는데 Separate Chaining에서는 index로부터 리스트의 형태로 추가한다. 
• Open Addressing에서 "Ted Baker"는 index가 153으로 원래는 충돌이 없었는데 "Sandra Dee"가 "John Smith"와 충돌나는 바람에 index를 침범하였다. 그래서 결국 "Ted Baker"도 충돌이 나게 된다. 
• 둘다 worst case에서 O(M)이다. Open Addressing은 기존 공간을 활용하므로 캐시 효율이 좋고 버켓 크기에 비해 데이터 개수가 충분히 적다면 Separate Chaining보다 효율적이다. 
• 반면 키-값 개수가 늘어나 충돌이 많아지면 일반적으로 Open Addressing이 Separate Chaining보다 느리다. Open Addressing이 캐시 효율이 좋지만 밀도가 높아 충돌 가능성을 더 높이기 때문이다. 또 Separate Chaining은 보조해시함수를 사용하면 충돌이 잘 발생하지 않도록 '조절'할 수 있다. 
• Java HashMap의 경우 Separate Chaining 방식을 사용하는데 위의 이유도 있고 추가로 Open Addressing이 원소의 삭제에 대해 효율적으로 구현하기 어렵다는 이유도 있다. HashMap은 remove() 호출이 빈번할 수 있기 때문이다. 

간단히 정리하자면,

Separate Chaining

• 충돌이 발생하면 주어진 공간외에 새로운 공간을 할당하여 해결한다 ( LinkedList -> Tree)
• 이런 특성으로 Open Hashing(개방 해싱)이라고도 부른다.

Open Addressing

• 주어진 해시테이블에서 정해진 규칙에 따라 다음 버킷을 찾아 저장하는 방법.
• 정해진 해시테이블내에서만 저장되는 특징이 있다 해서 Closed Hasing(폐쇄 해싱)이라고도 부른다.

 

Java8 에서의  Separate Chaining의 성능 개선

• Java 8에서 Separate Chaining를 구현할 때 리스트 대신 트리를 사용한다. 정확하게는 개수가 8개까지는 리스트를 사용하고 그것을 넘은 경우 트리로 전환한다. (다시 6개 보다 작아지면 리스트로 전환)
• 이때 사용하는 트리는 Red-Black Tree인데 TreeMap의 구현과 거의 동일하다.

6개일 때는 링크드리스트, 8개일 때는 Tree인데 그럼 7은 어디갔을까?

만약 기준이 6과 7이라면 링크드 리스트에서 트리로 변경해야 한다. 그러다 바로 하나의 값이 삭제되면 다시 트리에서 링크드 리스트로 변경해야 한다. 각각 자료구조로 넘어가는 기준이 1이라면 Switching 비용이 너무 많이 필요하게 되는 것이다. 그래서 2라는 여유를 남겨두고 기준을 잡은 것이다. 따라서 데이터의 수가 6 -> 7로 증가했을 때는 링크드리스트, 8 -> 7로 감소했을 때는 트리리의 자료구조를 취하고 있을 것이다.

 

즉, 간단히 말해서 링크드 리스트와 트리의 기준을 6과 8로 잡은 것은 변경하는데 소요되는 비용을 줄이기 위함이다.

 

보조 해시 함수

• index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M 값이 소수가 아니기 때문에 index 값의 분포가 가급적 균등하도록 보조 해시 함수를 이용한다.
• 즉, 보조 해시 함수는 키의 해시값을 변형하여 해시 충돌 가능성을 줄이는 역할을 한다. 
• Java 8에서의 보조 해시 함수이다. 

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 비교적 단순한데 Java 7까지는 이보다 복잡했다. 그 이유는 Java 8에서 충돌시 chain으로 리스트대신 tree를 사용하기 때문에 성능문제가 완화된 것도 있고, 최근의 해시 함수들이 균등분포가 잘되는 경향이 많아서 그렇다. (후자의 이유가 더 크다)

HashMap, HashTable 해시 충돌 가능성 차이

HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다.

 

해시 버킷의 동적 확장

• 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다.
• 버킷의 최대 개수는 230개다. 그런데 이렇게 버킷 개수가 두 배로 증가할 때마다, 모든 키-값 데이터를 읽어 새로운 Separate Chaining을 구성해야 하는 문제가 있다. 따라서 초기 사이즈를 적당하게 지정해주면 좋다.
• 두배로 확장하는 시점의 결정은 밀도가 임계치(75%)를 넘어설 때이다. 
• 두배로 확장할 때의 문제점이 크기가 2n, 즉 2의 지수승으로 커지면서 hash code의 하위 n 비트만 사용하게 된다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.
• 이 때문에 보조해시함수가 필요하다.

해싱, 해싱 함수, 해시충돌이란?

• 해싱은 해시함수를 이용해서 데이터를 해시 테이블에 저장하고 검색하는 기법을 말한다.
• 해시 함수는 임의의 문자열을 받아서 고정 문자열로 바꾸어주는 함수라고 일컫는다.
• 이때 서로 다른 문자열에 대하여 같은 고정 문자열이 될 수 있는데, 이러한 경우는 해쉬 충돌이라고 한다.

정렬된 키의 목록을 원한다면 TreeMap을 사용하자.

- TreeMap은 red-black 트리에 데이터를 담는다. TreeSet과 다른 점은 null 값을 허용한다는 점과 동기화 되어 있지 않다는 점이다.

- HashMap 객체의 키를 정렬하기 위해 Arrays라는 클래스를 사용하면 불필요한 객체가 생긴다는 단점이 있다. 이러한 단점을 보완하는 TreeMap라는 클래스가 있다. 이 클래스는 저장하면서 키를 정렬한다. 기본적인 순서는 "숫자 > 알파벳 대문자 > 알파벳 소문자 > 한글" 순이다. 하지만 매우 많은 데이터를 Treemap을 이용하여 보관하여 처리할때는 HashMap보다 느릴 것이다. 왜냐하면 키가 정렬되는 과정이 있기 때문이다. 하지만 100건, 1000건 정도의 데이터를 처리하고, 정렬을 해야할 필요가 있다면, HashMap보다는 Tremap를 사용하는 것이 더 유리하다.

TreeMap이 키를 정렬하는 것은 sortedMap이라는 인터페이스를 구현했기 때문이다. 키가 정렬되었을 때의 장점은 가장앞에 있는 키, 가장 뒤에 있는 키, 특정 키 뒤에 있는 키(higherKey()), 특정 키 앞에 있는 키(lowerKey()) 등을 알 수 있는 메소드를 제공해 준다는 것이다. 이러한 기능들은 키를 검색하는 프로그램을 작성할때 매우 도움이 된다.

Map을 구현한 properties 클래스는 알아두면 편리하다.

properties라는 클래스는 Hashtable를 확장 하였다. Map 인터페이스에서 제공하는 모든 메소드를 사용할 수 있다. 

정리

• HashMap과 HashTable을 정의한다면, '키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array'라고 할 수 있다. 

 

참고 자료 : 

자바의 신 / 이상민

해시테이블이란? / 망나니개발자

HashMap의 구조 /What a Great World!!

HashMap의 저장 방식 / Onsil's blog