해시테이블(Hash Table)

📢  해시테이블(Hash Table)

• (키-주소) 매핑에 의해 구현된 사전 ADT
  👉 예 : 컴파일러의 심볼 테이블, 환경변수들의 레지스토리

• 해시테이블 = 버켓 배열 + 해시함수
  👉 항목들의 키를 주소(즉, 배열첨자)로 매핑함으로서 1차원 배열에 사전 항목들을 저장한다.
• 성능
  👉 탐색,삽입,삭제 : 최악의 경우 O(N), 그러나 기대시간 O(1)

 

📢  버켓배열(Bucket Array)

해시테이블 버켓배열 예 ( M = 13 인 경우 )

• 키가 유일한 정수며 [0...M-1] 범위에 잘 분포되어 있다면, 해시테이블에서의 탐색, 삽입, 삭제에 O(1) 소요

• 두 가지 중요한 결함
  
  👉 O(N) 공간을 사용하므로, M이 N에 비해 매우 크면, 공간 낭비
  👉 키들이 [0...M-1] 범위 내의 유일한 정수여야 하지만, 이는 종종 비현실적
• 설계 목표
  
  👉 그러므로 해시테이블 데이터구조를 정의할 때는, 키를 [0...M-1] 범위 내의 정수로 매핑하는 좋은 방식과
  버켓배열을 구성해야 한다.

 

📢  해시함수 및 해시테이블

• 해시함수(Hash Function), h :  주어진 형의 키를 고정범위 [0...M-1]로 매핑
  
  👉 예 : h(x) = x % M ( h는 정수 키 x에 대한 해시함수 )
• 정수 h(x) : 키 x의 해시값(Hash value)
• 주어진 키 형의 해시테이블은 다음 두 가지로 구성
  
  👉 해시함수 h
  👉 크기 M의 배열(테이블이라 부른다.)
• 사전을 해시테이블로 구현할 때, 목표는 항목(k,e)를 첨자 i = h(k)에 저장하는 것
• 해시함수(Hash Function)는 보통 두 함수의 복합체로 명세한다.
  
  👉 해시코드맵(Hash code map) h1 : keys -> integers
  👉 압축맵(Compression map) h2 : integers -> [0...M-1]
• 먼저 해시코드맵을 적용하고, 그 결과에 압축맵을 적용한다. 즉,
  
  👉 h(k) = h2(h1(k))
• 좋은 해시함수가 되기 위한 조건
  
  👉 키들을 외견상 무작위하게(Random) 분산시켜야 한다.
  👉 계산이 빠르고 쉬워야 한다 ( 가능하면 상수시간 )

해시함수 예 

 

📢  압축맵

• 나누기(Division) (보통사용 방식)
  
  👉 h2(k) = |k| % M
  👉 해시테이블의 크기 M은 일반적으로 소수(Prime)로 선택
• 승합제(MAD, Multiply Add and Divide)
  
  👉 h2(k) = |ak + b| % M
  👉 a와 b는 음이 아닌 정수로서, a % M != 0, 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨

 

📢  해시코드맵

• 메모리 주소(Memory address)
  
  👉 키 개체의 메모리 주소를 정수로 재해석( 모든 Java객체들의 기본 해시코드다. )
  👉 일반적으로 만족스러우나 수치 또는 문자열 키에는 적용 곤란
• 정수 캐스트(Integer case)
  
  👉 키의 비트값을 정수로 재해석
  👉 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적당 ( Java의 byte, short, int, float )
• 요소합(Component sum)
  
  👉 키의 비트들을 고정길이(16 or 32bit)의 요소들로 분할한 후 각 ㅊ 합한다(overflow는 무시한다.)
  👉 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당 ( 예 : Java의 long, double )
  👉 문자의 순서에 의미가 있는 문자열 키에는 부적당 ( 예: temp01-temp10, stop-tops-spot-pots )
