Map
- Key와 Value로 이루어진 데이터 집합
- key의 중복은 허용되지 않고 Value의 중복은 허용된다.
- 내부적으로 배열을 이용하기 때문에 빠른 탐색 시간 O(1)
Hash function: 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
Collision
- Map은 버킷의 위치를 정할 때, 객체의 hashCode를 이용 해시 코드의 결과 자료형은 int 형이다.
논리적으로 2^32 보다 많은 객체를 생성할 수 있지만 엄청난 메모리 낭비와 배열과 다르지 않은 구조가 되어버려 해시의 의미가 퇴색된다.
따라서, 실제 HashMap에서는 메모리 절약을 위해 표현해야 할 N의 범위보다 적은 M만큼의 배열을 사용한다. - 1/M 확률로 나눠서 버킷에 들어가니 같은 버킷에 들어가는 충돌이 발생한다.
개방 주소법(Open Addressing)
- 비어있는 해시 테이블의 공간을 활용하는 방법
Linear Probing: 충돌이 h[k]에서 발생할 경우, h[k+1] 확인 -> 비어있지 않을 경우, h[k+2] .. 식으로 확인Quadratic Probing: 해시 저장순서 폭을 제곱으로 저장하는 방식, ex) 충돌이 발생한 경우 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식Double Hashing Probing: 해시된 값을 한번 더 해싱하여 새로운 주소 할당
분리 연결법(Separate Chaining)
- 동일한 버킷의 데이터에 대해
ListorTree자료구조를 이용해서 다음 데이터의 주소를 저장하는 방식 - 리스트의 개수에 따라 자료구조 변경
- 6개 이하인 경우: LinkedList
- 8개 이상인 경우: Tree(RBT)
7이 없는 이유: 각 자료 구조로 넘어가는데 기준이 1이라면 스위칭되는데 비용이 너무 많이 든다.
Map vs Table
| 특징 | Map | Table |
|---|---|---|
| Synchronized | x | o |
| Thread-Safe | x | o |
| Null Key & Null Value | One null key, Any null value | 둘 다 허용 안됨 |
| Performance | 빠름 | 비교 연산 느림 |
※ Thread-Safe: 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제없음을 뜻한다.
ex) 여러 스레드가 깉은 코드를 동시에 실행하더라고 각 스레드에서 출력되는 값이 동일하다.
참고
Positive Thinking