Map

• Map은 왜쓰였나? 왜 만들어졌나??
• HashTable
• Hash
• Java Map buckets

해당 포스트의 작성목적

컬렉션중 마지막인 Map에 대해서 알아보자!

Map이 무엇인지, 또 왜 만들어지고 쓰이는지 알아보자

Map??

자바에서 Map은 Key와 Value값으로 이루어져있다. Map에서 다른데이터와 구분하기 위해서 '값'의 이름을 key라고 보면 될것이다. 예를들어 A 핸드폰번호에 대한 주인은 A-라는 사람 한명뿐이다.

이때 A핸드폰 번호가 key, A-라는 사람은 값이 된다. 이 키는 Map안에서 중복될수 없다. 만일 value(값)이 같아도 key가 다르면 Map은 이를 다른것으로 취급한다.(마치 객체의 값은 같지만, 주소값은 다른 참조자료형의 객체들 같다.) 이런 Map의 특성은 다음과 같다.

• 모든 데이터는 키와 값이 존재한다.
• 키가 없이 값만 저장될수는 없다.
• 값 없이 키만 저장될수는 있다.
• 키는 해당 Map에서 고유해야한다.
• 값은 Map에서 중복되어도 상관없다.

왜 Map을 써야하는가?

Map은 Key와 Value 쌍으로 이루어져있다고 했다. 이런 관계에 있는 자료들(사전과 같은 형태...)을 처리할때 Map이 가장 성능이 좋기 떄문이다. 배열과 ArrayList에서 인덱스 값을 알고있을 경우 빠른 조회성능을 보여주는 것을 기억하는가? Map도 마찬가지이다. 단지 Map에서는 인덱스가 아니라 key라는 개발자가 직접 지정한 값일뿐이다.

Map을 구현한 주요 클래스들을 알아보자!

HashMap, TreeMap, LinkedHashMap등이 제일 유명하고 많이 쓰이는 클래스이며, HashTable이라는 클래스도 존재한다. HashTable도 Map을 구현하기는 했으나, 일반적인 Map을 구현한 클래스들과는 다르다. 두 클래스간의 차이점은 다음과 같다.

• Map은 컬렉션 뷰 (Collection View)를 사용하지만, HashTable은 Enumeration 객체를 통해서 데이터를 처리한다.
• Map은 키.값.키-값 쌍으로 데이터를 순환하여 처리하지만, HashTable은 이중에서 키-값쌍으로 데이터를 순환해 데이터를 처리할수 없다.
• Map은 Iteration을 처리하는 도중에 데이터를 삭제하는 안전한 방법을 제공하지만, HashTable은 그렇지 않다.

추가적인 차이점 Map VS HashTable

같은 Map을 구하는데, 왜 이런 차이가 발생했을까?

자바에 Collection이라는 인터페이스가 추가된것은 JDK.1.2부터다. 그러나, HashTable은 JDK1.0부터 사용되던 클래스이기 때문에 Map의 기능을 구현한것은 1.2이후부터다. 즉, 만들어진 Map에 맞춰 보완되었다고 보면 되겠다. 우리에게 중요한것은 어떤 클래스가 어느버전에 추가되었는지를 아는것이 아니라, 각 클래스의 특징을 알고, 어떤 작업을 할때 어떤 클래스가 더 유리한지 아는것이 더 중요하다. 특히 HashTable은 제외한 Map을 구현한 클래스들 중 Map으로 끝나는 클래스들 대부분은

멀티스레드 환경에서 쓰려면 다음과 같이 써야한다.

Map m = Collections.synchronizedMap(new HashMap(...));

혹은 이름에 Concurrent가 포함되어 있어야만 쓰레드 세이프하다! 이런 설명은 언제나 API에 있으므로, 항상 참고하도록 하자!

HashMap이란?!

그럼 Map을 구현하는 클래스들 중 가장 많이쓰이는 HashMap에대해서 알아보자. 우선 HashMap의 상속관계와 구현하고 있는 인터페이스를 알아보자

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

All Implemented Interfaces:
Serializable, Cloneable, Map<K,V>

HashMap클래스는 AbstractMap 이라는 Abstract클래스를 상속받았으며, 주요 메소드의 구현은 AbstractMap클래스에서 구현을 해두었다. 인터페이스는 앞서 알아본 List나 Set, Queue에 비하면 단순한것을 알수있다.

