The Map Interface

The Map Interface

Map은 키와 값으로 구성된 객체이다. 맵은 중복되는 키 값을 가질 수 없다. 각 키값은 맵 상에서 오직 하나의 값을 가질 수 있다. 이 모델은 수학 함수에 기반을 두고 있으며, 다음 인터페이스를 가지고 있다.

public interface Map<K,V> {



    // Basic operations

    V put(K key, V value);

    V get(Object key);

    V remove(Object key);

    boolean containsKey(Object key);

    boolean containsValue(Object value);

    int size();

    boolean isEmpty();



    // Bulk operations

    void putAll(Map<? extends K, ? extends V> m);

    void clear();



    // Collection Views

    public Set<K> keySet();

    public Collection<V> values();

    public Set<Map.Entry<K,V>> entrySet();



    // Interface for entrySet elements

    public interface Entry {

        K getKey();

        V getValue();

        V setValue(V value);

    }

}

Java 플랫폼에서는 다음과 같이 3가지 범용 맵을 구현하고 있으며 HashMap, TreeMap, LinkedHashMap이 그것이다. 이들의 동작은 HashSet, TreeSet, LinkedHashSet과 동일하게 동작한다. The Set Interface을 참조하길 바란다. 또한 Hashtable는 Map을 구현한 객체이다.

Hash테이블과 비교

만약 Hashtable을 이용하고 있다면 아마도 Map과 유사함을 느낄 것이다. (물론 Map는 인터페이스이고 Hashtable는 콘크리트 구현체이다.). 다음은 주요 차이점이다.

• Map는 직접적으로 Enumeration 객체를 반복하는것 대신에 Collection 뷰를 이용하도록 하고 있다. Collection 뷰는 인터페이스의 풍부한 항목을 이용할 수 있도록 하고 잇다.
• Map는 key, value들과 key-value 쌍의 반복을 허용한다. Hashtable는 이러한 오퍼레이션을 제공하지 않는다.
• Map는 엔트리를 탐색하고, 이를 제거할때 안전한 방법을 제공한다. 그러나 Hashtable는 그렇지 못하다.

마지막으로 Map는 Hashtable 인터페이스의 작은 결함을 수정했다. Hashtable는 contains라는 메소드를 가지고 있으며 이것은 특정 값을 해시테이블이 가지고 잇을경우 true값을 반환하도록 되어 있다. 만약 주어진 키 값이 존재하는지 검사하고 싶고, 존재한다면 true를 받고 싶을 것이다. Map에서는 다음과 같이 containsValue라는 메소드로 이 값을 대체하고 있다. 또한 일관성 있는 인터페이스를 제공하고 있다. containsValue와 쌍으로 containsKey를 구현하고 있다.

Map Interface Basic Operations

맵의 기본적인 처리는 (put, get, containsKey, containsValue, size, isEmpty)처럼 Hashtable에 있는 것과 동일한 처리를 수행한다. following program 은 아규먼트 리스트로 부터 테이블을 생성하는 처리를 한다. frequency 테이블의 각 단어들은 아규먼트 리스트에서 발생된 수치값의 빈도를 저장한다.

import java.util.*;



public class Freq {

    public static void main(String[] args) {

        Map<String, Integer> m = new HashMap<String, Integer>();



        // Initialize frequency table from command line

        for (String a : args) {

            Integer freq = m.get(a);

            m.put(a, (freq == null) ? 1 : freq + 1);

        }



        System.out.println(m.size() + " distinct words:");

        System.out.println(m);

    }

}

이 프로그램의 트릭중의 하나는 put 문장에서 두번째 아규먼트이다. 이 아규먼트는 상황에 따라 설정되는 값이 틀리며, 여기서는 값이 freq의 값이 존재할때에는 기존값에 1을 더해주고, 그렇지 않은경우 1을 설정하도록 되어 있다. 이 프로그램을 실행하기 위해서 다음과 같이 수행해보자.

java Freq if it is to be it is up to me to delegate

프로그램의 결과는 다음과 같이 나온다.

8 distinct words:

