[Java] Map 인터페이스
Map 인터페이스
Set 인터페이스와 다르게 key와 value를 이용한다.
Collection 인터페이스에 속한 구현체 클래스를 상속받은 구현 클래스 종류
HashMap
키에 대한 해시값을 사용해서 해당 값을 인덱스로 하여 배열을 만든다.
Thread-safe 하지 않다. 그렇기 때문에 Collections.synchronizedMap(new HashMap(…)); 으로 사용하거나
null을 허용한다. 또는 java.util.concurrent 패키지의 ConcurrentHashMap 클래스를 사용할 수 있다.
HashTable
Collection 인터페이스 이전에 나온 HashTable, synchronized를 사용해서 thread-safe 하다.
하위 호환성에 가치를 두기 때문에 HashMap에 비해 변화가 있진 않다.
TreeMap
키값을 가지고 정렬한다. 정렬을 해야 하기 때문에 값을 추가하고 조회하는 게 hashmap 보다 느리다.
데이터를 조회하는 경우 시간 복잡도 o(log n)
Comparable이나 Comparator인터페이스를 구현하기 때문에 값을 비교하고 정렬할 수 있다.
+ 해시값 충돌
HashMap을 사용할 때 서로 다른 입력 값에 대해 같은 출력 값을 내는 상황
왜 일어날까?
접근할 수 있는 index에 비해서 Bucket의 크기가 작기 때문에 해시 충돌이 일어난다.
HashMap 같은 경우 key값으로 vlue를 분류한다. 같은 key값을 가진 value를 저장할 때 해시값 충돌이 발생한다.
Key 값은 int 형 자료형을 사용하고 int형으로 나타낼 수 있는 범위는 2^32이다. 해시맵에 넣을 값의 종류가 2^32을 넘는다면 충돌이 일어날 수 있다.
2^32이 넘지 않더라도 해시값 충돌이 일어날 수 있는데 배열의 크기를 처음부터 2^32으로 선언하는 건 메모리 낭비이기 때문에 계속 일정 수치 이상 배열이 차면 2배씩 확장하는 식으로 늘려간다. 배열의 크기를 처음부터 예상하고 크게 선언하지 않는 한 해시값 충돌이 일어날 수 있다.
*리사이징 : 해시충돌 방지를 위해 배열의 크기를 2배로 늘리기 위해서 기존 배열에 있는 값들을 모두 더 큰 새로운 배열에 할당하는 작업을 거쳐야 한다. 확장하는 임계점은 현재 데이터 개수가 해시 버킷의 개수의 75%가 될 때이다.
-인덱스를 계산할 때 배열의 크기를 넘어가면 안 되기 때문에 해시값 % m(배열의 크기)를 한다. 그렇기에 인덱스는 중복될 수 있다. 해시 충돌 가능성은 1/m
-String이나 pojo를 사용해서 완전한 해시함수를 만들 수 없다.
-hashmap은 index값이 균등하게 분포, 해시 충돌 가능성을 줄이기 위해 보조 해시함수를 사용한다. 그런데 자바 8 이후 보조 해시함수가 간단해졌고 그 이유는 최근 해시 함수는 균등 분포가 잘되게끔 하는 경향이 있어서이다.
-자바 8부터 HashMap버킷에 저장되는 데이터의 단위는 Entry 대신 Node를 사용한다.
해시충돌을 피하기 위한 방법
1. chaining
해시값이 충돌하면 linkedList로 충돌된 key값을 가진 값들을 연결한다.
HashMap은 같은 key값을 가진 버킷의 개수가 6개 이상 늘어나면 treeMap을 사용한다. 시간 복잡도가 줄어들기 때문이다. 처음엔 linkedList -> treemap 으로 사용하는 이유는 뭘까?
treeMap은 저장할 때 key값에 따라 정렬하는 작업이 들어간다. 그래서 linkedlist보다 비교적 느리다. 데이터가 적은 경우에 굳이 정렬 작업을 추가적으로 해야 하는 treeMap보다 데이터를 추가하고 찾는 과정이 linkedList가 충분히 빠르기 때문이다. 하지만 데이터가 많아지는 경우 linkedlist로 계속 데이터를 찾게 되면 오래 걸리기 때문이다.
2. Open Addressing
해시값이 충돌하면 다른 주소값을 사용한다. 그래서 추가적인 메모리를 사용하지 않는다. 하지만 이 방법은 특정 키값들이 한 곳에 몰리는 경우가 발생할 수 있다.
HashMap 같은 경우 값을 삭제하는 경우가 많을 수 있는데 Open Addressing은 데이터를 삭제할 때 효율적이기 어렵다. 왜냐하면
해시값이 충돌된 하나의 key값을 삭제한다면 다음 데이터가 해당 key값을 가지고 참조할 때 정상적으로 값을 반환시켜 주기 위해서 따로 처리를 해야 하기 때문이다.
공통점
둘 모두 worst case O(m)이다.
차이점
Load-fator가 일정 수치보다 높으면 Open Addressing의 한 종류인 linear probing 은 비약적으로 look-up이 느려진다. 하지만 Load-fator가 낮은 경우 chaining보다 linear probing이 더 빠르다. 그 이유는 chaining 은 추가적인 자료구조를 사용하기 때문이다.
Reference.
https://d2.naver.com/helloworld/831311