Lesson: Introduction to Collections 4

[이진 탐색 트리]

 

[Hash, Map, Set 참조]

The Map Interface

Map은 키를 값에 매핑하는 객체입니다. Map은 중복된 키를 가질 수 없습니다. 각 키는 최대 하나의 값에만 매핑될 수 있습니다. 이는 수학적 함수 추상화를 모델링합니다. Map 인터페이스에는 기본 작업(예: put, get, remove, containsKey, containsValue, size, isEmpty), 대량 작업(예: putAll, clear), 컬렉션 뷰(예: keySet, entrySet, values)를 위한 메서드가 포함되어 있습니다.

※ 수학적 함수 추상화란 일대일 대응(one-to-one mapping) 함수를 의미.

Java 플랫폼에는 세 가지 범용 Map 구현이 있습니다: HashMap, TreeMap, LinkedHashMap. 이들의 동작과 성능은 Set 인터페이스 섹션에서 설명한 HashSet, TreeSet, LinkedHashSet과 정확히 유사합니다.

이 페이지의 나머지 부분에서는 Map 인터페이스에 대해 자세히 논의합니다. 먼저, JDK 8 aggregate 작업을 사용하여 Map에 컬렉팅하는 몇 가지 예를 소개합니다. 객체 지향 프로그래밍에서 현실 세계의 객체를 모델링하는 것은 일반적인 작업이므로, 예를 들어 직원들을 부서별로 그룹화하는 프로그램이 있을 수 있습니다.

// Group employees by department
Map<Department, List<Employee>> byDept = employees.stream()
.collect(Collectors.groupingBy(Employee::getDepartment));

 

또는 부서별로 모든 급여의 합계를 계산합니다:

// Compute sum of salaries by department
Map<Department, Integer> totalByDept = employees.stream()
.collect(Collectors.groupingBy(Employee::getDepartment,
Collectors.summingInt(Employee::getSalary)));

 

또는 학생들을 합격 및 불합격 성적으로 그룹화합니다:

// Partition students into passing and failing
Map<Boolean, List<Student>> passingFailing = students.stream()
.collect(Collectors.partitioningBy(s -> s.getGrade()>= PASS_THRESHOLD));

 

또한 사람들을 도시별로 그룹화할 수도 있습니다:

// Classify Person objects by city
Map<String, List<Person>> peopleByCity
         = personStream.collect(Collectors.groupingBy(Person::getCity));

 

또는 두 개의 컬렉터를 사용하여 사람들을 주(state)와 도시(city)별로 분류할 수도 있습니다:

// Cascade Collectors 
Map<String, Map<String, List<Person>>> peopleByStateAndCity
  = personStream.collect(Collectors.groupingBy(Person::getState,
  Collectors.groupingBy(Person::getCity)))

 

다시 말하지만, 이것들은 새로운 JDK 8 API를 사용하는 몇 가지 예에 불과합니다. 람다 expression과 aggregate 연산에 대한 심도 있는 내용은 "Aggregate 연산"이라는 제목의 강의를 참조하십시오.

 

위 설명에 소개된 단편 코드들이 포함된 샘플 코드는 다음과 같습니다.

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;

// Department 클래스 정의
class Department {
    private String name;

    public Department(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Department that = (Department) obj;
        return name.equals(that.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }
}

// Employee 클래스 정의
class Employee {
    private String name;
    private Department department;
    private int salary;

    public Employee(String name, Department department, int salary) {
        this.name = name;
        this.department = department;
        this.salary = salary;
    }

    public String getName() {
        return name;
    }

    public Department getDepartment() {
        return department;
    }

    public int getSalary() {
        return salary;
    }

    @Override
    public String toString() {
        return name + "(" + salary + ")";
    }
}

// Student 클래스 정의
class Student {
    private String name;
    private int grade;

    public Student(String name, int grade) {
        this.name = name;
        this.grade = grade;
    }

    public String getName() {
        return name;
    }

    public int getGrade() {
        return grade;
    }

    @Override
    public String toString() {
        return name + "(" + grade + ")";
    }
}

// Person 클래스 정의
class Person {
    private String name;
    private String city;
    private String state;

    public Person(String name, String city, String state) {
        this.name = name;
        this.city = city;
        this.state = state;
    }

