[JAVA ] 맵 (Map)

Map은 사전(Dictionary)와 비슷하게 key와 value 쌍으로 데이터를 저장하여 대응관계를 쉽게 표현할 수 있게 해주는 자료형입니다. 맵은 인덱스가 아닌 키를 통해서 값을 얻는다는 특징이 있습니다. Map에서 키와 값은 모두 객체입니다. 값은 중복될 수 있지만, 키는 유일한 값을 가집니다.

 

Map의 종류 중 대표적인 HashMap, LinkedHashMap, TreeMap에 대해 알아보겠습니다.

 

1. HashMap

가장 기본적인 Map 인터페이스의 구현체로 해시 함수를 통해 키와 값이 저장되는 위치를 결정하기 때문에 사용자는 위치를 알 수 없고 삽입 순서와 저장된 위치 또한 관계가 없습니다. 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색할 때 뛰어난 성능을 보입니다.

이미지 출처: https://coding-factory.tistory.com/556

 

💡해싱
임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 해시(Hash)함수라고 합니다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 하며, 이 값은 해시 코드, 해시섬(sum), 체크섬 등으로도 불립니다.

HashMap은 원본 데이터(key) 값을 해시 함수를 통해 해시값으로 바꾸고 해시값을 배열의 인덱스로 하여 그 위치에 데이터를 저장하는 방식을 사용합니다.

해싱 과정에서 키가 다른데 해시함수를 통해 나온 해시 값이 같은 경우가 발생하기도 합니다. 이를 충돌이라고 하며, 이 부분은 아래에서 다시 알아보겠습니다.

 

HashMap을 선언하는 방법은 다음과 같습니다.

HashMap<String,String> map1 = new HashMap<String,String>(); // 기본 선언 (new에서 타입 파라미터 생략가능)
HashMap<String,String> map2 = new HashMap<>(10); //초기 용량 지정 (기본 16)
HashMap<String,String> map3 = new HashMap<>(10, 0.7f); //초기 용량(capacity), 부하 계수(load factor) 지정
HashMap<String,String> map4 = new HashMap<String,String>(){{ //초기값 지정
    put("name","bee");
}};

HashMap은 저장공간보다 값이 더 들어오면 저장공간을 약 두배로 늘리기 때문에 초기에 저장할 데이터의 크기를 아는 경우 초기 용량을 정해주는 것이 좋습니다. 아무것도 적지 않고 선언하는 경우 초기 용량은 16, 부하 계수는 0.75입니다.

 

💡용량은 실제 데이터(값)가 저장되는 Bucket의 수로 초기 용량은 16입니다.

💡부하 계수는 Map의 용량을 늘릴 시기를 결정하는 척도로 기본값은 0.75입니다. 해시 테이블의 항목 수가 임계값(현재 용량 * 부하 계수)를 초과하면 저장된 항목의 해시값을 다시 계산하는 Rehashing 과정을 거쳐 약 2배로 수가 증가한 버킷에 저장됩니다.

 

HashMap에 값을 추가하고 삭제하는 방법은 다음과 같습니다.

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "apple"); // 데이터 추가
map.put(2, "orange");
map.put(3, "grape");

map.put(2, "banana"); // orange -> banana 로 변경

map.remove(1); // key가 1인 요소 삭제
map.clear();  // 전체 삭제

HashMap에 키가 같은 값을 저장하면 기존 값이 새로운 값으로 변경됩니다.

 

HashMap을 출력하는 방법은 다음과 같습니다.

HashMap<Integer, String> map = new HashMap<>({{
    put(1, "apple");
    put(2, "banana");
    put(3, "grape");
}});

System.out.println(map.get(1)); // key를 사용하여 값 얻기 (출력: apple)


// entrySet() 사용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

// 출력
// Key: 1, Value: apple
// Key: 2, Value: banana
// Key: 3, Value: grape


