[자료구조] Map과 Map 컬렉션들(HashMap, HashTable, LinkedHashMap)

Map

- Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 key를 통해 value(값)를 얻는다. 예를 들어 easy란 단어의 뜻을 찾기 위해서 사전의 내용을 순차적으로 모두 검색하는 것이 아니라 해당 단어가 있는 곳만을 펼쳐보는 것이다. 

- 순서가 없고, 키(key)-값(value) 쌍으로 이루어져있다. key는 중복불가, value는 중복 가능하다.

- Map은 List와 같이 인터페이스이고, Map 인터페이스를 구현한 Map 컬렉션 프레임워크(자료구조)에 HashMap, LinkedHashMap, TreeMap, HashTable 등이 있다.

 

 

---

HashMap

HashMap은 Map 인터페이스를 구현한 대표적인 Map 컬렉션이다.  Map 인터페이스를 상속하고 있어 Map의 성질을 그대로 가지고 있다. 
HashMap은 이름 그대로 해싱(Hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.
HashMap에서 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대체된다. (키는 동일하므로 유지, value는 최신값으로 변경됨)
HashMap은 해시 함수를 통해 '키'와 '값'이 저장되는 위치를 결정하므로, 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어 있는 위치 또한 관계가 없다. 즉, 코드상으로 순차적으로 key와 value를 넣어도, 실제 HashMap에서는 해당 순서가 지켜지지 않는다. 
HashMap은 저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 추가로 늘리는데 List처럼 저장공간을 한 칸씩 늘리지 않고 약 두배로 늘린다. 여기서 과부하가 많이 발생한다 (그렇기에 초기에 저장할 데이터 개수를 알고 있다면 Map의 초기 용량을 지정해주는 것이 좋다)

 

 

HashMap 생성

HashMap<String,String> map = new HashMap<>(10);//초기 용량(capacity)지정
Map<String, Object> map = new HashMap<>(); // new로 생성할 때 파라미터를 생략가능하다

 

 

 

유지보수를 생각한 HashMap 생성

Map<String, Object> map = new HashMap<String, Object>();
HashMap<String, Object> map = new HashMap<String, Object>();

첫 번째의 Map은 HashMap이 구현하는 인터페이스(map) 라고 생각하면 된다. 단 받는 걸 map으로 받을 뿐이다. 둘다 모두 HashMap을 선언하여 사용할 수 있고, 기능상 차이는 없다. 하지만 유지보수성을 생각했을 때 전자가 더 낫다.
JAVA에는 앞서 살펴 봤듯이 HashMap 외에도 다양한 map 컬렉션이 존재하는데, 모두 Map 인터페이스를 구현하는 구조로 정의되어 있다.
따라서 전자처럼 사용하게 되면 추후에 HashMap이 아닌 다른 Map 종류를 사용해야 하는 상황에서도 좀더 쉽게 코드를 수정하고, 유연하게 대처할 수 있다.
하지만 후자처럼 작성하게 되면 해당 map object는 오직 HashMap에 대한 object만 담을 수 있기 떄문에 전자에 비해 유지보수성이 떨어진다.

Map 값 추가

Map<String, Object> map = new HashMap<String, Object>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");

put으로 값을 추가해준다.

 

Map 값 삭제

map.remove(1); // key값 1 제거
map.clear(); // 모든 값 제거

- remove() : 괄호 안 key값에 해당하는 데이터를 삭제한다.

- clear : 모든 값을 제거한다.

Map 출력

HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"A");
    put(2,"B");
    put(3,"C");
}};

위와 같이 HashMap을 선언했다고 했을 때, 출력 방법은 총 3가지가 있다.

 

1. print로 출력하기

System.out.println(map); //전체 출력 : {1=A, 2=B, 3=C}
System.out.println(map.get(1));		//key값 1의 value : A

{}로 묶어 Map의 전체 key값, value가 출력된다.  

 

2. entrySet()

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

/** 출력 결과
[Key]:1 [Value]:A
[Key]:2 [Value]:B
[Key]:3 [Value]:C
*/

특정 key값의 value를 가져오고 싶다면 get(key)를 사용하면 되고 전체를 출력하려면 entrySet()이나 keySet()메소드를 활용하여 Map의 객체를 반환받은 후 출력하면 된다. entrySet()은 key와 value 모두 필요할 때 사용한다.

 

3. keySet()

/* KeySet() 활용 */
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}

/** 출력 결과
[Key]:1 [Value]:A
[Key]:2 [Value]:B
[Key]:3 [Value]:C
*/

 

---

TreeMap

입력순서는 유지하지 않으나, 입력된 Key(키)데이터에 따라 정렬되어 저장

 

---

LinkedHashMap

LinkedHashMap은 put을 통해 입력된 순서대로 Key가 보장되는 map 컬렉션이다.
map이나 다른 map 컬렉션의 특징이 put을 통해 데이터나 객체를 넣을 때 key의 순서가 지켜지지 않는다는 것이다.
여기서 Map을 순서 있게 만드려면 LinkedHashMap을 사용하면 된다.

LinkedHashMap 선언

Map<String, Object> map = new LinkedHashMap();

 

 

---

HashTable

HashTable은 HashMap과 내부 구조가 동일하다. 키는 중복이 안되지만, 값은 중복을 허용한다.

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

---

HashMap vs HashTable

HashMap	HashTable
- 병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황에 적절 - 하나의 Null key 와 여러개의 Null value 를 저장 가능 (우리가 key 로 null 을 전달하면 haspMap 은 실제 사용할 고유키(= hash) 로 0 를 사용) - 비동기로 동작 - 쓰레드 동기화 기능이 필요없는 경우, HashMap 이 HashTable 보다 빠르다.	- 병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황에 적절 - Null 비허용, 입력 불가능 - 멀티 쓰레드 환경 - 동기화

 

 

---

번외 : Hash Table 시간 복잡도

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.   
빠른 검색 속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.   
각 Key값은 해시함수에 의해 고유한 index를 가지게 되어 바로 접근할 수 있으므로 평균 O(1)의 시간 복잡도로 데이터를 조회한다. 
하지만 index값이 충돌이 발생한 경우 Chanining에 연결된 리스트들까지 검색해야 하므로 최악의 경우 O(N)까지 증가할 수 있다.

 

 

 

 

 

---

참고자료

Map vs HashMap : https://velog.io/@mon99745/Java-Map-HashMap-%EC%A0%95%EB%A6%AC
https://juyoungit.tistory.com/587
자료구조 3가지 차이(List, Set, Map) : https://velog.io/@heewonim/Java-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Array-List-Map-Set-Stack-Queue
https://mangkyu.tistory.com/102](https://mangkyu.tistory.com/102
Hashmap의 KEY로 NULL이 가능한 이유 : https://www.inflearn.com/questions/723816/map%EC%9D%98-%EA%B0%80%EC%9E%A5-%ED%81%B0-%ED%8A%B9%EC%A7%95%EC%9D%B4-key%EB%8A%94-null%EC%9D%B4-%EC%95%84%EB%8B%88%EB%8B%A4
Hash Table과 시간 복잡도 : https://dev-coco.tistory.com/159](https://dev-coco.tistory.com/159