    public String getName() {
        return name;
    }

    public String getCity() {
        return city;
    }

    public String getState() {
        return state;
    }

    @Override
    public String toString() {
        return name + " (" + city + ", " + state + ")";
    }
}

public class Main {
    public static final int PASS_THRESHOLD = 60;

    public static void main(String[] args) {
        // 직원 목록 생성
        Department hr = new Department("HR");
        Department it = new Department("IT");
        Department sales = new Department("Sales");

        List<Employee> employees = Arrays.asList(
                new Employee("Alice", hr, 50000),
                new Employee("Bob", it, 60000),
                new Employee("Charlie", it, 70000),
                new Employee("David", sales, 45000),
                new Employee("Eve", hr, 55000)
        );

        // 부서별 직원 그룹화
        Map<Department, List<Employee>> byDept = employees.stream()
                .collect(Collectors.groupingBy(Employee::getDepartment));

        byDept.forEach((dept, empList) -> {
            System.out.println(dept.getName() + ": " + empList);
        });

        // 부서별 급여 합계 계산
        Map<Department, Integer> totalByDept = employees.stream()
                .collect(Collectors.groupingBy(Employee::getDepartment,
                        Collectors.summingInt(Employee::getSalary)));

        totalByDept.forEach((dept, totalSalary) -> {
            System.out.println(dept.getName() + " total salary: " + totalSalary);
        });

        // 학생 목록 생성
        List<Student> students = Arrays.asList(
                new Student("John", 85),
                new Student("Jane", 55),
                new Student("Jack", 75),
                new Student("Jill", 45)
        );

        // 합격 및 불합격 학생 분류
        Map<Boolean, List<Student>> passingFailing = students.stream()
                .collect(Collectors.partitioningBy(s -> s.getGrade() >= PASS_THRESHOLD));

        System.out.println("Passing students: " + passingFailing.get(true));
        System.out.println("Failing students: " + passingFailing.get(false));

        // 사람 목록 생성
        Stream<Person> personStream = Stream.of(
                new Person("Tom", "New York", "NY"),
                new Person("Jerry", "Los Angeles", "CA"),
                new Person("Spike", "New York", "NY"),
                new Person("Tyke", "San Francisco", "CA")
        );

        // 도시별 사람 분류
        Map<String, List<Person>> peopleByCity = personStream.collect(Collectors.groupingBy(Person::getCity));

        peopleByCity.forEach((city, people) -> {
            System.out.println(city + ": " + people);
        });

        // 사람 목록 재생성 (stream은 1회용이므로 다시 생성)
        personStream = Stream.of(
                new Person("Tom", "New York", "NY"),
                new Person("Jerry", "Los Angeles", "CA"),
                new Person("Spike", "New York", "NY"),
                new Person("Tyke", "San Francisco", "CA")
        );

        // 주 및 도시별 사람 분류
        Map<String, Map<String, List<Person>>> peopleByStateAndCity = personStream.collect(
                Collectors.groupingBy(Person::getState, Collectors.groupingBy(Person::getCity)));

        peopleByStateAndCity.forEach((state, cityMap) -> {
            System.out.println(state + ": " + cityMap);
        });
    }
}

 

 

Map Interface Basic Operations

Map의 기본 연산들(put, get, containsKey, containsValue, size, isEmpty)은 Hashtable에서의 동작과 정확히 동일합니다. 다음 프로그램은 아규먼트 리스트에서 발견된 단어의 빈도 테이블을 생성합니다. 빈도 표는 각 단어를 아규먼트 리스트에서 발생한 횟수에 매핑합니다.

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 문장의 두 번째 아규먼트입니다. 이 아규먼트는 조건식으로, 단어가 처음 등장한 경우 빈도를 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}

 

빈도 테이블을 알파벳 순서로 보고 싶다고 가정해 봅시다. 해야 할 일은 Map의 구현 타입을 HashMap에서 TreeMap으로 변경하는 것뿐입니다. 이 네 글자를 변경하면 프로그램은

import java.util.*;

public class Freq {
    public static void main(String[] args) {
        Map<String, Integer> m = new TreeMap<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);
    }
}

 

동일한 커맨드라인에서 다음과 같은 출력을 생성합니다.

8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

 

