[JAVA] 컬렉션 클래스 (Map)

컬렉션 클래스 HashMap

HashMap과 Hashtable의 관계는 ArrayList와 Vector의 관계와 같아서 Hashtable보다는 새로운 버전인 HashMap을 사용하는 것을 권장한다. 둘다 Map인터페이스를 상속받아 구현되어 데이터를 키와 값으로 관리하는 자료구조이다. 큰 특징으로는 키(Key)가 데이터를 추출할 때 구분자로 활용하는 방식을 취하는데 이는 리스트 인터페이스와 같은 자료구조보다 탐색에 있어서 더 높은 효율을 기대할 수 있다.

책에는 HashMap에 대해서만 설명이 되어 있는데 둘의 차이점을 간단히 살펴보고 넘어가자,

HashMap과 Hashtable의 차이

둘의 차이점으로 동기화를 들 수 있다. HashMap의 경우 동기화를 지원하지 않는다. 반면 다중 쓰레드 환경에서 Hashtable은 동기화를 지원하기 때문에 실행 환경에 따라 구분하여 사용하면 된다. 하지만 책에는 위에서 말했듯이 새로운 버전인 HashMap을 활용하고 동기화가 필요한 시점에는 Java 5부터 제공하는 ConcurrentHashMap을 사용하는 것이 더 좋은 방법이라 표현한다. ConcurrentHashMap은 HashMap과 다르게 Key, Value에 null을 허용하지 않는다. 추가로 속도적인 측면에서도 구형이라 할 수 있는 Hashtable은 동기화 처리라는 추가적 비용 때문에 HashMap에 비해 더 느리다고 한다.

※ Hashtable의 모든 Data 변경 메서드는 synchronized로 선언되어 있음.

HashMap 기본개념

다시 돌아와서 HashMap은 Map을 구현했기 때문에 Map의 특징인 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

HashMap이 데이터를 어떻게 저장하는지 확인하기 위해 실제소스의 일부를 살펴보자.

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
{
    transient Entry[] table;
 
    ...
 
    static class Entry implements Map.Entry {
        final Object Key;
        Object value;
        ...
    }
}

HashMap은 Entry라는 내부 클래스를 정의하고 다시 Entry타입의 배열을 선언하고 있다. 키와 값은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기 보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성을 보장하는 것에 더 바람직하다.

// 비객체지향적 코드
Object[] key;
Object[] value;
 
 
// 객체지향적 코드
Entry[] table;
class Entry {
    Object key;
    Object value;
}

한마디로 위와같은 코드의 차이.

※ Map.Entry는 Map인터페이스에 정의된 'static inner interface'이다.

HashMap은 키와 값을 각각 Object타입으로 저장한다. 즉, 어떤 객체도 저장할 수 있다. 하지만 키는 보통 String을 대문자 또는 소문자로 통일해서 사용한다.

키(key)        컬렉션 내의 키(key) 중에서 유일해야 한다.

값(value)      키(key)와 달리 데이터의 중복을 허용한다.

키는 저장된 값을 찾는데 사용되는 데이터이기 때문에 당연히 컬렉션 내에서 하나만 존재하여야 한다.

HashMap 예제 1

import java.util.*;
 
class HashMapEx1 {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("myId", "1234");
        map.put("asdf", "1111");
        map.put("asdf", "1234");
 
        Scanner s = new Scanner(System.in);    // 화면으로부터 라인단위로 입력받는다.
 
        while(true) {
            System.out.println("id와 password를 입력해주세요.");
            System.out.print("id :");
            String id = s.nextLine().trim();
 
            System.out.print("password :");
            String password = s.nextLine().trim();
            System.out.println();
 
            if(!map.containsKey(id)) {
                System.out.println("입력하신 id는 존재하지 않습니다. 다시 입력해주세요.");
                continue;
            } else {
                if(!(map.get(id)).equals(password)) {
                    System.out.println("비밀번호가 일치하지 않습니다. 다시 입력해주세요.");
                } else {
                    System.out.println("id와 비밀번호가 일치합니다.");                        
                    break;
                }
            }
        } // while
    } // main의 끝
}

[실행결과]

id와 password를 입력해주세요.

id :asdf

password :1111