HashMap의 키가되는 객체를 개발자가 직접 만들었을 때는 매우 중요한것이 있다.

바로 Object클래스로부터 상속받는 equals()와 hashCode()를 잘 구현해 둬야한다는 것이다.

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

HashMap 객체의 값을 확인하는 방법은 여러가지가 있다.

• get() : 매개변수로 키를 넣어주면, 키에 해당하는 값을 리턴한다.

map.put("A","a");
System.out.println(map.get("A"));
// a

• keySet() : HashMap의 키값들을 확인하는 메소드, get()메소드를 위해서는 키를 알고있어야 하므로, Map을 사용한다면 키를 확인하는 방법은 꼭 알고있어야한다. 메소드 이름에서 알수있듯이, 반환값은 Set형이며, Set의 제네릭타입은 키의 제네릭타입과 동일하게 선언하면 된다.

map.put("A","a");
map.put("B","b");
map.put("C","c");
map.put("D","d");
Set<String> keySet = map.keySet();
for(String key : keySet){
    System.out.print(key + " = " + map.get(key) +"  ");
}
// D=d  A=a  B=b  C=c

결과 순서가 왜 이러지? 생각했다면, 순서를 중요하게 생각하는것은 List와 Queue뿐인것을 다시 상기하자.

• values() : HashMap에 담겨있는 값들의 목록을 Collection타입으로 반환한다.

map.put("A","a");
map.put("B","b");
map.put("C","c");
map.put("D","d");
Collection<String> values = map.values();
for(String value : values){
    System.out.print(value+" ");
}
// d a c b

• entrySet() : Map에서 선언된 Entry라는 타입의 객체를 반환, 이 Entry에는 단하나의 키와 값만 저장된다. 이 Entry객체의 getKey()와 getValue()메소드를 사용하면 키와 값을 간단히 가져올수있다.

map.put("A","a");
map.put("B","b");
map.put("C","c");
map.put("D","d");
Set<Map.entry<String,String>> entries = map.entrySet();
for(String entry : entries){
    System.out.print(entr.getKey()+" : " + entry.getValue() + "  ");
}
//D : d  A : a  B : b  C : c

정렬된 키의 목록을 원한다면 TreeMap을!

만약 우리가 HashMap에서 키를 정렬하려면 여러가지 방법을 써야할것이다. 그중 간단한 방법중 하나가 Arrays라는 클래스를 이용하는 방법인데, 이렇게 되면 불필요한 객체가 하나 더 생기게 된다.

이럴때 TreeMap을 사용하면 좋다. TreeMap은 키를 저장하면서 동시에 정렬을 한다.

매우 많은 데이터를 TreeMap을 이용해 처리하면 HashMap보다는 느릴 것이다. 그러나 100건, 1000건 정도의 데이터를 처리하고, 정렬해야 할 필요가 있다면 HashMap보다는 TreeMap을 추천한다.

이렇게 정렬이 가능한 이유는 TreeMap이 SortedMap 인터페이스를 구현했기 때문이다.

SortedMap을 구현한 모든 클래스는 모두 키가 정렬되있어야 한다. 이렇게 키를 정렬했을때 장점은

가장 앞에 있는키(firstKey()), 가장 뒤에있는키(lastKey()), 특정 키 뒤에있는 키(higherKey()), 특정키 앞에있는 키(lowerKey())등의 메소드를 사용할수 있다는 것이다. 이런 메소드들은 키를 검색하는 프로그램을 작성할 때 매우 도움이 된다.

Map을 구현한 Properties 클래스!

System클래스를 공부하면서 Properties 클래스도 가볍게 알아본적이 있다. Properties는 HashTable을 확장한 클래스이다. getProperties() 메소드는 Properties객체를 반환하며, Map객체의 값을 확인하는 방법들과 같은 방법들로 Properties객체의 값을 확인할 수있다.

public class MapExam {
    public static void main(String[] args) {
        Properties props = System.getProperties();
        Set<Entry<Object, Object>> entries = props.entrySet();
        for(Entry entry : entries) {
            System.out.println(entry);
        }
    }
}
/*
java.runtime.name=Java(TM) SE Runtime Environment
sun.boot.library.path=D:\gitPrjxt\smartcard\jdk1.8.0_112\jre\bin
java.vm.version=25.112-b15
java.vm.vendor=Oracle Corporation
java.vendor.url=http://java.oracle.com/
path.separator=;
java.vm.name=Java HotSpot(TM) 64-Bit Server VM...
*/