마찬가지로, Map의 구현 타입을 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 메서드에 대한 요구사항을 강화하여 두 Map 객체가 구현 타입에 관계없이 논리적 동등성을 비교할 수 있도록 합니다. 두 Map 인스턴스는 동일한 키-값 매핑을 나타내는 경우 동등합니다.

관례에 따라, 모든 범용 Map 구현은 Map 객체를 아규먼트로 받아 지정된 Map의 모든 키-값 매핑을 포함하도록 새로운 Map을 초기화하는 생성자를 제공합니다. 이 standard Map conversion 생성자는 standard Collection 생성자와 완전히 유사합니다: 이를 통해 호출자는 다른 Map의 구현 타입에 관계없이, 원하는 구현 타입의 Map을 생성하고 초기값으로 다른 Map의 모든 매핑을 포함시킬 수 있습니다. 예를 들어, m이라는 이름의 Map이 있다고 가정해봅시다. 다음 싱글 라인의 코드는 m과 동일한 키-값 매핑을 처음에 포함하는 새로운 HashMap을 생성합니다.

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

 

String 클래스 hashCode

String 클래스의 hashCode 메서드에서, 해시코드를 생성하는 statement에서 10진수 31을 특정 로컬 변수에 곱하는 코드[h = 31 * h + (v & 0xff);]가 있는 이유는, 해시 코드를 계산할 때 더 좋은 분포를 만들기 위해서입니다. 이 관행은 자바의 String 클래스에서 해시 코드를 계산할 때 사용되는 방법과 유사합니다. 31을 곱하는 이유는 다음과 같은 몇 가지 이유가 있습니다:

1. 소수의 특성: 31은 소수(prime number)이기 때문에, 해시 함수가 충돌 없이 더 균등하게 분포된 해시 값을 생성하는 데 도움을 줍니다. 소수를 사용하면 해시 충돌이 줄어들고, 해시 테이블에서 키의 분포가 고르게 되어 성능이 향상됩니다.

2. 곱셈과 shift의 최적화: 31은 2의 거듭제곱에 가까운 수(32-1)이기 때문에, 컴파일러가 곱셈 연산을 쉬프트 연산으로 최적화할 수 있습니다. 이는 성능 향상에 기여할 수 있습니다.

  ⦁ 예: 31 * h는 (h << 5) - h로 변환될 수 있습니다. 이 계산은 5비트 왼쪽으로 이동하고 원래 값을 뺀 것과 같습니다.

     (십진수 31은 이진수 0001 1111)

3. 효율적인 분포: 31을 사용한 곱셈은 비트 분포를 다양화하여 해시 코드가 더 잘 분산되도록 합니다. 이는 특히 문자열이나 배열과 같은 데이터에서 각 요소의 위치가 해시 값에 고르게 영향을 미치도록 돕습니다.

아래는 String 클래스의 주어진 코드의 해시 계산 과정을 설명하는 예시입니다:

public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

이 함수는 byte 배열의 해시 코드를 계산합니다. 배열의 각 요소에 대해 다음을 수행합니다:
1. 초기 해시 값 h는 0으로 시작합니다.
2. 배열의 각 바이트 v에 대해:
  ⦁ h 값을 31로 곱합니다.
  ⦁ 바이트 값을 0xFF와 AND 연산을 하여 unsigned 바이트 값으로 만듭니다.
  ⦁ 이를 h에 더합니다.
3. 최종 해시 값을 반환합니다.

sungwon이라는 문자열에 대한 해시 코드를 생성하는 과정을 설명하겠습니다. 이 과정은 문자열의 각 문자에 대해 동일한 방식으로 해시 코드를 계산합니다. 자바에서 문자열 해시 코드는 다음과 같이 계산됩니다:

위의 hashCode 메서드는 문자열의 각 문자의 유니코드 값을 이용해 해시 코드를 계산합니다. 이제 sungwon 문자열을 예로 들어 해시 코드 생성 과정을 단계별로 설명하겠습니다.

문자열 "sungwon" 해시 코드 계산

1. 초기 해시 값 h는 0으로 시작합니다.
2. 문자열의 각 문자에 대해 다음을 수행합니다:
   ⦁  h = 31 * h + value[i]