비밀번호가 일치하지 않습니다. 다시 입력해주세요.

id와 password를 입력해주세요.

id :asdf

password :1234

id와 비밀번호가 일치합니다.

이 코드가 실행되고 나면 HashMap에는 아래와 같은 형태로 데이터가 저장된다.

키(key)	값(value)
myId	1234
asdf	1234

이 외에도 HashMap안에 HashMap을 넣어서 하나의 키에 복수의 데이터를 저장할 수 있도록 하는 방법도 있다. (이차원 배열처럼)

HashMap 예제 2

import java.util.*;
 
class HashMapEx2 {
    public static void main(String[] args) {
        String[] data = { "A","K","A","K","D","K","A","K","K","K","Z","D" };
 
        HashMap map = new HashMap();
 
        for(int i=0; i < data.length; i++) {
            if(map.containsKey(data[i])) {
                Integer value = (Integer)map.get(data[i]);
                map.put(data[i], new Integer(value.intValue() + 1));
            } else {
                map.put(data[i], new Integer(1));            
            }
        }
 
        Iterator it = map.entrySet().iterator();
 
        while(it.hasNext()) {
            Map.Entry entry = (Map.Entry)it.next();
            int value = ((Integer)entry.getValue()).intValue();
            System.out.println(entry.getKey() + " : " + printBar('#', value) + " " + value );
        }
    } // main
 
    public static String printBar(char ch, int value) { 
        char[] bar = new char[value]; 
 
        for(int i=0; i < bar.length; i++) { 
            bar[i] = ch; 
        } 
 
        return new String(bar);     // String(char[] chArr)
    }
}

[실행결과]

A : ### 3

D : ## 2

Z : # 1

K : ###### 6

문자열 배열에 담긴 문자열들의 빈도수를 구하는 예제이다.

문자열 배열에 담긴 문자열을 하나씩 읽어서 HashMap에 키로 저장하고 값으로 1을 저장한다. HashMap에 같은 문자열이 키로 저장되어 있는지 containsKey()메서드로 확인하여 이미 존재하는 문자열이면 값을 1 증가시킨다.

 

그리고 그 결과를 printBar()메서드를 이용해서 그래프로 표현했다.  한정된 범위 내에 있는 순차적인 값들의 빈도수는 배열을 이용하지만, 이처럼 한정되지 않은 범위의 비순차적인 값들의 빈도수는 HashMap을 이용해서 구할 수 있다.

※ 결과를 통해 HashMap과 같이 해싱을 구현한 컬렉션 클래스들은 저장순서를 유지하지 않는다는 사실을 다시 한 번 확인하자.

해싱과 해시함수

해싱이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다. 

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있다. 해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 되어 있다.

배열과 링크드 리스트의 조합

사진 출처 : http://codedragon.tistory.com/6334

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다.

책에 예시를 그대로 보면 한 간호사가 많은 병원의 환자 데이터 중에서, 원하는 환자의 데이터를 쉽게 찾을 수 있는 방법이 없을까를 고민하다가 주민등록번호의 맨 앞자리인 생년을 기준으로 데이터를 분류해서 10개의 서랍(배열)에 나눠 담는 방법을 생각해냈다고 하자.

예를 들면, 71년생, 72년생과 같은 70년대생 환자들의 데이터는 같은 서랍에 저장된다.

이렇게 분류해서 저장해두면 환자의 주민번호로 태어난 년대를 계산해서 어느 서랍에서 찾아야 할지를 쉽게 알 수 있다.

해싱에 사용되는 자료구조를 서랍에 비유한 그림

여기서의 서랍은 해싱에 사용되는 자료구조 중 배열의 각 요소를 의미하며, 배열의 각 요소에는 링크드 리스트가 저장되어 있어서 실제 저장한 데이터는 링크드 리스트에 담겨지게 된다.

아래 그림은 79년생 환자의 주민번호를 키로 해시함수를 통해 7이라는 해시코드를 얻은 다음, 배열의 7번째 요소에 저장된 링크드 리스트에서 원하는 데이터를 검색하는 과정을 표현한 것이다.

HashMap에 저장된 데이터를 찾는 과정

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.

2. 해시함수의 계산결과인 해시코드를 이용해서 해당 값이 저장되어 있는 링크드 리스트를 찾는다.

