Hashing

Hashing의 권오흠 교수님의 수업을 들으며 교수님께서 말하긴 이 친구는 너네 식으로 말하면 치트키다라는 말씀이 인상깊었다.
그럼 왜 그런말을 했는지 알아보자!! 

Binary Search Tree는 Hashing과 비슷한 Dynamic Set이다. Dynamic Set은 동적으로 데이터가 저장되고 삭제되고 검색하는 것을 뜻한다. Binary Search Tree는 높이에 비례하기 때문에 insert, search, delete는 O(n)이고 red black은 O(logn)입니다.

 

그렇지만 Hashing은 O(1)의 시간이 소요된다. 혹은 최악으로 O(n)이 소요된다. 왜 이렇게 되는지 알아보자!!

 

기본적으로 key와 value의 조합으로 이루어 져있으며 (key, "hoony) 이러한 형태로 이루어 져있다고 생각하면 된다.

 

보통 이러한 프로세스를 갖고 있다.

 

value -> hash함수 ->index를 만들어준 후 -> 배열[index] 에 값을 넣어주는 형태를 가진다. 밑에 함수를 보면 각 키에 대한 해쉬함수 값을 저장할 배열 인덱스로 사용하는 것이다. 

 

일반 배열과 같이 index를 바로 조회해서 값을 가져오고 넣을 수 있기 때문에 O(1)이라고 한다. 

여기서 말하는 Hashing 함수는 특별히 정해져있지는 않다 개발자가 특별히 작성하거나 유명한 Hashing함수를 사용하면된다. 여기서 value는 어떤 데이터를 사용해도 된다. 문자열이든 숫자든 상관없다. 그렇지만 이 데이터형에 맞추어 index로 반환해주는 Hashing 함수가 필요하다. 

 

그렇지만 일반적으로 하나의 값들만 딱 맞게 저장되면 너무 이상적일 것이다. 여러분도 알겠지만 모든 상황에서 이상적이지 않다. 여러개의 key가 동일한 위치로 Hashing 할 경우 Collision이라고 한다. 

3번째 줄을 보면 모든 종류의 키가 종류가 더 많으므로 m보다는 양이 당연히 많아서 항상 발생가능하다. 실제 Key의 집합이 m보다 크다면 당연히 발생가능하다. 

 

1. 서로 다른 key 값을 통해서 동일한 index가 발생할 수 있습니다.

     왜냐하면 key값은 문자열, 숫자 등을 무한히 사용할 수 있지만 배열의 index는 숫자이기 때문에 그렇지 않아서 어쩔 수 없이 겹치는 코드가 발생할 수 있습니다. 

 

해결법

1. Chaining 

  하나의 키값을 하나의 배열 값에만 저장하겠다고 하면 문제가 되겠지만 각 배열을 연결리스트로 구성하여 여러개의 데이터를 줄줄이 이어주는 것을 Chaning이라고 한다. 

 

키의 삽입 

연결리스트 제일 앞에 삽입한다면 O(1)입니다.

그렇지만 공통된 값의 삽입을 허용하지 않는다면 순차검색이 필요하므로 리스트를 검색해야한다. 

 

키의 삭제

키를 검색 후 삭제 

검색을 하고나면 O(1)밖에 시간이 안걸린다. 

키의 검색
리스트의 특정 키를 통해 검색한다. 
시간 복잡도는 키가 저장된 리스트에 비례한다. 

최악의 경우

모든 키값들이 하나의 인덱스에 연결되는 상황이 발생할 수 있다. 

-> 길이가 n인 하나의 연결리스트가 만들어짐 

-> 따라서 최악의 경우 시간 복잡도는 O(n)이 발생할 수  있다. 

 

 

2. Open Addressing 

   하나의 모든 키를 해쉬 테이블 자체에 저장 

   테이블은 각 칸에는 1개의 키만 저장 

 

Linear Probing

 

하나의 키값을 저장하려는 곳에 저장하려 하는데 비어 있지 않으면 circual하여 처음 비어 있는 곳에 저장한다. 끝까지 갔는데 없으면 다시 첫 인덱스로 이동하여 저장한다. 

 

검색
자기의 키값인지 확인하고 맞다면 반환하고 아니면 찾을 때 까지 순환하여 찾으면 반환한다. 

 

단점 

 

키들이 골고루 흩어져 있지 않고 뭉쳐서 하나의 cluster를 이루고 있을 확률이높다. 새로운 값이 추가될 때마다 아마도 클러스터에 붙어서 추가될 가능성이 높습니다. 특정 클러스가 계속해서 커질 가능성이 있다. 

 

즉 클러스터에 의해 원래의 위치보다 훨씬 멀리 저장될 가능성이 높습니다. 

 

Quadratic Probing

 

처음에 저장할 때 자기 위치에 비어 있지 않으면 

 

ex) h(k) h(k)+1^2 h(k)+2^2 h(k)+3^2 h(k)+4^2 h(k)+5^2