각 문자의 유니코드 값은 다음과 같습니다:
⦁  s = 115
⦁  u = 117
⦁  n = 110
⦁  g = 103
⦁  w = 119
⦁  o = 111
⦁  n = 110

이제 각 단계별로 해시 값을 계산해 보겠습니다:
1. 문자 's':
  ⦁ h = 31 * 0 + 115 = 115
2. 문자 'u':
  ⦁ h = 31 * 115 + 117 = 3562
3. 문자 'n':
  ⦁ h = 31 * 3562 + 110 = 110532
4. 문자 'g':
  ⦁ h = 31 * 110532 + 103 = 3426595
5. 문자 'w':
  ⦁ h = 31 * 3426595 + 119 = 106224564
6. 문자 'o':
  ⦁ h = 31 * 106224564 + 111 = 3292961595
7. 문자 'n':
  ⦁ h = 31 * 3292961595 + 110 = 102081809555

최종 해시 값은 102081809555입니다. 

하지만 실제 자바에서는 이 값이 32비트 정수로 변환되어야 합니다. 자바의 int 자료형은 32비트이기 때문에 최종 해시 값은 다음과 같이 변환됩니다:

(int) 102081809555

32비트의 범위를 넘는 값은 오버플로우되어 특정 비트만 남게 됩니다. 따라서 최종 해시 코드는 음수로 변환될 수 있습니다. 이 예제에서는 최종 해시 값이 32비트 범위를 넘어섰기 때문에 실제 값은 다음과 같이 변환됩니다:

(int) 102081809555 = -1321595653

따라서 sungwon 문자열의 해시 코드는 -1321595653입니다. 

따라서 31을 곱하는 것은 해시 코드의 충돌을 줄이고 더 고르게 분포된 해시 값을 생성하여 데이터 구조의 성능을 향상시키기 위한 것입니다.

 

Map Interface Bulk Operations

clear 연산은 예상대로 모든 매핑을 Map에서 제거합니다. putAll 연산은 Collection 인터페이스의 addAll 연산의 Map 버전입니다. 한 Map을 다른 Map에 덤프하는 명백한 용도 외에도, 더 미묘한 두 번째 용도가 있습니다. Map이 attribute-value 쌍의 컬렉션을 나타내는 데 사용된다고 가정해 봅시다. putAll 연산은 Map conversion 생성자와 결합하여 디폴트 값을 사용하여 속성(attribute) 맵을 생성하는 깔끔한 방법을 제공합니다. 다음은 이 기법을 보여주는 정적 팩토리 메서드입니다.

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 메서드는 Map을 다음 세 가지 방법으로 Collection으로 볼 수 있게 해줍니다:
▪ keySet — Map에 포함된 키의 집합(Set).
▪ values — Map에 포함된 값의 컬렉션(Collection). 이 컬렉션은 집합(Set)이 아닌데, 그 이유는 여러 키가 동일한 값에 매핑될 수 있기 때문입니다.
▪ entrySet — Map에 포함된 키-값 쌍의 집합(Set). Map 인터페이스는 이 집합의 요소 타입인 Map.Entry라는 작은 중첩 인터페이스를 제공합니다.

 

컬렉션 뷰는 Map을 반복(iterate)하는 유일한 방법을 제공합니다. 다음 예제는 for-each 구조를 사용하여 Map의 키를 반복하는 표준 관용 코드를 보여줍니다:

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();

 

값을 반복(iterate)하는 관용 코드는 유사합니다. 다음은 키-값 쌍을 반복하는 관용 코드입니다.

for (Map.Entry<KeyType, ValType> e : m.entrySet())
    System.out.println(e.getKey() + ": " + e.getValue());

 

처음에는 많은 사람들이 이러한 관용 코드가 느릴 것이라고 걱정합니다. 왜냐하면 Map이 컬렉션 뷰 연산이 호출될 때마다 새로운 Collection 인스턴스를 생성해야 한다고 생각하기 때문입니다. 걱정하지 마세요: Map은 주어진 컬렉션 뷰에 대해 요청할 때마다 항상 동일한 객체를 반환할 수 있습니다. 이것이 바로 java.util의 모든 Map 구현에서 하는 일입니다.

세 가지 컬렉션 뷰 모두에서 Iterator의 remove 작업을 호출하면 지원 맵이 처음부터 엘리먼트 제거를 지원한다는 가정 하에 지원 맵에서 관련 엔트리가 제거됩니다. 이는 앞의 필터링 관용 코드로 설명됩니다.

