Map이란?
Map은 Key와 Value를 가진 데이터를 저장하는데 사용되는 인터페이스이다. Map 인터페이스 만으로는 데이터를 보유할 수 없지만, 해당 구현 클래스의 객체를 생성한 다음 Map 참조를 이용하여 객체를 보유할 수 있다.
Map의 구현체로는 HashTable, HashMap, TreeMap, LinkedHashMap가 있다.
순서는 유지되지 않으며, 키의 중복을 허용하지 않는다.
import java.util.HashMap;
import java.util.Map;public class SimpleTesting{
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
System.out.println(map);
}
}
출력
{One=1, Two=2, Three=3}
HashMap이란?
Map 인터페이스를 구현한 Class로서, key와 value의 쌍으로 이루어져 있다.
키 객체의 해시 값을 버킷에 저장하는데, 이때 해시 코드의 결과 자료형은 int이다.
하지만 2^32보다 더 많은 객체를 생성할 수 있지만 메모리를 절약하기 위해 표현해야 할 N의 범위보다 적은 M만큼의 배열을 사용한다.
그렇다보니 같은 버켓에 들어갈 확률이 존재하게 되고, 이를 충돌이라 한다.
이 충돌을 해결하기 위한 대표적인 방법으로 개방 주소법과 분리 연결법이 있다.
개방 주소법(Open Addressing)이란?
추가적인 메모리를 사용하는 chaining 방식과는 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다.
개방 주소법을 구현하기 위한 대표적인 3가지 방법은 아래와 같다.
1. Linear Probing: 만약 충돌이 h[k]에서 난다면 h[k + 1]이 비어있는 확인하고 비어 있지 않다면 h[k + 2] . . . 식으로 계속 확인하는 방법이다.
2. Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 처음 충돌이 발생한 경우 1만큼 이동하고, 계속 충돌이 발생하면 2^2, 2^3칸씩 이동하는 방식이다.
3. Double Hashing Probing: 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하는 방식이다.
분리 연결법(Seperate Chaining)이란?
동일한 버킷의 데이터에 대해 리스트나 트리 자료구조를 이용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다.
충돌이 발생하면 다음 노드로 연결하게 된다. 충돌이 많이 발생하여 리스트의 형태로 계속 데이터가 쌓인 경우 시간 복잡도가 O(n)으로 나빠지게 된다.
따라서, Java8의 HashMap은 리스트의 개수가 8개 이상이 되면 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현한다.
개방 주소법과 분리 연결법의 비교
개방 주소법은 분리 연결법에 비해 연속된 공간에 데이터를 저장하므로 캐시 효율이 높다. 데이터의 개수가 적은 경우 개방 주소법이 성능이 더 좋다.
하지만, 데이터의 개수가 많아지면 개방 주소법의 성능은 떨어지게 된다.
해시 코드란?
객체를 식별하는 하나의 정수를 말한다. Object의 hashCode() 메소드는 객체의 메모리 번지를 이용해 해시코드를 만들어 리턴하기 때문에 객체마다 다른 값을 가지고 있다.
Reference
https://devlog-wjdrbs96.tistory.com/249