// keySet() 사용
for (Integer key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

// 출력
// Key: 1, Value: apple
// Key: 2, Value: banana
// Key: 3, Value: grape


// Iterator 사용
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

keySet()에서 key를 받아 get(key)로 값을 얻을 수도 있지만, value를 찾는 과정에 시간이 많이 소모되므로 많은 양의 데이터를 가지고 올 때는 entrySet()을 쓰는 것이 좋다고 합니다.

반복문을 사용하지 않고 Iterator를 사용하여 Map 전체 요소를 출력할 수 있습니다.

 

HashTable

병렬 처리로 동기화를 고려해야 하는 상황에서 사용할 수 있으며, 키 값에 Null을 허용하지 않습니다. HashMap은 병렬 처리를 하지 않는 상황에 사용하며 Null 값을 허용한다는 차이가 있습니다.

 

HashSet

Set은 중복이 없이 데이터를 저장하는 자료구조로 객체 형태의 key 값만 받아서 내부적으로는 HashMap 구조로 데이터를 저장합니다. HashMap으로 데이터를 저장할 때 주어진 key말고 value가 필요한데 이때 PRESENT라는 더미 오브젝트가 저장됩니다. 내부 구조를 그림으로 살펴보면 다음과 같습니다.

---

충돌(Collision)

서로 다른 문자열이 해시함수를 통해 Hash 한 결과가 같은 경우(중복되는 경우)를 충돌이라고 하며, 이를 해결할 수 있는 방법은 다음과 같습니다.

 

✔️Separate Chaining

인덱스 충돌이 나는 경우 인덱스가 가리키고 있는 Linked List에 노드를 추가하여 값을 삽입하는 방식으로 해시 값이 같은 데이터끼리는 서로 연결된 Linked List로 관리하는 방식입니다.

이미지 출처: https://en.wikipedia.org/wiki/Hash_table

데이터를 탐색할 때는 키에 대한 인덱스가 가리키고 있는 Linked list를 선형 검색하여, 해당 키에 대한 데이터를 반환합니다. 삭제하는 것도 비슷하게, 키에 대한 인덱스가 가리키고 있는 Linked list에서, 그 노드를 삭제합니다.

이 방식은 JDK 내부에서도 사용하고 있는 충돌 처리 방식입니다. JDK에서는 인덱스가 같은 데이터가 6개 이하이면 Linked List를 사용하고 8개 이상이면 Tree(Red-Black Tree)를 사용합니다. Tree를 사용하게 되면 get() 메소드 호출에 대한 기댓값이 N/M 에서 E(log⁡〖N/M〗)로 향상됩니다.

 

✔️Open Addressing

이 방법은 인덱스에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용합니다. 따라서 Separate chaining방식에 비해서 메모리를 덜 사용하지만, 키를 통해 나온 인덱스 위치에 알맞은 값이 저장되어 있지 않을 수 있습니다.

---

2. LinkedHashMap

입력된 순서대로 데이터가 출력되는 특징을 가집니다. 순서를 유지하기 위해 이중 연결 리스트 Doubly Linked List를 사용하여 FIFO (First In First Out) 구조로 데이터를 저장합니다. 사용법은 HashMap과 동일합니다.

---

3. TreeMap

입력된 키의 sort 순으로 데이터가 출력되는 특징을 가집니다. 동기화 처리가 되어 있으며, HashMap과 다르게 Key 값에 Null을 허용하지 않습니다. 내부적으로 RedBlack Tree로 저장되며, 키값에 대한 Compartor 구현으로 정렬 순서를 바꿀수 있습니다.

---

 

참고

• recordsoflife.tistory.com/205
• hee96-story.tistory.com/48
• github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#hash-table
• codingdog.tistory.com/entry/java-hashset-%EC%96%B4%EB%96%BB%EA%B2%8C-%EA%B5%AC%ED%98%84%EC%9D%B4-%EB%90%98%EC%96%B4-%EC%9E%88%EC%9D%84%EA%B9%8C%EC%9A%94
• d2.naver.com/helloworld/831311