학교에서 진행되는 자료구조 수업을 듣고 중요한 부분 위주로 정리하였습니다. 내용 상에 오류가 있다면 댓글로 피드백 부탁드립니다!

map

• 탐색 가능한(searchable) entry(key, value로 이루어지는 pair)의 묶음(collection)으로 정의
• opeartion: 탐색(search), 삽입(insertion), 삭제(deletion). key에 기반
• 각각의 key는 반드시 unique하다 (똑같은 key를 가진 entry가 존재하지 않는다).
• key가 entry를 저장하게 될 공간을 결정하여 associative store라는 이름으로도 부른다.
• 종류 : list-based, hash table

list-based map

• unsorted, node list로 구현한다.
• 데이터를 탐색하기 위해 linear search algorithm을 사용한다.
  • linear search: 원하고자 하는 데이터를 찾기 위해 순차적으로 확인하는 탐색
• operation: get, remove, put
• performance: O(n)
• 구현하기 쉬우나 데이터 개수가 적을때만 효율적이다.

hash table

• entry를 저장하기 위한 주소로 key를 활용한다.
• performance: 대부분 O(1) (예외: collisiion으이 발생하는 경우)
• 구성 요소: bucket array, hash functions

hash function 만드는 방법

다음의 두가지 단계가 필요하다.

• hash code generation(생성): key와 integer를 mapping
• hash code compression(압축): 생성된 integer를 bucket array의 index와 mapping

generation methods

• key의 type에 따라 결정된다.

1. object

• object끼리는 메모리 주소가 같을 수 없다는 점을 이용하여 object가 저장된 메모리의 주소를 정수값으로 변환하여 사용한다.

2. number

type에 따라 나뉜다.

int: hash code의 값으로 숫자를 그대로 사용한다.

그 외(byte, float, double, ...):

• integer casting(int보다 메모리를 적게, 또는 같게 쓰는 type)

  • byte, short : int로 type casting
  • float : 소수 부분을 정수로 올림 Float.floatIntToBits(x)

• component summation(int보다 메모리를 많이 쓰는 type)

  고정된 길이(int type의 길이만큼)로 key의 비트를 잘라서 만들어진 것을 component라 한다. overflow를 무시하고 component끼리 더하여 합을 구한다.

  문자열에도 사용할 수 있으나 비효율적인 방법이다. 문자 한 바이트를 component로 하여 더할 수 있다. 예를 들어 stop, tops, spot은 단어에 쓰이는 알파벳이 동일하여 collision이 발생한다.

3. string

• polynomial accumulation
  문자열을 k개의 문자 sequence로 보자. 다음과 같은 다항식의 결과를 hash code로 사용한다. 이 때 $a_n$은 상수이고 각 문자가 $x_n$이다.

  $h = a_{k-1}x_0+a_{k-2}x_1+\dots+a_0x_{k-1}$

  성능: 5000개의 영단어에 대하여 a = 33, 37, 39, 41로 두고 테스트한 결과 7번의 충돌 발생 -> 0.014%의 collision 발생 확률
  

• cyclic shift

  number component summation과 비슷하나 각 덧셈이 발생할 때마다 비트 자리올림을 발생시킨다. key를 고정된 길이(int 길이)로 분할하고 이것을 component라 부르자. component를 더하고 5 bits left shift를 하는 과정을 반복한다. 오버플로우되는 부분은 오른쪽 비트로 다시 옮겨서 채운다.

  코드

  h = (h << 5) | (h >>> 27)
  h += (int) s.charAt(i)

  성능: polynomial accumulation과 동일한 실험 -> 0.016%의 collision 발생 확률

compression methods

division method

• N은 bucket의 사이즈이다.
• n은 key의 개수이다.
• x는 압축하고자 하는 key의 값이다.
  $h(x) = x \mod N$
• N은 소수여야지 효율적이다.
• 단순하지만 잦은 collision이 발생한다.

MAD(multiply, add and divide) method

collision을 줄이기 위하여 division method를 개선하였다.
$h(x) = ((ax + b) \mod p) \mod N$

• p는 N보다 큰 소수이다.
• a, b는 [0, p-1] 구간에서 선택된 임의의 정수이다.

