[컴퓨터 알고리즘 기초] 9. 해쉬 알고리즘(1)

학습목표

1. Direct-address Tables에 대해 이해하고 장단점을 파악할 수 있다.

2. Hash Tables를 이해하고 장단점을 파악할 수 있습니다.

---

1. Direct-address Tables

Direct-address Tables

• 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식
• 단, 중복되는 key는 없다고 가정

Direct-address tables의 주요 함수

Direct_Addtess_search(T,k)
	return T[k]

Direct_Addtess_insert(T,x)
	T[x.key] = x

Direct_Addtess_delete(T,x)
	T[x.key] = nil

각각의 수행 시간은 O(1)

Direct-addressing의 공간 복잡도

• Θ(U)
• 실세 공간 사용을 전체 공간으로 나눈 K/U를 적재율이라고 한다.
• 만약 적재율이 낮다면 실제로 대부분의 공간은 낭비 된다.

---

2. Hash Table

해슁(Hashing)

• Key k를 저장할 때 slot k에 저장하는 것이 아니라 slot h(k)에 저장한다.
• 이것을 key k가 slot h(k)로 해쉬되었다고 하며 h(k)를 key k의 해쉬값이라고 부른다.
• 이때 h()를 해쉬 함수(hash function)라고 부른다.

수행시간 분석

• instertion : O(1)
• deletion : O(1)
• search : O(1)

이 때 slot은 항상 비어져 있으며 이 중 연결 리스트로 구현되어 있다고 가정하며 리스트의 길이를 1이라고 생각한다.

 

충돌 문제(collision)

• 두 개의 key가 동일한 hash 값을 갖는 경우 '충돌이 발생했다.'라고 한다.
• 충돌을 피하는 방법은 충돌이 적은 좋은 해쉬함수를 쓰는것
  • 하지만 테이블의 크기가 해쉬함수의 치역영역보다 크다면 충돌을 피하는 것은 매우 어렵다.

 

체인을 이용한 충돌해결법(collision resolution by chaining)

• 중복되는 key값이 있을 경우, 해당 슬롯을 연결리스트로 저장한다.

 

주요 함수 

chained_hash_insert(T,x)
	insert x into list T[h(x.key)]
chained_hash_delete(T,x)
	delete x from the list T[h(x.key)]
chained_hash_search(T,k)
	search for an element with key k io list T[h(k)]

 

최악의 경우의 수행 시간(worst Case)

• Θ(n)

모든 key 값 k가 하나의 slot으로 해슁되는 경우는 길이가 n인 이중 연결 리스트가 된다.

해쉬 테이블이 아닌 일반적인 리스트에 저장하는 것과 성능이 동일하다.

 

평균적인 수행시간

• Θ(1+a)

이때 a는 적재율(load factor)이라고 부르며 a=n/m으로 계산한다.

n은 테이블의 원소 개수이고 m은 slot의 수이다.

 

해쉬 함수(hash functions)

좋은 해쉬 함수는 무엇인가?

• 좋은 해쉬함수는 simple uniform hashing을 만족하는 해쉬 함수이다.

각각의 key는 중복없이 m개의 slot으로 동일한 확률로 해쉬되며 각각의 key는 다른 key값의 해쉬값과 관계없이 해쉬된다.

• 즉, 좋은 해쉬 함수는 모든 값이 모든 값이 골고루 나오는 것이다.

m개의 slot이 있으면 중복없이 확률적으로 m개의 slot에 골고루 나누어지는 것이 좋으며 이것을 simple uniform hashing이라고 부른다.

 

해쉬 함수와 key

• 해쉬함수에서는 key값을 자연수로 가정
• 만약 key가 자연수가 아닌 character나 string의 형태라면 자연수 형태로 변형하여 사용한다.

나눗셈 방법(the division method)

• 해쉬 함수로 나눗셈을 이용하는 방법으로 키값 k를 m으로 나누고 나머지를 이용
• 효율적인 m의 선택 방법
  • m =2의 지수 승인 경우는 피하는 것이 좋다.
  • 또한 2의 지수 승 -1 인 경우도 피하는 것이 좋다.
  • 2의 지수승에 너무 가깝지 않은 소수를 선택하는 것이 좋다.

 

다음시간에 이어서 해쉬 알고리즘을 구현해 보겠습니다.