해쉬

21 Jan 2021 in Algorithms

Direct-Address Tables

• 크기가 U인 테이블 T를 생성하고, key k를 slot K 에 저장
• 중복되는 Key는 없다.
• 시간 복잡도가 빠르다. 키값만 알면 바로 데이터를 가져올 수 있어서.
• 공간 복잡도는 크다. 100만개의 공간을 미리 할당한다고 치면, 그만큼 사용하지 않을 경우 공간 낭비가 많다.

Hash Tables

• hash 함수는 임의의 크기의 데이터를 받아서 이 데이터를 고정된 크기로 바꿔준다.
• key k를 저장할 때, slot k에 직접 저장하는 것이 아니라 , h(k)를 계산해서 넣는다.
• 동일한 해쉬값을 가지는 키가 생기는 문제가 생긴다.
  • 이걸 chianing 방법으로 해결해준다. 중복되는 key값이 있으면 해당 슬롯을 연결 리스트로 저장한다.
  • 이때문에 최악의 경우 데이터 검색 시 Θ(n)의 시간복잡도를 가진다.
• 공간의 효율성은 좋다.

그렇담, 좋은 해쉬 함수란?

• simple uniform hasing 만족하는 해쉬함수
  • 각각의 key는 중복없이 m 개의 slot으로 동일한 확률로 해쉬되며
  • 각각의 key는 다른 key값의 해쉬값과 상관없이 해쉬된다.
• ex) h(k) = k mod 701

Open Addressing

• collision 을 피하기 위한 다른 방법. key를 hash table에 직접저장
• 포인터를 사용하지 않아서 구현이 간편하고, 추가메모리 공간 사용이 가능하다.

Open Addressing 방법

Linear Probing

• 충돌나면, 연결 리스트에 저장하는게 아니라 그 다음 공간에 저장하는 것.

• 충돌이 나면 빈 Slot이 나올 때까지 해쉬 테이블 탐색.

  h(k,i) = (k+i) mod 13
  

• 좀 별로여보이는데, 사실 그렇지 않다고 한다.

슈도코드

Hash-Search(T,k)
	i=0
	repeat
		j=h(k,j)
		if T[j]==k
			return j
			i++
		until T[j] = NIL or i==m
			return NIL

• 테이블 전체를 다 뒤졌거나, 빈칸이 나올때 까지 search 를 한다.
• 빈칸이 나올때 까지라는 조건때문에 삭제할 때 조심해야한다. 그래서 삭제할때 빈칸으로 바꾸지 않고(빈공간이 나오지 않게한다.) Deleted 표시한다.
• 구현은 쉬우나 primary clustering 문제가 있다. (충돌하면 다음 빈칸에 채우기 때문에 정보들이 cluster로 뭉쳐있을 확률이 크다.)

**Quadratic Probicng

• 다음과 같이 표현된다.

  h(k,i)=(h'(k)+ c1*i + c2*i^2) mod m
  

• 이렇게 저장하면 linear probing에서의 primary cluster 문제를 해결할 수 있다.

• secondary clustering 문제가 발생한다.

Double Hashing

• 충돌 시 다른 hashing을 또 이용해 값을 저장

  h1(k) = k mod 13
  h2(k) = 1 + (k mod 11)
  h(k,i) = (h1(k) + i*h2(k)) mod 13)