{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

예상하는것과 같이 알파벳 순서로 출력이 되도록 하고 싶다면, HashMap에서 TreeMap를 이용하여 처리를 하게 되면 이러한 결과가 나오게 된다.

8 distinct words:

{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

유사하게 첫번째 나오는 문장부터 값이 순서대로 나오게 하고 싶다면 LinkedHashMap를 이용하면 다음과 같은 결과가 나온다.

8 distinct words:

{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

Set과 List 인터페이스와 같이 Map는 equals와 hashCode를 엄격히 처리한다. 내부에 존재하는 값이 동일한경우 두 값은 동일하다고 판단하게 된다. 두개의 맵에서 key-value 쌍이 서로 동일하게 저장되어 있다면 이들은 서로 같다고 표현한다.

모든 범용 목적의 Map는 특정 맵에 포함된 값을 새로운 맵으로 복사를 수행하도록 하고 있다. 이러한 표준 맵 변환은 표준  Collection 생성자와 같이 수행된다. 이것은 하나의 맵의 모든 엘리먼트를 새로운 맵에 추가하여 생성할 수 있도록 하고 있다. 예를 들어, m이라는 맵이 존재할경우 다음 라인은 새로운 HashMap를 생성하며, 동일한 키와 값을 가지도록 한다.

Map<K, V> copy = new HashMap<K, V>(m);

Bulk 데이터를 위한 맵 오퍼레이션

clear 처리는 생각하는데로, 정확한 처리를 수행한다. 맵으로 부터 모든 값을 제거하고자 할때 사용된다. putAll 처리는 콜렉션 인터페이스인 addAll 처리와 같은 동작을 수행한다.

static <K, V> Map<K, V> newAttributeMap(

        Map<K, V>defaults, Map<K, V> overrides) {

    Map<K, V> result = new HashMap<K, V>(defaults);

    result.putAll(overrides);

    return result;

}

Collection Views

Collection view 메소드는 다음과 같이 3가지 방법을 통해서 Map의 내용에 대한 view를 제공한다.

• keySet — Map에 포함된 키의 셋을 반환한다.
  
• values — Map에 포함된 value의 컬렉션들을 반환한다. 이 Collection은 Set이 아니다. 왜냐하면 다양한 키에 대해서 동일한 값을 가질 수 있기 때문이다.
• entrySet — Map에 포함된 key-value쌍에 대한 집합을 가진다. Map인터페이스는 작은 인터페이스를 가지고 있는데 이것이 Map.Entry이다.
  

Collection 뷰는 Map를 irerator 로만 접근 할수 있도록 하고 있는데 이 예제는 맵에 속해있는 키 값에 의해서 for-each구문을 이용하여 접근하는 법을 보여주고 있다.

for (KeyType key : m.keySet())

    System.out.println(key);

iterator을 이용한 처리

// Filter a map based on some property of its keys.

for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )

    if (it.next().isBogus())

        it.remove();

연속적인 방법으로 값을 iterating 해서 가져오는방법

for (Map.Entry<KeyType, ValType> e : m.entrySet())

    System.out.println(e.getKey() + ": " + e.getValue());

첫번째로 많은 사람들이 걱장허는 것은 Map가 Collection 처리에서 Collection 인스턴스를 매번 생성하는 것이 늦을 것이라고 생각하는 것이다. 쉽게 생각하면, 맵은 주어진 Collection view에서 매번 동일한 객체를 반환하지 않기 때문이다.

With all three Collection views, calling an Iterator's remove operation removes the associated entry from the backing Map, assuming that the backing Map supports element removal to begin with. This is illustrated by the preceding filtering idiom.

entrySet 뷰는 반복때 Map.Entry's의 setValue 메소드를 호출함으로 해서 연관된 값을 변화 시킬 수 있다. 이러한 방법은 iteration을 통해서 값을 수정할때 가장 안정적인 방법이다. 언뜻 보아서는 Map를 iteration을 이용하여 값을 변경할 수 있는 다른 방법이 있을것 같지만, 다른것은 권하지 않는 방식이다.

Collection 뷰는 많은 형태의 remove 처리를 제공한다. remove, removeAll, retainAll, clear이 그것이다. 

Collection view는 특정 환경에서는 엘리먼트 추가 작업을 지원하지 않는다. 이것은 keySet과 value뷰에서 의미상 맞지 않는 것이다. baking Map는 put과 putAll 메소드를 동일하게 지원한다.

Fancy Uses of Collection Views: Map Algebra

Collection 뷰를 이용하여 bulk 오퍼레이션을 수행할때 (containsAll, removeAll, retainAll)과 같은 것을 수행할때 매우 강력한 툴이 있다. 예를 들어 하나의 맵이 다른 맵을 가지고 있는지 알고자 할때, 첫번째 맵이 두번째 맵의 모든 키와 값을 알아야 하는 경우와 같은 처리를 수행할때 다음과 같은 코드를 확인해 보자

if (m1.entrySet().containsAll(m2.entrySet())) {

	...

}

동일한 라인에 2개의 맵에 대해 모두 동일한 키값을 가지고 있는지에 대해서 알고자 한경우 다음 코드를 확인해보자.

if (m1.keySet().equals(m2.keySet())) {

	...

}

Map에서 속성 값의 컬렉션을 표현하고자 할 경우, 두개의 set이 표현할 수 있는 속성과 퍼미션된 속성이 있을 수 있다. (퍼미션가능한 속성은 요구되는 속성값을 포함하고 있다.) 다음 정의부분을 보면 값을 충족 시키거나, 자세한 오류 메시지를 보여주는 예이다.

static <K, V> boolean validate(Map<K, V> attrMap,

        Set<K> requiredAttrs, Set<K>permittedAttrs) {

    boolean valid = true;

    Set<K> attrs = attrMap.keySet();

    if(!attrs.containsAll(requiredAttrs)) {

        Set<K> missing = new HashSet<K>(requiredAttrs);

        missing.removeAll(attrs);

        System.out.println("Missing attributes: " + missing);

        valid = false;

    }

    if (!permittedAttrs.containsAll(attrs)) {

        Set<K> illegal = new HashSet<K>(attrs);

        illegal.removeAll(permittedAttrs);

        System.out.println("Illegal attributes: " + illegal);

        valid = false;

    }

    return valid;

}

두개의 모든 객체에서 공통적인 키 값을 원하는 경우.

Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());

commonKeys.retainAll(m2.keySet());

동일한 처리로 공통적인 값을 획득할 수있다.

모든 처리는 비 파괴적인 방식으로 처리된다. 이것들은 backing Map을 변경하지 않는다. 여기서는 몇개의 처리를 볼 수 있다. 하나의 맵에서 모든 키-값 쌍을 제거하고 다른 곳으로 이동하고자 할 경우 다음과 같이 처리할 수 있다.

m1.entrySet().removeAll(m2.entrySet());

하나의 맵의 모든 키값과 매핑되는 값을 다른 테이블에서 제거를 원하는 경우 다음과 같이 처리할 수 있다.

m1.keySet().removeAll(m2.keySet());

혼합된 키와 값의 쌍에 대한 벌크데이터를 처리하고자 하는일이 발생한다면? 관리자 맵과, 각 고용인에 대해서 회사 고용인들을 관리하는 관리자 맵이 있다면... 우리는 키와 값을 처리하는것에 대한 애메한 사항에 대해서 심사숙고 해야한다. 동일한 형태의 자료에 대해서 시간이 충분하다면 이것은 문제가 되지 않을 것이다. 지금 모든 "개인 기여자" 혹은 매니져가 없는 사람을 알기를 원한다면 다음 예제를 보면 알 수 있을것이다.

Set<Employee> individualContributors =

    new HashSet<Employee>(managers.keySet());

individualContributors.removeAll(managers.values());

만약 Simon이라는 사람의 특정 관리자를 거치지 않고 바로 해고하고자 한다면 다음과 같이 처리하면 된다.

Employee simon = ... ;

managers.values().removeAll(Collections.singleton(simon));

여기에 사용된 Collections.singleton은 정적 팩토리 메소드로 변하지 않는 Set을 반환한다.

한번 이 작업을 수행하면, 회사에서 더이상 일하지 않을 사람에 대한 묶음을 가지게 된다. 다음 코드는 회사에서 더이상 일할 수 없는 사람들의 관리자가 있는지 여부를 말해주는 코드이다.

Map<Employee, Employee> m =

    new HashMap<Employee, Employee>(managers);

m.values().removeAll(managers.keySet());

Set<Employee> slackers = m.keySet();

여기에 트릭이 조금 있는데 첫번째는 Map의 임시 복사본을 만드는 것과 임시 맵에서 원본 맵의 키값에 대한 모든 엔트리를 제거하고 있는 것이다. 그러므로 임시 맵에 남은 엔트리는 원본에 있는 관리자 키코드 값에든 더이상 직원이 없게 된다. 임시로 복사된 키는 여전히 일을 하고 잇는 사람이 된다.

이번 섹션에서는 많은 용어를 봤다. 그러나 모든것을 다 이해하는것은 불필요하고 지루한 것이다. 필요한 것만 확인하면 될 것이다.

Multimaps

멀티맵은 Map과 같다. 그러나 각 키값에대해서 복합적인 값을 가질 수 있는 것이다. Java Collectons Framework는 멀티맵을 위한 인터페이스를 가지고 있지 않다. 외냐 하면 일반적으로 사용되는 것이 아니기 때문이다. 이것은 value를 위해 Map을 사용하거나 List를 이용하는 형태로 구현된다. 다음 코드는 단순하게 기술적으로 구현해보는 것으로, 각 단어 리스트에 포함된 단어를 읽고, 이것을 알파벳 순으로 처리하는 것이다. anagram group는 단어의 묶음으로 정확하게 같은 단어들을 포함할것이다. 그러나 순서는 틀리게 저장된다. 프로그램은 2개의 아규먼트를 입력받고 하나는 딕셔나리 파일이고 다른하나는 anagram 그룹이 출력될 최소 크기가 된다. Anagram 그룹은 지정된 최소값의 여부에 따라 출력이 되지 않을 것이다.

여기에는 anagram 그룹을 찾기 위한 표준 트릭값을 가지고 있다. 각 단어사전에는 알파벳순으로 저장되며, 멀티맵에 저장된다.

예를 들면 bad라는 단어가 생기면 abd라는 단어로 bad라는 멀티맵에 저장이 된다. 이값은 단순하게 anagram 그룹으로 부타 매핑된 값을 보여주게 되며, 멀티맵에 저장된 anagram 그룹은 크기의 제약에 걸리게 되면 각 내용을 출력하게 된다.

The following program 이 프로그램은 직관적으로 이러한 기술을 보여준다.

import java.util.*;

import java.io.*;



public class Anagrams {

    public static void main(String[] args) {

        int minGroupSize = Integer.parseInt(args[1]);



        // Read words from file and put into a simulated multimap

        Map<String, List<String>> m

	    = new HashMap<String, List<String>>();

        try {

	    Scanner s = new Scanner(new File(args[0]));

            while (s.hasNext()) {

		String word = s.next();

                String alpha = alphabetize(word);

                List<String> l = m.get(alpha);

                if (l == null)

                    m.put(alpha, l=new ArrayList<String>());

                l.add(word);

            }

        } catch (IOException e) {

            System.err.println(e);

            System.exit(1);

        }



        // Print all permutation groups above size threshold

        for (List<String> l : m.values())

            if (l.size() >= minGroupSize)

                System.out.println(l.size() + ": " + l);

    }



    private static String alphabetize(String s) {

	char[] a = s.toCharArray();

	Arrays.sort(a);

	return new String(a);

    }

}

Running this program on a 173,000-word dictionary file with a minimum anagram group size of eight produces the following output.

9: [estrin, inerts, insert, inters, niters, nitres, sinter,

     triens, trines]

8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]