entrySet 뷰를 사용하면, 반복 중에 Map.Entry의 setValue 메서드를 호출하여 키에 연관된 값을 변경할 수도 있습니다. (다시 말하지만, Map이 처음부터 값 수정을 지원한다고 가정) 반복 중에 Map을 수정하는 유일한 안전한 방법은 이러한 방법뿐입니다. 반복이 진행되는 동안 다른 방법으로 기본 Map이 수정되면 그 동작은 지정되지 않습니다.

컬렉션 뷰는 다양한 형태의 엘리먼트 제거를 지원합니다 — remove, removeAll, retainAll, clear 연산뿐만 아니라 Iterator.remove 연산도 지원합니다. (역시, 백업 Map이 엘리먼 제거를 지원해야 합니다.)

컬렉션 뷰는 어떠한 상황에서도 엘리먼트 추가를 지원하지 않습니다. 이는 keySet 및 values 뷰의 경우 의미가 없으며, entrySet 뷰의 경우에도 불필요합니다. 기본 Map의 put 및 putAll 메서드가 동일한 기능을 제공하기 때문입니다.

 

예제

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class MapViewExample {

    public static void main(String[] args) {
        // Sample map creation
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);
        map.put("three", 3);
        map.put("four", 4);

        // 1. Iterating through keys using keySet
        System.out.println("Iterating through keys:");
        for (String key : map.keySet()) {
            System.out.println(key);
        }

        // 2. Filtering map based on some property of its keys using iterator
        System.out.println("\nFiltering keys and removing those which contain 'o':");
        for (Iterator<String> it = map.keySet().iterator(); it.hasNext(); ) {
            if (it.next().contains("o")) {
                it.remove();
            }
        }

        // 3. Iterating through values using values view
        System.out.println("\nIterating through values:");
        for (Integer value : map.values()) {
            System.out.println(value);
        }

        // Adding some elements back for the next example
        map.put("one", 1);
        map.put("four", 4);

        // 4. Iterating through key-value pairs using entrySet
        System.out.println("\nIterating through key-value pairs:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 5. Modifying values during iteration
        System.out.println("\nModifying values during iteration:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getKey().equals("one")) {
                entry.setValue(10);
            }
        }

        // Display the modified map
        System.out.println("\nModified map:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // 6. Removing elements using collection view methods
        System.out.println("\nRemoving elements using collection view methods:");
        map.keySet().removeIf(key -> key.contains("t"));

        // Display the final map
        System.out.println("\nFinal map:");
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

 

Fancy[멋진] Uses of Collection Views: Map Algebra[대수]

컬렉션 뷰에 적용된 대량 작업(containsAll, removeAll, retainAll)은 놀랍도록 강력한 도구입니다. 먼저, 한 Map이 다른 Map의 서브맵인지, 즉 첫 번째 Map이 두 번째 Map의 모든 키-값 매핑을 포함하는지 알고 싶다고 가정해 봅시다. 다음 관용구가 그 일을 해냅니다.

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

비슷한 방식으로, 두 Map 객체가 동일한 키에 대한 매핑을 모두 포함하는지 알고 싶다고 가정해 봅시다.

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;
}

두 Map 객체에 공통으로 포함된 모든 키를 알고 싶다고 가정해 봅시다.

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

유사한 관용 코드를 사용하여 공통 값을 얻을 수 있습니다.

지금까지 제시된 모든 관용 코드는 비파괴적입니다. 즉, 기본 Map을 수정하지 않습니다. 여기 몇 가지 수정하는 예제가 있습니다. 한 Map이 다른 Map과 공통으로 가진 모든 키-값 쌍을 제거하고 싶다고 가정해 봅시다.

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

 

다른 Map에 매핑된 키를 한 Map에서 모두 제거하고 싶다고 가정해 봅시다.

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

같은 대량 작업에서 키와 값을 혼합하면 어떻게 될까요? 회사의 각 직원을 해당 직원의 관리자에 매핑하는 managers라는 Map이 있다고 가정해 봅시다. 키와 값 객체의 타입에 대해 모호하게 처리할 것입니다. 상관없습니다. 동일하기만 하면 됩니다. 이제 회사에서 "개별 기여자"(비관리자)가 누구인지 알고 싶다고 가정해 봅시다. 다음 코드는 정확히 알고자 하는 것을 알려줍니다.

Set<Employee> individualContributors = new HashSet<Employee>(managers.keySet());
individualContributors.removeAll(managers.values());

Simon이라는 관리자에게 직접 보고하는 모든 직원을 해고하고 싶다고 가정해 봅시다.

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

이 관용 코드는 단일 지정 엘리먼트를 가진 불변 Set을 반환하는 정적 팩토리 메서드인 Collections.singleton을 사용합니다.

이 작업을 수행한 후, 회사에 더 이상 근무하지 않는 관리자를 가진 여러 직원을 보유하게 될 수 있습니다(만약 Simon의 직접 보고자들 중 일부가 관리자였다면). 다음 코드는 더 이상 회사에 근무하지 않는 관리자를 가진 직원을 알려줍니다.

Map<Employee, Employee> m = new HashMap<Employee, Employee>(managers);
m.values().removeAll(managers.keySet());
Set<Employee> slackers = m.keySet();

이 예제는 약간 까다롭습니다. 먼저, Map의 임시 복사본을 만들고, 임시 복사본에서 (관리자) 값이 원본 Map의 키인 모든 항목을 제거합니다. 원본 Map에는 각 직원에 대한 항목이 있으므로, 임시 Map에 남은 항목은 더 이상 직원이 아닌 (관리자) 값을 가진 원본 Map의 모든 항목으로 구성됩니다. 따라서 임시 복사본의 키는 우리가 찾고 있는 직원들을 정확히 나타냅니다.

이 섹션에 포함된 것과 같은 관용 코드는 더 많이 있지만, 모두 나열하는 것은 비실용적이고 지루할 것입니다. 일단 익숙해지면 필요할 때 올바른 것을 생각해내는 것이 그리 어렵지 않습니다.

 

예제

import java.util.*;

public class FancyUsesOfCollectionViews {

    public static void main(String[] args) {
        // Map 설정
        Map<String, Integer> m1 = new HashMap<>();
        m1.put("one", 1);
        m1.put("two", 2);
        m1.put("three", 3);

        Map<String, Integer> m2 = new HashMap<>();
        m2.put("one", 1);
        m2.put("two", 2);

        // 1. m1이 m2의 서브맵인지 확인
        if (m1.entrySet().containsAll(m2.entrySet())) {
            System.out.println("m1은 m2의 서브맵입니다.");
        }

        // 2. 두 Map 객체가 동일한 키를 포함하는지 확인
        if (m1.keySet().equals(m2.keySet())) {
            System.out.println("m1과 m2는 동일한 키를 포함합니다.");
        } else {
            System.out.println("m1과 m2는 동일한 키를 포함하지 않습니다.");
        }

        // 3. 속성-값 쌍의 컬렉션 검증
        Set<String> requiredAttrs = new HashSet<>(Arrays.asList("one", "two"));
        Set<String> permittedAttrs = new HashSet<>(Arrays.asList("one", "two", "three"));

        boolean isValid = validate(m1, requiredAttrs, permittedAttrs);
        System.out.println("속성 맵 유효성: " + isValid);

        // 4. 두 Map 객체에 공통으로 포함된 모든 키 찾기
        Set<String> commonKeys = new HashSet<>(m1.keySet());
        commonKeys.retainAll(m2.keySet());
        System.out.println("공통 키: " + commonKeys);

        // 5. 공통 값을 얻기 (키와 값 혼합 예시)
        // (여기서는 생략)

        // 6. 한 Map이 다른 Map과 공통으로 가진 모든 키-값 쌍 제거
        m1.entrySet().removeAll(m2.entrySet());
        System.out.println("m1에서 m2의 키-값 쌍 제거 후: " + m1);

        // Map 다시 설정
        m1.put("one", 1);
        m1.put("two", 2);
        m1.put("three", 3);

        // 7. 다른 Map에 매핑된 키를 한 Map에서 모두 제거
        m1.keySet().removeAll(m2.keySet());
        System.out.println("m1에서 m2의 키 제거 후: " + m1);

        // 8. 개별 기여자 찾기 (비관리자)
        Map<Employee, Employee> managers = new HashMap<>();
        Employee e1 = new Employee("John");
        Employee e2 = new Employee("Jane");
        Employee e3 = new Employee("Bob");
        Employee e4 = new Employee("Alice");

        managers.put(e1, e2); // John -> Jane
        managers.put(e3, e2); // Bob -> Jane
        managers.put(e2, e4); // Jane -> Alice

        Set<Employee> individualContributors = new HashSet<>(managers.keySet());
        individualContributors.removeAll(managers.values());
        System.out.println("개별 기여자: " + individualContributors);

        // 9. Simon에게 직접 보고하는 모든 직원 해고
        Employee simon = new Employee("Simon");
        managers.put(new Employee("Peter"), simon);
        managers.values().removeAll(Collections.singleton(simon));
        System.out.println("Simon 제거 후 매니저 목록: " + managers);

        // 10. 더 이상 회사에 근무하지 않는 관리자를 가진 직원 찾기
        Map<Employee, Employee> tempManagers = new HashMap<>(managers);
        tempManagers.values().removeAll(managers.keySet());
        Set<Employee> slackers = tempManagers.keySet();
        System.out.println("더 이상 회사에 근무하지 않는 관리자를 가진 직원: " + slackers);
    }

    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<>(requiredAttrs);
            missing.removeAll(attrs);
            System.out.println("Missing attributes: " + missing);
            valid = false;
        }
        if (!permittedAttrs.containsAll(attrs)) {
            Set<K> illegal = new HashSet<>(attrs);
            illegal.removeAll(permittedAttrs);
            System.out.println("Illegal attributes: " + illegal);
            valid = false;
        }
        return valid;
    }

    static class Employee {
        String name;

        Employee(String name) {
            this.name = name;
        }

        @Override
        public String toString() {
            return name;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Employee employee = (Employee) o;
            return Objects.equals(name, employee.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }
    }
}

 