3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

이미 배운 바와 같이 링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다. 이는 하나의 서랍에 데이터의 수가 많을 수록 검색에 시간이 더 걸리는 것과 같다.

반면에 배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는 지만 알면 아래의 공식에 의해서 빠르게 원하는 값을 찾을 수 있다.

배열의 n번째 요소의 주소 = 배열의 시작주소 + type의 size * n

그래서 실생활과는 맞지 않는 얘기지만, 하나의 서랍에 많은 데이터가 저장되어 있는 형태보다는 많은 서랍에 하나의 데이터만 저장되어 있는 형태가 더 빠른 검색결과를 얻을 수 있다.

하나의 링크드 리스트(서랍)에 최소한의 데이터만 저장되려면, 저장된 데이터의 크기를 고려해서 HashMap의 크기를 적절하게 지정해주어야 하고, 해시함수가 서로 다른 키(위의 경우엔 주민번호)에 대해서 중복된 해시코드(서랍위치)의 반환을 최소화해야 한다. 그래야 HashMap에서 빠른 검색시간을 얻을 수 있다.

그래서 해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘이며, 이 예에서 사용된 해시함수의 알고리즘은 주어진 키(주민번호)의 첫 번째 문자를 뽑아서 정수로 반환하기만 하면 된다.

알고리즘이 간단한 만큼 성능은 좋지 않아서 서로 다른 키에 대해서 중복된 해시코드를 반환하는 경우가 많다. 실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다. Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일하다.

※ 참고로 String클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다. 따라서 서로 다른 String인스턴스일지라도 내용이 같으면 hashCode()의 결과 또한 같다.

TreeMap

TreeMap은 이름에서 알 수 있듯이 이진검색트리의 형태로 키와 값이 쌍으로 이루어진 데이터를 저장한다. 그래서 검색과 정렬에 적합한 컬렉션 클래스이다.

HashMap과 TreeMap은 검색에 관한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나므로 HashMap을 사용하는 것이 좋다. 다만 범위검색이나 정렬이 필요한 경우에는 TreeMap을 사용하자.

Properties

Properties는 HashMap의 구버전인 Hashtable을 상속받아 구현한 것으로, Hashtable은 키와 값을 (Object, Object)로 저장하는데 비해 Properties는 (String, String)으로 저장하는 보다 단순화된 컬렉션 클래스이다.

주로 어플리케이션의 환경설정과 관련된 속성(property)을 저장하는데 사용되며 데이터를 파일로부터 읽고 쓰는 편리한 기능을 제공한다. 그래서 간단한 입출력은 Properties를 활용하면 몇 줄의 코드로 쉽게 해결될 수 있다.

Collections

Arrays가 배열과 관련된 메서드를 제공하는 것처럼, Collections는 컬렉션과 관련된 메서드를 제공한다. fill(), copy(), binarySearch() 등의 메서드는 두 클래스에 모두 포함되어 있으며, 같은 기능을 한다. 

※ 주의 - java.util.Collection은 인터페이스이고 , java.util.Collections는 클래스이다.

컬렉션 클래스간 정리 및 요약

컬렉션 클래스간의 관계

컬렉션	특징
ArrayList	배열 기반, 데이터의 추가와 삭제에 불리, 순차적인 추가삭제는 제일 빠름.  임의의 요소에 대한 접근성이 뛰어남.
LinkedList	연결기반, 데이터의 추가와 삭제에 유리, 임의이 요소에 대한 접근성이 좋지 않다.
HashMap	배열과 연결이 결합된 형태, 추가, 삭제, 검색, 접근성이 모두 뛰어남. 검색에는 최고.
TreeMap	연결기반, 정렬과 검색(특히 범위검색)에 적합. 검색 성능은 HashMap보다 떨어짐
Stack	Vector를 상속받아 구현
Queue	LinkedList가 Queue인터페이스를 구현
Properties	Hashtable을 상속받아 구현
HashSet	HashMap을 이용해서 구현
TreeSet	TreeMap을 이용해서 구현
LinkedHashMap LinkedHashSet	HashMap과 HashSet에 저장순서유지기능을 추가하였음.

참고 : 자바의 정석 3rd