1. 맵
키를 이용해 연관된 데이터를 빠르게 검색할 수 있는 자료구조
- 키와 값의 매핑 관계를 관리한다
- 키는 유일해야지만 값은 중복 가능하다
- 맵 = 딕셔너리 = 연관 배열
1-1. 맵의 핵심 기능
1-2. 맵의 부가 기능
2. 맵 구현
2-1. 정렬되지 않은 테이블 맵 구현
- UnsortedTableMap : (키, 값) 아이템을 정렬하지 않고 리스트로 관리
키를 찾는 시간이 O(n)으로 간단하지만 비효율적이다
2-2. 해시 테이블
순서 관계가 없는 데이터를 빠르게 검색할 수 있는 동적 집합 관리 데이터 구조
룩업 테이블 : 키와 배열 인덱스가 같은 테이블
문제점 : 키가 정수여야하고 배열의 길이를 넘어가지 않도록 보장해야한다
해시 함수 : 키를 인덱스로 맵핑해준다
해시 테이블
- 키를 값에 매핑하는 데이터 구조
- 해시 함수를 통해 키를 해시 테이블의 인덱스로 맵핑
- 해시 테이블의 크기와 상관없이 한번만 계산하면 인덱스를 구할 수 있다
2-2-1. 해시 함수
-
해시 함수의 목표 : 키를 해시 테이블의 인덱스 범위로 맵핑하는 함수
-
좋은 해시 함수 : 충돌이 적게 발생하고 계산이 빠르고 쉬운 함수
충돌 : 두개 이상의 키가 같은 해시 값을 가져 같은 버킷에 여러 아이템이 맵핑되는 상태
해시 함수의 2 단계
- 해시 코드 : 객체를 임의의 정수로 변환
- 압축 함수 : 임의의 정수를 [0, N-1] 범위로 압축
>> 단계를 나누므로써 해시 테이블의 크기와 무관하게 해시 코드를 만들 수 있다
3. 해시 코드
목표 : 객체를 정수로 변환, 키 충돌 최소화
3-1. 객체의 비트 표현 정수로 해석
- 가장 간단한 방법이지만 해석한 정수 길이가 해시코드 길이보다 길면 사용하기 어렵다
3-2. 해시 코드 길이로 변환
- 객체 비트 표현을 32bit 튜플로 정의해 XOR하여 해결. 단 문자열이나 가변 크기 객체에는 부적합
3-3. 다항식 해시 코드
- (x0, x1, ..., xn−1)을 계수로 갖는 a에 대한 다항식으로 표현
- 비트 표현 튜플의 위치에 따라 영향이 달라진다
a : 오버플로가 발생해도 일부 정보를 유지하도록 선택
3-4. 사이클 시프트 해시 코드
- 다항식 해시 코드의 변형. a의 곱 대식 시프트 + 부분 합을 수행
- 실험적으로 영어 문자는 5비트 시프트가 좋음
4. 압축 함수
해시 코드를 버킷 배열의 인덱스 범위로 만드는 과정. 서로 다른 해시코드의 충돌 최소화 해야함
4-1. 분배 방법
-
i mod N
i = 해시 코드, N = 버킷 배열 크기 -
N이 소수면 해시 값이 잘 분산되고, 소수가 아니면 분포에 패턴이 생겨 충돌 발생
-
N이 소수여도 해시 코드에 pN+q 같은 반복 패턴이 존재하면 충돌 발생 가능
4-2. MAD 방법
-
[(ai + b) mod p] mod N
i = 해시코드, N = 버킷배열 크기, p = N보다 큰 소수, a와 b = [0,p-1] 범위의 양수 난수 -
해시 코드의 반복 패턴이 나타나지 않게 개선한 압축 방법
-
MAD : Multiply-Add-and-Divide
5. 충돌 해결 기법
5-1. 체이닝
각 버킷마다 같은 해시 값을 갖는 아이템을 저장하는 컨테이너를 갖는다
- 최고 성능 : O(n/N(올림))
5-2. 오픈 어드레싱
저장 공간 절약을 위해 테이블 슬롯에 직접 저장. 충돌 해경 방법이 복잡하다
5-3. 선형 탐색
충돌 발생 시 한 칸 씩 이동하면서 빈 슬롯을 찾는다
- 클러스터가 생기기 때문에 속도가 저하되는 문제가 있다
5-4. 제곱 탐색
충돌 발생 시 제곱수인 i^2만큼 떨어진 곳에서 빈 슬롯을 찾는다
- 문제점
i. 이차 클러스터가 생길 수 있다
ii. 버킷배열 크기가 소수가 아니거나 테이블이 50% 이상 채워지면 빈 슬롯을 못찾을 수도 있다.
5-5. 이중 해싱
충돌 발생 시 2차 해시 함수를 선택해 이동할 위치를 정한다. 1,2차 클러스터가 생기지 않게 개선한 방식
5-6. 의사 난수 발생
충돌 발생 시 의사 난수를 발생해서 이동할 위치를 정한다
6. 로드 팩터
각 슬롯에 저장할 아이템 수의 기댓값. λ=n/N. 1보다 작으면 좋고 작은 상수 이내여야한다
로드팩터가 임계치 이상이 되면 해시 테이블의 크기를 늘려 로드팩터를 낮춰야 한다. 최소 2배 이상 늘려주는 것이 좋고, 기본 연산 성능을 보장하기 위해서는 로드팩터를 임계치 이하로 유지하는 것이 중요하다.
6-1. 체이닝의 로드팩터
- 컨테이너 탐색 시간이 O(n)이기 때문에 로드 팩터가 1에 가까워 질수록 충돌이 증가하며 성능이 저하된다
- 로드 팩터가 0.9보다 작은 것이 바람직하다
6-2. 오픈 어드레싱의 로드팩터
- 로드 팩터가 0.5이상이고 1에 가까워질수록 클러스터가 증가한다
- 클러스터가 증가할 수록 탐색 횟수가 증가해 성능이 저하된다
- 선형 탐색의 경우 0.5 미만의 로드팩터, 다른 방식의 경우 2/3 미만의 로드팩터가 바람직하다
7. 재해싱
해시 테이블의 크기가 늘어나면 압충 함수가 달라지기 때문에 재해싱을 수행한다
- 크기 조절을 위해 재해싱에 사용되는 비용은 분할 분석을 통해 추가/삭제 연산에 분산할 수 있다
8. 성능 분석
해시 테이블이 재해싱을 통해 일정 로드팩터를 유지한다는 가정하에 기본 연산의 기대 성능 = O(1)*
- worst case : 모든 아이템이 같은 버킷에 저장
9. 정렬 맵
키를 순서대로 탐색하거나 가장 근접한 키를 찾을 수 있게 만든 맵
- 다음과 같은 연산을 할 수 있다
i. 최소, 최대 키 찾기
ii. 키 k 직전, 직후 키 찾기
iii. 구간 탐색
iv. 작은 값에서 큰 값 순으로 혹은 역순으로 iter
9-1. 정렬 탐색 테이블
- 정렬 맵 중 가장 간단한 형태
- 이진 탐색으로 연산 효율을 올릴 수 있다
9-2. 이진 탐색
- 정렬된 데이터의 구간을 반 씩 나눠서 탐색 하는 방법
- 찾는 키 값이 중간의 값보다 작으면 낮은 쪽으로 크면 높은 쪽으로 재귀적 탐색
- low > high가 되면 데이터가 없다