Multimaps

멀티맵은 Map과 유사하지만 각 키를 여러 값에 매핑할 수 있습니다. Java Collections Framework에는 멀티맵에 대한 인터페이스가 포함되어 있지 않은데, 이는 멀티맵이 일반적으로 많이 사용되지 않기 때문입니다. 값을 List 인스턴스로 가지는 Map을 멀티맵으로 사용하는 것은 비교적 간단합니다. 다음 코드 예제에서는 이 기법을 보여줍니다. 이 예제는 한 라인에 하나의 단어(모두 소문자)를 포함하는 단어 리스트를 읽고, 지정된 크기 기준을 충족하는 모든 애너그램 그룹을 출력합니다. 애너그램 그룹은 동일한 글자를 포함하지만 다른 순서로 배열된 단어들의 모임입니다. 프로그램은 커맨드 라인에서 두 개의 아규먼트를 받습니다: (1) 사전 파일의 이름과 (2) 출력할 애너그램 그룹의 최소 크기. 지정된 최소 크기보다 적은 단어를 포함하는 애너그램 그룹은 출력되지 않습니다.

애너그램 그룹을 찾는 표준적인 방법이 있습니다: 사전의 각 단어에 대해, 단어의 글자를 알파벳 순서로 정렬(즉, 단어의 글자를 알파벳 순서로 재배열)하고, 정렬된 단어를 원래 단어에 매핑하여 멀티맵에 엔트리를 추가합니다. 예를 들어, 단어 bad는 abd를 bad에 매핑하는 엔트리를 멀티맵에 추가하게 합니다. 잠시 생각해보면, 주어진 키에 매핑된 모든 단어가 애너그램 그룹을 형성한다는 것을 알 수 있습니다. 멀티맵의 키를 반복하면서 크기 제약 조건을 충족하는 각 애너그램 그룹을 출력하는 것은 간단한 일입니다.

다음 프로그램은 이 기법의 단순한 구현입니다.

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);
    }
}

 

이 프로그램을 173,000개의 단어가 있는 사전 파일과 최소 애너그램 그룹 크기를 8로 설정하여 실행하면 다음과 같은 출력이 생성됩니다.

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에 있습니다. 우리가 사용한 사전 파일은 Public Domain ENABLE 벤치마크 참조 단어 목록에서 유래한 것입니다.

 

Object Ordering

...차후 업데이트...