• 다항 누적(Ploynomial accumulation)
  
  👉 요소합과 마찬가지로, 키의 비트들을 고정길이(8,16,32bit)의 요소들로 분할 ( a(0),a(1),...,a(N-1) )
  👉 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산 (overflow 무시)
  👉 p(z) = a(0) + a(1) * z + a(2) * z^2 + .... + a(N-1) * z ^ (N-1)
  👉 문자열에 특히 적당 ( 예 : 고정값 z = 33을 선택할 경우, 50,000개의 영단어에 대해 단지 6회 충돌만 발생

 

📢  충돌해제 (중요 !!)

• 충돌(Collision) : 두 개 이상의 원소들이 동일한 셀로 매핑되는 것
• 즉, 상이한 키, k1과 k2에 대해 h(k1) = h(k2)면 "충돌이 일어났다."고 말한다.
• 충돌 해결(Collision resolution)을 위한 일관된 전략이 필요하다.
  
  👉 분리연쇄법(Separate Chaining)
  👉 선형조사법(Linear Probing)
  👉 2차 조사법(Quadratic Probing)
  👉 이중해싱(Double Hashing)
  
  

해시 충돌(Hash Collision)

 

📢  분리연쇄법

• 분리연쇄법(Separate Chaining), 연쇄법 : 각 버켓 A[i]는 리스트 L(i)에 대한 참조를 저장 ( L(i)는 리스트 )
  
  👉 해시함수가 버켓 A[i]로 매핑한 모든 항목들을 저장
  👉 무순리스트가 또는 기록파일 방식을 사용하여 구현된 미니 사전이라 볼 수 있다.
• 장단점 : 단순하고 빠르다는 장점이 있으나 테이블 외부에 추가적인 저장공간을 요구

분리연쇄법(Separate Chaining)

• 예시
  
  👉 h(k) = k % M
  👉 키 : 25,13,16,15,7,28,31,20,1  (    = 충돌 일어난 키값 )
  👉 리스에 추가되는 항목들의 위치는, 리스트의 맨 앞에 삽입하는 것이 유리하다. (리스트의 tail 포인터 없는경우)

분할연쇄법 예시

 

📢  개방주소법 ( 선형조사법 )

• 개방주소법(Open Addresssing) : 충돌 항목을 테이블의 다른 셀에 저장
• 장단점 : 분리연쇄법에 비해 공간 사용을 절약하지만, 삭제가 어렵다는 것과 사전 항목들이 연이어 군집화

개방 주소법

• 선형조사법(Linear Probing) : 충돌 항목을 (원형으로)바로 다음의 비어있는 테이블 셀에 저장함으로써 충돌을 처리
• 즉, 다음 순서에 의해 버켓을 조사한다.
  
  👉 A[ (h(k) + f(i)) % M ], f(i) = i, i = 0,1,2,...
• 검사되는 각 테이블 셀은 조사(Probe)라 불린다.
• 충돌 항목들은 군집화하며, 이후의 충돌에 의해 더욱 긴 조사열(Probe sequence)로 군집됨 = "1차 군집화"
• 예시
  
  👉 h(k) = k % M
  👉 키 : 25,13,16,15,7,28,31,20,1,38 (      = 충돌 키 )

선형조사법 예시

 

📢  개방 주소법( 2차 조사법 )

• 2차 조사법(Quadratic Probing) : 다음 순서에 의해 버켓을 조사
  
  👉 A[ (h(k) + f(i) % M ], f(i) = i^2, i = 0,1,2,...
• 해시 값이 동일한 키들은 동일한 조사를 수반한다.
• 1차 군집화를 피하지만, 나름대로의 군집을 형성 할 수 있다. = "2차 군집화"
• M이 소수가 아니거나 버켓 배열이 반 이상 차면, 비어 있는 버켓이 남아 있더라도 찾지 못할 수 있다. ( 단점 )
• 예시
  
  👉 h(k) = k % M, f(i) = i^2
  👉 키 : 25,13,16,15,7,28,31,20,1,38

2차 조사법 예시

 

📢  이중해싱

• 이중해싱(Double Hashing) : 두 번째의 해시함수 h`를 사용하여 다음 순서에 의해 버켓을 조사
  
  👉 A[ (h(k) + f(i)) % M ], f(i) = i * h`(k), i = 0,1,2,....
• 동일한 해시값을 가지는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화를 최소화한다.
• h`는 계산 결과가 0이 되면 안된다. 👉 ( 0이 되면, f(i)는 결과적으로 0만 되겠죠 ? 그럼 한자만 계속 해싱충돌 )
• 최선의 결과를 위해, h`(k)와 M은 서로소(Relative Prime)여야 한다.
  
  👉 d(1)*M = d(2)*h`(k)이면, d(2) 개의 조사만 시도한다. 즉, 버켓들 중 d(2)/M만 검사
  👉 h`(k) = q - (k % q) 또는 1 + (k % q)를 사용 ( 단, q < M은 소수며 M 역시 소수일 경우 )
  👉 한 마디로 위에 두 조건을 만족시키는, 해시함수를 적용하면, 군집화를 최소화하면서, 최소화로 실행가능
• 예시
  
  👉 h(k) = k % M, h`(k) = 11 - (k % 11),  ( 이때 q = 11이고, 11은 서로소이다. )
  👉 키 : 25,13,16,15,7,28,31,20,1,38 (      = 충돌 키 )

이중해싱 예시

• 개방주소법( 선형조사법, 2차조사법 ), 이중해싱 알고리즘

Alg findElement(k)
	input bucket array A[0...M-1], hash function h, key k
    output element with key k

v <- h(k)			// h(k) = 해시함수는 보통 주어진다.
i <- 0
while(i < M)
	b <- getNextBucket(v,i)
    if(isEmpty(A[b])
		return NoSuchKey
	elseif(k == key(A[b])
		return element(A[b])
	else
    	i <- i + 1
return NoSuchKey

=========================================================
Alg insertItem(k,e)

v <- h(k)
i <- 0
while(i < M)
	b <- getNextBucket(v,i)
    if(isEmpty(A[b]))
    	Set bucket A[b] to (k,e)
        return
	else
    	i <- i + 1
overflowException()
return

Alg getNextBucket(v,i)		// 선형조사법

return (v + i) % M

==========================================
Alg getNextBucket(v,i)		// 2차조사법

return (v + i^2) % M
==========================================
Alg getNextBucket(v,i)		// 이중해싱

return (v + i * h`(k)) % M




===========================================
Alg initBucketArray()		// 버킷초기화(예시)
	input bucket array A[0...M-1]
    output bucket array A[0...M-1] initialized with null buckets

for i <- 0 to M-1
	A[i].empty <- 1			// Set empty
return
===========================================
Alg isEmpty(b)
	input bucket b
    output boolean

return b.empty

 

📢  적재율

• 해시테이블의 적재율(Load factor), a = N/M ( N은 키 수, M은 버켓배열 크기 )
  
  👉 즉, 좋은 해시함수를 사용할 경우의 각 버켓의 기대크기
• 적재율은 낮게 유지되어야 한다 ( 가능하면 1 아래로, 즉 a = N/M < 1 되도록)
• 좋은 해시함수가 주어졌다면, 탐색,삽입,삭제 각 작업의 기대 실행시간 = O(a)
• 분리연쇄법
  
  👉 a > 1 이면, 작동은 하지만 비효울적
  👉 a < 1 이면, O(a) = O(1)의 기대실행시간 성취 가능
• 개방주소법 ( 선형조사법, 2차조사법 )
  
  👉 항상 a < 1
  👉 a > 0.5 이면, 선형 및 2차 조사인 경우 군집화 가능성 농후하다.
  👉 a <= 0.5 이면, O(a) = O(1) 기대실행시간

 

📢  해싱의 성능

• 해시테이블에 대한 탐색,삽입,삭제
  
  👉 (최악의 경우) O(N) 시간 소요
• 최악의 경우란 : 사전에 삽입된 모든 키가 충돌할 경우
• 적재율(Load factor) : a = N/M은 해시테이블의 성능을 좌우한다.
• 해시값들은 흔히, 난수(Random numbers)와 같다고 가정하면, 개방주소법(선형조사법 or 2차조사법)에 의한
  삽입을 위한 기대 조사횟수는 1/(1 - a)라고 알려져 있다.
• 해시테이블에서 모든 사전 ADT 작업들의 기대실행시간 : O(1)
• 실전에서, 적재율이 1(즉, 100%)에 가깝지만 않다면, 해싱은 매우 빠른 것이다.
• 응용분야
  
  👉 소규모 데이테베이스 ( 인덱스 )
  👉 컴파일러
  👉 브라우저 캐시