이런식으로 해주면 위의 단점인 Linear Probing의 단점인 cluster를 피할 수 있을 것이다. 

Double Hashing

두가지 해쉬함수를 사용하여 저장될 위치의 장소를 구하는 것이다. 
ex) h(k, i) = (h1(k) + i *h2(k)) mod m
i가 지속적으로 증가하며 이 i는 배열의 index를 의미한다. 

삭제와 검색

만약에 붙어있는 A2 B2 C2가 있다고 해보자!! B2가 삭제되고 나서 검색을 해보면 A2를 본 후 다르고 다음 칸을 보면 비어져있다. 그래서 아 Search 함수는 아 C2는 없는 값이라고 생각할 수 있다. 그래서 이와 같은 문제를 해결하기 위해 삭제된 값의 다음 값을 한칸 옮기면 문제가 해결될 것이다. 

 

Hash의 성능 따져보기 

해쉬의 성능은 키들이 얼마나 해쉬에 골고루 분포되느냐에 따라서 선택될 수 있다. 그럼 사람들은 랜덤으로 키를 만들어서 생각하면 골고루 퍼지지 않을까 생각할 수 있지만 역시 이번에도 그렇게 이상과 달리 현실은 키 값들이 랜덤하지 않다. 

1. 특정 패턴을 갖고 있어도 해쉬함수 값이 불규칙적이여야한다. 

    해쉬 함수값이 키의 특정 부분에 의해서만 결정되지 않아야한다. 

 

해쉬함수 구현법

1. Division

 

h(k) = k % table Size

이는 인덱스의 크기인 0~table Size-1로 구성하기에 가장 빠르고 좋은 방법이다. 

 

어떤 테이블 사이즈에 해쉬 함수값이 특정 부분에 의해 결정될 수 있음 

 

예를 들어 테이블 사이즈가 2^p라면 k 값의 하위 p만큼의 값이 해쉬 함수값이 될 것이다. 

2. Multiplication 

1. 0에서 1사이에 값 하나를 선택한다.(소수) 0 < A < 1

 

2. key 와 A의 값을 곱한 후 소수 점 부분 만 선택한다. 

 

3.소수부분에 m을 곱한 후 소수점 아래를 버린다. 

 

그 후 인덱스 값이 정해진다. 

정리 

오늘 수업시간에 배운 Hashing에 의해 정리해봤다. 바이너리 서치 트리에 비해 정렬이 안되고 충돌이 일어날 수 있다는 단점이 있지만 그래도 속도적인 면과 구현적인 부분에서는 많이 단순했다. 

그리고 충돌이 어떨 때 일어나고 어떻게 해결하는지 알아 보았다. 충돌은 서로 다른 키값이 공통된 해슁값을 가질 때 발생할 수 있었다. 이는 문자열과 숫자를 1대1로 매핑해주면 편하겠지만 이것이 실질적으로 불가능해서 발생하는 문제였다. 

 

이는 노드로 계속해서 이어주거나 값을 뒤로 넘겨버리는 Chaining과 Open Addressing이다. 그리고 좋은 해슁 함수를 만들기 위한 방법도 논의했다. 

 

이는 여러 조건이 있었다.

 

1. 키들이 얼마나 테이블에 골고루 분포가 되어있나

 

2. 현실적으로 특정한 패턴을 갖고있을 수 있는데 이를 불규칙하게 만들어야한다. 

 

3. 해쉬함수값이 키의 특정부분에 있어서만 결정되지 않아야한다는 조건들이 있었다. 

 

해슁 테이블의 성능은 크게 key 값을 인덱스로 바꾸어주는 Hash 함수가 결정 하는 것 같다. 

 

다음에는 그래프로 돌아와 보겠다.