Map은 키(Key)와 값(Value) 으로 이루어진 Entry객체 데이터를 보관하는 자료구조이다. java.util안에 존재한다.
순서를 유지하지 않는다. Key는 중복을 허용하지 않지만, Value는 가능하다.
해시 맵(HashMap)
Map 인터페이스를 구현한 대표적인 Map 컬렉션이다. Map은 키와 값으로 구성된 Entry객체를 저장하는 구조를 가지고 있는 자료구조이다. 여기서 키와 값은 모두 객체이다. 값은 중복 저장될 수 있지만 키는 중복 저장될 수 없다. 만약 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.
HashMap은 이름 그대로 해싱(Hashing)을 사용하기 때문에 특정 데이터의 저장위치를 해시함수를 통해 바로 알 수 있기 때문에 데이터 추가, 삭제, 특히 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다.(검색)
여기서 해싱은 어떤 키를 특정 계산식(해시함수)에 넣어 나온 결과를 이용해서 값에 접근하는 과정이다.
해시 함수를 통과하여 나온 해시값을 인덱스로 삼아서 테이블에 접근하는 것이다. 해시값에 골고루 분포되도록 만드는 것이 좋은 해시 함수이다. 접근하는 곳에 계속 접근하게 되면 해시 충돌이 발생하게 된다.
해시 충돌은 같은 공간(인덱스)에 서로 다른 값을 저장하려고 할 때 일어나는 일이다. 다른 킷값으로 접근했는데 같은 결과가 나오는 그런 상황을 말한다.
해결 방법
- 개방 주소법(Open Address) - 충돌 발생 시 테이블에서 비어 있는 공간의 해시를 찾아 데이터를 저장하는 방법이다. 그래서 해시와 value가 1:1 관계를 유지한다. 이 비어있는 공간의 탐색 방법에는 3가지 방법이 있다.
- 선형 탐사법(Linear Probing) - 빈공간 순차적 탐사, 충돌 발생 지점 이후의 빈공간 순서대로 탐사, 반복된 충돌 발생시 해당 지점 주변에 데이터가 몰리는 현상이 발생(일차 군집화 문제)),
- 제곱 탐사법(Quadratic Probing) - 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법, 충돌 발생 지점 이후부터 n제곱 간격으로 탐사, 일차 군집화 문제를 어느정도 해결하지만 이차 군집화 문제가 발생할 가능성이 있음)
- 이중 해싱(Double Hashing) - 해시 함수를 이중으로 사용하는 것, 해시1은 최초 해시를 구할 때 사용하고, 해시2는 충돌 발생 시 탐사 이동 간격을 결정할 때 사용하는 것이다. 위 두 방법에 비해 데이터가 고루 분포되지만 시간이 위 두 방법보다 많이걸림)이 있다.
- 분리 연결법(Separate Chaining) - 해시 테이블을 연결리스트로 구성하는 방법이다. 충돌 발생시 테이블의 다른 위치를 찾는 것이 아닌, 연결리스트를 사용하여 해당 테이블에 데이터를 연결한다. 1대1 매칭 방식이 아니라 원하는 값을 찾을 때 상대적으로 위 방법보다 오래 걸린다.
HashMap은 저장공간보다 값이 추가로 들어오면 약 두배로 늘리는데 보통 여기서 과부하가 많이 발생한다. 그렇기에 초기에 저장할 데이터 개수를 알고 있다면 Map의 초기 용량을 지정해주는 것이 좋다.
null key와 null value를 모두 허용한다.
내부적으로 데이터에 접근할 때 동기화를 보장하지 않는다.
HashMap 시간복잡도 ( Big O )
- get : O(1)
- containsKey : O(1)
- next : O(h/n) h는 테이블 용량
- 삽입 : O(1)
- 삭제 : O(1)
- 검색 : O(1)
HashMap 선언 예시
HashMap h1 = new HashMap();
HashMap h2 = new HashMap(4);; // 4=initialCapacity, 초기용량(resize 과부하 고려)
HashMap<String, Integer> h3 = new HashMap<>();; // <>는 앞의 String, Integer과 동일하게 암묵적으로 인정된다.
같이 만들 수 있다.
<> 로 타입을 제한하지 않을 경우, 어떤 타입이든 Key가 될 수 있고, 어떤 타입이든 Value가 될 수 있다.(원시타입은 안됨)
loadFactor는 테이블의 버킷이 얼마나 가득 찼는지 보여주는 수치다.
주로 사용하는 메소드
예시로 사용하는 변수 => HashMap<String, Integer> h1 = new HashMap()
| 메소드 이름 | 사용 예시 | 설명 |
| put | h1.put("apple", 3000); h1.put("banana", 123); |
앞이 key, 뒤가 value로 데이터가 추가된다. key 값이 중복될 경우 덮어쓴다. |
| putIfAbsent | h1.putIfAbsent("apple", 2000); | key가 있으면 그냥 넘어가고, 없으면 만들어주는 것이다. |
| get | h1.get("kiwi"); h1.get("apple"); |
해당 key에 매칭되는 value를 반환한다. 없을경우 null을 반환한다. |
| putAll | h2.putAll(h1); | key, value 자료형이 같은 map을 통째로 복사하는 함수. h2+=h1 같다고 생각하면 된다. |
| size | h1.size(); | map의 크기 반환(한 쌍이 하나) |
| remove | h1.remove("kiwi"); h1.remove("apple"); h1.remove("apple", 3000); |
해당 key에 매칭되는 쌍을 삭제한다. (value값 반환) 없을경우 null을 반환한다.(map은 변화없음) 인자가 2개라면 key, value가 모두 일치하는 데이터를 삭제한다. |
| clear | h1.clear(); | 빈 map으로 만든다. |
| isEmpty | h1.isEmpty(); | 빈 map인지를 boolean으로 반환 |
| containsKey | h1.containsKey("kiwi"); h1.containsKey("apple"); |
map에 해당 key가 있는지를 boolean으로 반환 containsValue()도 있다. |
| keySet | for(String key:map.keySet()){ ... } | list처럼 증가하는 index를 사용할 방법이 없지만 keySet메소드를 이용하여 키를 Set으로 넘겨주어 Map에 존재하는 키를 모두 순회할 수 있다. |
| entrySet | for(String key:map.entrySet()){ ... } | entrySet메소드를 이용하여 key, value쌍인 entry객체를 Set으로 넘겨준다. KeySet은 내부적으로 get을 호출하기에 전체 HashMap 데이터를 순회해야할 경우, EntrySet을 쓰는것이 좋다. |
foreach(람다) 혹은 Iterator로 해당 map을 순회할 수 있다.
같은 객체를 판별하는 코드를 넣고자하여 equals()를 재정의할때 반드시 hashCode()도 다시 정의해주어야한다.
entrySet()은 key와 value 모두가 필요할 경우 사용하며 keySet()은 key 값만 필요할 경우 사용하는데 key값만 받아서 get(key)를 활용하여 value도 출력할 수도 있기에 어떤 메소드를 선택하든지 간에 큰 상관이 없어 대부분 코드가 간단한 keySet을 활용하지만 key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되므로 많은 양의 데이터를 가져와야 한다면 entrySet()이 좋다.(약 20%~200% 성능 저하가 있음)
HashMap과 사용법이 거의 동일한 컬렉션(Collection)에는 Hashtable이 있다. 두 클래스의 차이점은 Thread 관점에서 안전하냐(Hashtable), 안전하지 않은 대신 속도가 빠르냐(HashMap)이다.
다른 특징으로는 HashTable과 유사하지만 동기화가 되지 않고 Null값도 저장이 가능하다.
HashTable과 HashMap 둘다 맵 인터페이스로부터 구현된 클래스이므로 선언방법부터 사용법까지 거의 동일하다. 그래서 다형성을 생각해서 Map m1=ht, Map m2=hm 둘다 가능하다.
synchronizedMap, ConcurrentHashMap을 사용하면 thread-safe하게 HashMap을 사용할 수 있어서 보통 이쪽을 쓴다고 한다.