8: [aspers, parses, passer, prases, repass, spares, sparse,

     spears]

10: [least, setal, slate, stale, steal, stela, taels, tales,

      teals, tesla]

8: [enters, nester, renest, rentes, resent, tenser, ternes,

     treens]

8: [arles, earls, lares, laser, lears, rales, reals, seral]

8: [earings, erasing, gainers, reagins, regains, reginas,

     searing, seringa]

8: [peris, piers, pries, prise, ripes, speir, spier, spire]

12: [apers, apres, asper, pares, parse, pears, prase, presa,

      rapes, reaps, spare, spear]

11: [alerts, alters, artels, estral, laster, ratels, salter,

      slater, staler, stelar, talers]

9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,

     secpar, spacer]

9: [palest, palets, pastel, petals, plates, pleats, septal,

     staple, tepals]

9: [anestri, antsier, nastier, ratines, retains, retinas,

     retsina, stainer, stearin]

8: [ates, east, eats, etas, sate, seat, seta, teas]

8: [carets, cartes, caster, caters, crates, reacts, recast,

     traces]

이내용은 조작된 것처럼 보일것이다. 그러나 프로그램의 오류가 아니라. 단어 사전에 저장된 내용때문에 그런 것이다. dictionary file을 보면 확인할 수 있다.