왜? Properties를 쓸까??

위의 예제코드에서 보듯이 기존의 Map과 완전히 똑같은 방식으로 값과 속성을 읽고 있다. 그럼 왜?? 귀찮게 Properties 클래스를 쓸까?? HashMap 클래스나 HashTable를 쓰면 되지않을까??

다음과 같이 Properties에서 제공하는 메소드를 사용하기 위해서다.

Properties에서 제공하는 메소드

Properties클래스의 객체는 시스템 속성만 저장할 수있는것이 아니다! 우리가 사용하는 어플리케이션에서 사용할 여러가지 속성값들을 Properties 클래스를 사용해 데이터를 넣고, 빼고 처리할수있다. 만약 이 클래스가 없다면, 개발자들이 직접 파일을 읽고, 쓰는 메소드들을 만들어야 할 것이다.

간단하게 설정파일을 만들고, 이를 읽어들여 출력하는 코드를 작성해 보자.

public class PropExam {
    public static void main(String[] args) {
        String fileName = "test.properties";
        File propFile = new File(fileName);
        try(FileOutputStream fos = new FileOutputStream(propFile);
                FileInputStream fis = new FileInputStream(propFile)){
            //속성 파일 만들기
            Properties props = new Properties();
            props.setProperty("Writer", "phd");
            props.setProperty("comp", "tsis");
            props.store(fos, "exam Properties file");
            //속성값 로드 & 출력
            Properties loadedProps = new Properties();
            loadedProps.load(fis);
            System.out.println(loadedProps); //출력

        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }
}
// {comp=tsis, Writer=phd}

갑작스레 등장한 FileOutputStream과 FileInputStream, File등의 코드가 혼란스럽겠지만, 후에 공부할태니 간단하게만 알고 넘어가자. File클래스은 File을 다룰때 사용하며, outputStream은 파일을 저장할때, inputStream은 파일을 읽어드릴때 쓰인다.

HashTable이란?

해시 테이블은 키와값으로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수있는 자료구조이다. 이렇게 빠른 검색속도를 제공할 수 있는 이유는 내부적으로 배열(버킷)을 사용해 데이터를 저장하기 때문이다. 해시테이블은 각각의 key에 해시함수를 적용해 배열의 고유한 index를 생성한다. 이 index를 활용해 값을 저장하거나 검색한다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.

https://mangkyu.tistory.com/102

예를 들어 (key : value) 값이 (Johm Smith : 521-1234)인 데이터를 해시 테이블에 저장한다고 하자,

index = hash_function("John Smith") % 16 연산을 통해 index 값을 계산한다. 그리고 Arrray[index] = "521-1234" 로 value를 저장한다. 이렇게 데이터를 저장한다면 key값으로 데이터를 찾을때 hash함수를 1번만 수행하면 되므로 시간복잡도는 O(1)이 되게 된다.

Hash함수?....

해시 함수는 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수다.

(해시함수로 고유값을 만들수 있으면 좋겠지만, 그것은 현실적으로 불가능 하며, 이렇게 서로다른 메세지의 해시값이 같게 나올경우 충돌(Collision)이 일어났다고 하며, 해시함수들은 이런 충돌을 줄이는것을 목표로 발전해왔다)

해시함수에서 중요한 것은 고유한 인덱스 값을 설정하는 것이다. 해시 테이블에 사용되는 대표적인 해시 함수는 아래의 3가지가 있다.

• Division Method : 나눗셈을 이용, 입력값을 테이블의 크기로 나누어 계산 (주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 한다.
• Digit Folding : 각 key의 문자열을 아스키코드로 바꾸고 값을 합한 데이터를 데이블 내의 주소록 사용
• Multiplication Method : 숫자로 된 key와 0과1사이의 실수 A, 보통 2의 제곱수인 m을 사용해 다음과 같은 계산을 한다. h(k) = (kA mod 1) * m
• Universal Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법

Java Map Bucket 과 LoadFactor

위 해시테이블에서 설명한 Bucket, 그리고 로드팩터에 대해서 좀더 알아보자.

map이라는 객체는 별도의 설정이 없다면 생성시 capacity = 16, load_factor = 0.75 값을 가지고 bucket이라는 ArrayList를 만든다. 만약 map.put(16,12); 를 실행하면 먼저 다음과 같은 연산을 실행한다.

int index = key.hashCode() % capicty;

여기서 key는 16이 되겠고, capacity는 기본값인 16이다. Integer의 hashCode()는 Integer값을 그대로 반환한다. 그러므로 index = 16 % 16 → 0이 되겠다. 이 연산이 행해지면 (16,12)로 이루어진 데이터는 map 내부의 bucket의 0번째 공간에 12를 저장한다. 이런식으로 데이터를 저장하다가, (32,9)라는 데이터를 저장하게 되면, 역시 index값이 0 이 나온다. 이때는 기존에 존재하던 (16,12) 데이터 앞에 (32,9)를 저장하고 노드의 next값이 (16,12)를 참조하도록 설정한다. 즉 LinkedList의 형태로 노드들이 저장되는것이다. 이런 방식으로 데이터가 저장되는 것을 Seperate Chaning이라고 부른다. 이상황에서 get()메소드를 쓴다고 해보자. map.get(16)을 했다면 key의 해시코드를 계산, 곧바로 0번째 공간을 찾아간다. 그런데 이 공간에는 데이터가 1개가 아니다. 여기서 equals()메소드를 통해 key가 같은지를 확인한다. 이런 현상때문에 해싱 충돌이 일어날수록 기존 O(1) → O(n)으로 가까워진다. 이런 현상을 ㄱ고자 map은 capacity에 일정 데이터가 저장되면 자동으로 bucket의 크기를 늘린다(약 두배).

load_factor == 저장된 데이터 수 / capacity

위 코드가 true가 되는 시점에 bucket을 자동으로 늘린다.

즉 load_facotr는 한 공간에 저장된 데이터의 수를 뜻한다고 볼수 있다. 그럼 load_factor의 기본값이 0.75라는 것은 한공간에 저장된 데이터의 평균수가 0.75개, 즉 1개도 안되서 버킷을 늘려버린다 라는 말이다. 이 과정을 rehashing이라고 하며, 모든 키들의 hashCode를 다시 실행하고, 그에 맞게 저장하게 된다.

왜?? 데이터의 수가 한 공간에 1개조차 저장되지 않았는데 버킷을 늘릴까??

한 공간에 있는 데이터 수가 1개 이하라면 get()메소드를 호출해도 equals()등의 메소드를 호출하지 않을태니 O(1)을 보장할수 있지 않을까?? 하지만 이것은 평균의 함정이다.

만약 16개의 저장공간에 데이터들이 균등하게 퍼져 저장된다면 해시충돌이 일어나지 않을것 이다. 그러나 해시충돌이 많이 일어나게 된다면?? 16개의 공간중 한 공간에만 데이터가 많이 저장된다고 보자. 분명 load_factor는 낮아도, 성능은 낮아지는것을 체험할 수있다. 그러나, capacity를 무작정 늘린다고 만사가 해결되지는 않는다. 메모리 공간이 그만큼 늘어나고, 비효율적이 되기 떄문이다. 즉 이런 복잡한 상황속에서 0.75가 가장 이상적인 값이라고 API가 친절히 말해주고 있다.

포스트를 작성하며 알게된 점

Map의 객체의 값을 가져오는 메소드 keySet과 entrySet에 대해서 좀더 자세히 알게되었다. 부끄럽지만 여태까지는 모두 get()메소드 만을 이용해왔었다. keySet()과 entrySet() 메소드에 대한 개념이 없었기 떄문이다.... 또 HashMap외에도 Map을 구현한 클래스중 데이터를 저장하면서 동시에 정렬하는 TreeMap이 있다는 사실을 알게되었다. 예전에는 많이 쓰이는것만 알면 되지, 뭐하러 다른 클래스들을 알아야하나? 라는 생각이 있엇지만, 요즘은 이런 클래스도 있구나!! 저 클래스는 어떤 특징이 있으며, 어떤 상황에서 써야 좋은 클래스인걸까? 라는 생각이 든다. 조금씩 조금씩 생각의 방향이 바뀌고 있는것 같다.

Reference

[Java] HashMap의 element 저장 방식(bucket) - Onsil's blog

#2 - 해시함수란 무엇인가? - Steemit

[자료구조] 해시테이블(HashTable)이란?