Collision Handling

• Bucket array의 크기는 한정적
• bucket array의 길이보다 데이터의 개수가 많아지면 collision은 필연적으로 발생

Seperate Chaining

• collision이 생긴 entry를 List-based map에 저장
  A[h(k1)] = M1 => M1.get(k1)
• 구현하기 쉬우나 list-based map을 만들기 위한 추가적인 메모리 필요
• 메모리 절약법
  • 빈 bucket을 null로 놓기
  • 하나의 entry가 들어갈 경우에는 list 대신 entry 자체를 bucket에 넣기
• operation: get, put, remove

Seperate Chaining의 성능 분석

• 각각의 bucket에는 평균적으로 n/N개의 데이터가 저장된다
  그러므로, get/put/remove operation은 시간복잡도 O(n/N)을 갖는다.
• 일반적으로 Bucket에 들어가는 list의 크기를 상수로 고정하여 사용
  O(n/N) <= O(c) = O(1)

Open Addressing

• 추가적인 자료구조를 사용하지 않고 Bucket Array cell에 충돌이 생긴 데이터를 저장
• 더 복잡한 구조가 형성된다.

Linear probing

A[h(x)]에 데이터가 있으면,
try A[h(x) + 1 mod N]
Then A[h(x) + 2 mod N]
Then A[h(x) + 3 mod N]
...

• 한계
  • Cluster(뭉침)의 문제가 발생할 확률이 높아진다.
  • Colisiion을 점점 늘려나감 => 더 긴 probe가 가 만들어짐
  • Consecutive cell inspection을 통하여 만들어진 연속적인 데이터: probe

Search with linear probing

• cell h(k)에서 시작
• 다음 조건이 만족될 때까지 위치를 probe(탐사)함
  • k를 가진 entry를 찾음(성공)
  • 비워진 cell 발견(실패)
  • 모든 cell을 탐사함(실패)

Update with linear probing

• remove(k)

  • map이 비어있을 경우 exception 발생
  • n <- n-1
  • cell을 비움
  • return v or return null

• put(k, v)

  • map이 가득 차있을 경우 exception 발생(k를 찾지 못했을 경우)
  • k가 발견될 경우 => e를 v로 교체
  • 빈 방이 발견될 경우 => k와 v를 빈 방에 저장하고 n <- n+1로 업데이트

Quadratic probing

• A[(h(k) + j^2) mod N]
  (j >= 1인 정수이고 각 시도마다 j의 값을 1씩 늘린다.)
• Secondary clustering: 부분부분 작은 cluster가 생기는 문제가 발생할 수 있다.
• map.size() >= N/2라면 빈 공간이 있음에도 불구하고 찾지 못하는 상황이 발생할 수 있다.

Double Hashing

제 2의 해쉬함수 h’(k) 를 만든다.

• A[(h(k) + j * h’(k)) mod N], where 1 <= j <= n-1
• h’(k)는 0번째 index에 값을 가지면 안된다.
• $h’(k) = q - (k mod q)$ where a prime number q < N

Load Factor of Hash Table

n entries, bucket array of capacity N
Load factor λ는 다음과 같이 정의된다.

$λ = n / N$
$λ > 1$ : 저장해야할 데이터 개수가 bucket보다 커짐 => collision 반드시 발생
$λ < 1$일 경우 좋은 성능을 낼 수 있음, 그러나 메모리는 한정적이라 여러번의 실험과 경험 통해 살펴보니 일정한 값 이내로 유지하는게 좋다는 것이 밝혀짐

• seperate chaining: keep λ < 0.9
• open addressing: keep λ < 0.5
  open addressing은 직접 arraycell에 데이터 저장하기 때문에 seperate chainng보다 상한선이 더 작은게 좋음

Rehashing

• λ가 threshold를 넘어설 경우
  낮춰주는 것이 필요하다 => 분모 늘림 => bucket array의 크기를 늘림=> growable array를 사용하여 2배만큼 늘려줌(N => 2N)
  $h(k) = k \mod 2N$
• 변경된 hash 함수로 다시 기존에 있는 데이터를 다시 한번 저장을 해주는 과정 필요(reinsert every entry)