알고리즘-해시(Hash)

해시를 잘 표현한 그림

해시라는 것은 하나의 자료구조이다.

 

해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다.

보통 배열을 사용해서 구현을 하고 해시함수가 무엇인지 , 해시 테이블이라는 것은 뭔지 한번 알아보자.

 

직접 주소 테이블(Direct Address Table)

이라는 것은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다.

 

VALUE = KEY이므로 들어오는 값이 뭔지 알면 이 값이 저장된 인덱스도 함께 알 수 있다.

 

그래서 시간 복잡도는 O(1)이다.

 

하지만 직접 주소 테이블에는 단점이 있는데 -공간의 효율성-이 좋지 않다는 것이다.

 

만약 입력받은 value가 100000... 0같이 매우 큰 값이면? 그만큼 배열의 크기도 늘어난다. 

3,10,90의 값을 넣게 된다면 

배열이 매우 커짐

때문에 공간 효율이 좋지 못하다.

직접 주소 테이블은 1,2,3 이런 식의 수열이 값으로 입력되는 경우에는 좋은 효율성을 발하지만 값이 커지거나 매우 튀는 경우에는 좋지 못한 효율성을 자랑한다.

 

그. 해. 서 

 

해시 테이블이라는 것이 이러한 단점을 보완한다.  

해시 테이블은 직접 주소 테이블처럼 값을 바로 인덱스에 사용하는 것이 아니다. 

해시 함수라는 것에 한번 통과시켜서 사용한다. 해시 함수는 임의의 길이를 가지는 임의의 데이터를 

고정된 길이에 데이터로 매핑하는 함수이다.

 

이때! 이 함수가 return 하는 결과물을 Hash라고 한다.

간단한 hashFunction이 있다고 해보자.

function hashFunction (key) {
  return key % 10;
}

이 함수는 입력받은 값의 1의 자릿수를 리턴한다. 

즉 102301230123이라는 수가 입력됐다고 가정하면 이 해시함수는 3이라는 값을 리턴하는 것이다.

 

그렇다면 이 해시함수의 반환값의 범위는 무조건 (0~9)가 된다. 이 개념이 아까 위에서 설명한 해시 함수의 개념이다.

-임의의 길이를 가지는 임의의 데이터를 고정된 길이에 데이터로 매핑한다. 

 

이제 어느정도 해시함수의 개념이 잡힌 것 같다.

 

그리고 이 Hash라는것은 Hashing 된 값(Hash 함수에서 return 된 값)만 보면 인자로 어떤 값을 받았는지 추측하기 힘들다는 특성이 있다. 

이러한 특성은 우리가 비밀번호같이 암호화가 필요한 작업에서 자주 쓰이고 있다. sha-256가 대표적인 예이다.

(sha-256으로 암호화한 비밀번호는 복호화가 불가능하다...)

 

자. 이제 직접 주소 테이블의 단점을 보완할수 있게 되었다. 

 

하지만!!

 

우리는 해시가 충돌하는 경우를 생각하지 못했다. 

예를 들어보자 

 

아까만든 HashFunction의 인자로 1231234 그리고 24가 입력되었다고 쳐보자.

function hashFunction (key) {
  return key % 10;
}

hashFunction(1231234) // => return 4
hashFunction(24) // => return 4

 

 이런 경우가 발생한다는 것이다. 4가 충돌이 났다...

 

이제 우리에게 주어진 숙제는 해시의 충돌을 해결하는 것이다.

해시의 충돌 문제 때문에 해시 테이블을 운용할 때 가장 중요한 것은 사실 해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐이다.

 

마냥 값을 넣어서 충돌하는 값이 많아질 가능성이 있으면 좋은 hash가 아니라는 것이다.

 

그래서 여러가지 해시 충돌 방지 알고리즘이 있다.

1. 선형 탐사법(Linear Probing)

2. 제곱 탐사법(Quadratic Probing)

3. 이중해싱(Double Hashing)

.

.

.

추후에 이 알고리즘들에 대해서 설명할 예정이다.

 

Thank you!