unit 4. hashing

 hashing에 대해 정리합니다.  이미 밝혔다시피 해당 포스팅은 inflearn의 "영리한 프로그래밍을 위한 알고리즘 강좌"를 기반으로 합니다.

 hash table은 dynamic set을 구현하는 효과적인 방법 중 하나입니다.  dynamic set이라 함은 다양한 데이터들이 유동적으로 in/out하기에 적합한 자료구조입니다.  

 데이터를 소스로 하여 특정 함수로 해당 데이터가 저장될 위치를 구하며, 이를 통하여 효율적인 데이터 관리가 가능해집니다.

 주의할 점은, 데이터와 특정 함수에 따라서 저장될 위치가 겹치는 경우가 발생합다.  이러한 collision problem에, 두 개 이상의 키가 동일한 위치에 해슁되는 경우, 해결 방안으로 두 가지를 본 강의에서 제시하고 있습니다.

 해쉬함수값이 불규칙적이 되도록 하는게 바람직합니다.  또한, 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 합니다.

 두 가지 방법은 다음과 같습니다.

니

1. chaining

-collision problem이 발생할 때, 해당 키를 가진 위치에 링크드리스트로 next 항을 이어 만듭니다.(하나의 예시)  충돌이 발생하고 해당 key에 데이터가 이미 존재할 경우, 링크드리스트의 next node에 데이터 유무를 확인하고 있다면 다음 node로, 없다면 해당 공간에 저장합니다.

(java의 hashset 메소드가 이러한 방법을 사용한다고 설명합니다.  hashset인지 hashmap인지는 정확하지 않음)

2. open addressing

-모든 키를 hash table 자체에 저장합니다.

-테이블의 각 칸에는 1개의 키만 저장합니다.

2.1 linear probing

-키에 해당하는 장소에 데이터가 존재한다면 그 다음 항에 데이터를 저장합니다.

array = [0, 1, 4, 5, None, None]
data = 'data'
target = 3
 
while array[target] != None: target += 1
array[target] = data 

2.2 quadratic probing

-키에 해당하는 장소에 데이터가 존재한다면 밀린 카운트^2의 장소에 데이터를 저장합니다.

import random
 
target = 3
data = "soicem"
array = [1,3,2,4,4,5,6,None,3,None]
cnt = 1
while array[target] != None:
    target += target + cnt**2
array[target] = data

2.3 double hashing

-k에 따라서 키가 바뀝니다.  

 h(k, i) = (h1(k) + i * h2(k)) mod m