해시 개념 정리

► 코딩테스트 합격자 되기 자바스크립트편 08 해시 개념 정리한 포스팅입니다.

해시

key: Data : 키를 통해 데이터를 탐색한다.

해시 특징

• 해시는 단방향으로 동작한다. 이런 특징은 외부에 정보를 안전하게 제공하는 특징이 있어 네트워크 보안에서 많이 활용된다.
• 찾고자 하는 값은 O(1)에서 바로 찾을 수 있다. 키 자체가 해시함수로 인해 값이 있는 인덱스가 된다.
• 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야한다.

해시 특성 활용 분야

· 비밀번호 관리, 데이터 베이스 인덱싱, 블록체인

자바스크립트에서의 해시

자바스크립트에는 오브젝트 자료형을 제공하는데, 이 자료형이 해시와 거의 동일하게 동작한다.

해시 함수 구현시 고려사항

1. 해시 함수로 인한 변환값은 인덱스로 활용된다. 충돌은 서로 다른 두키가 해시 함수로 인해 변환된 값의 결과가 동일한 것을 말한다.
2. 변환된 값 간의 충돌은 최대한 적게 발생해야 한다. 충돌은 서로 다른 두키가 변환된 값의 결과가 동일한 것을 말한다.

자주 사용하는 해시 함수 알아보기

나눗셈법division method키를 소수로 나눈 나머지를 활용한다. ( = 모듈러 연산 : 나머지를 취하는 연산 )

 

h(x) = xmodk // 키를 소수로 나눈 나머지를 인덱스로 사용

 

✔️ 왜 소수로 나눌까?

다른 수들로 나눌 때보다 충돌이 제일 적기 때문에! 소수가 아닌 정수로 나눌 경우 n의 정수로 나오게되는 경우가 많아 해시 함수로 반환된 값 또한 충돌이 많이 발생한다. 따라서 1과 자신 밖에 없는 소수를 사용하는 것을 추천한다.

✔️ 나눗셈 법의 해시테이블 크기는 k

나눗셈 법의 단점은 매우 많은 데이터를 저장해야할 때 매우 큰 소수를 구하는 효율적인 방법이 아직 없다는 것이다. 필요한 경우 기계적인 방법으로 구해야한다.

---

곱셈법나눗셈 법은 때에따라 큰 소수를 사용해야할 때 큰 수소를 구하기 어렵다는 단점이 있다. 곱셈법은 비슷하게 모듈러 연산을 활용하지만 소수는 사용하지 않는다.

h(x) = ((( x * A )mod 1) * m) // A는 황금비 (= 무한소수), m은 최대 버킷의 개수

 

✔️곱셈법 방법

1. 키 * 황금비 ( x * A )
2. 모듈러 1을 취한다. 이때 정수는 버리고 소수 부분만 취한다.
3. 해시 테이블에 매핑한다. 테이블 크기가 m일 경우, 앞에서 소수 부분만 취한 것에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블 매핑을 할 수 있다.

곱셈법은 황금비를 사용하므로 소수가 필요없다는 장점이 있다. 테이블이 커져도 추가 직업이 필요없다.

---

문자열 해싱키의 자료형이 문자열일 경우 사용할 수 있는 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.

> polynomial rolling method

hash(s) = (s[0] + s[1]*p + s[2]*p^2 + ...+ s[n-1]*p^(n-1))mod m > p는 31(메르센 소수이기 때문, 메르센 소수는 해시에서 충돌을 줄이는데 효과적임), m은 해시 테이블 최대 크기.

 

✔️ 문자열 해싱 방법

1. 알파벳 a부터 z까지 숫자와 매치된 표와 키가 있다. ( a~z ) -> ( 1~26 )
2. apple이란 문자를 두고 매치 표를 보았을 때, "a"는 1이다. 수식의 s[0] * p^0은 1 * 1이므로 1이다.
3. 다음 문자열 "p"에 대한 연산을 진행했을 때, "p"는 16이다. s[1] * p^1은 16 * 31^1이므로 496이다.
4. 이렇게 곱한 값들을 더하면 최종값은 4,990,970이다. 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 된다.

키 자체가 숫자라면 바로 해시 함수를 적용할 수 있지만 문자열일 경우 각 문자열의 문자들을 적절한 숫자로 변경하여 해시 함수를 적용해야 한다. 이런 변환 과정을 통해 문자열 키인 데이터에도 해시를 사용할 수 있다. 적용한 값이 해시 테이블 크기에 비해 너무 클 수 있지만 해시 함수가 내는 결과의 크기를 해시 테이블 크기에 맞도록 하는 작업이 필요하다. 결과값이 커지면 오버플로가 발생할 수 있으므로 문자열 해시 함수 수정을 통해 수정할 수 있다. 모두 덧셈을 한 다음 중간 중간 모듈러 연산을 해, 더한 값을 모듈러 연산을 하면 오버플로를 최대한 방지할 수 있다.

 

hash(s) = (s[0]%m + s[1]*p%m + s[2]*p^2%m + ...+ s[n-1]*p^(n-1)%m)% m

 

난이도 높은 문제는 오버플로 함정이 있는 경우가 많으니 유의하기!

---

해시 충돌 처리

☑️ 방법 1 : 체이닝으로 처리

해당 버킷에 연결 리스트( linked list: 데이터 요소들을 연결하여 구성한 선형 데이터 구조 )로 같은 해시값을 가지는 데이터를 연결한다.

이후 어떤 데이터가 해시 테이블 상 같은 위치에 저장되어야 하면 이런 방식으로 데이터를 저장한다. 체이닝은 충돌을 연결 리스트로 간단히 해결한다는 장점이 있다.

체이닝 단점

1. 해시 테이블 공간 활용성이 떨어짐
2. 검색 성능이 떨어짐

☑️ 방법 1 : 체이닝으로 처리

개방 주소법(open addressing)은 체이닝에서 연결 리스트로 충돌값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다. 해시체이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다.

 

 

선형 탐사 방식

충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동한다.

 

h(x,i) = (h(k) + i)mod m

 

m은 수용할 수 있는 최대 버킷이다. 선형 탐사 시 테이블 범위를 넘으면 안 되므로 모듈러 연산을 적용한 것이다. 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌을 발생한 값끼리 모이는 영역이 발생한다.( = 클러스터cluster 형성 ) 충돌이 발생한 값들이 모인 영역이 생기면 해시값은 겹칠 확률이 더 올라가게 된다. 이를 방지하기 위해 제곱수만큼 이동하여 탐사하는 방법도 있다.

 

☑️ 이중 해싱 방식

말 그대로 해시 함수를 2개 사용한다. 때에 따라 해시 함수를 N개로 늘리기도 한다. 두 번째 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 한다.

 

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

 

수식을 보면 선형 탐사와 비슷한 방식으로 데이터의 위치를 정하지만 클러스터를 줄이기 위해 m을 제곱수로 하거나 소수로 하여 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 할 수 있다.

 

처음 알고리즘 입문할때는 자바스크립트의 오브젝트 자료형이 해시와 거의 동일하게 동작한다고 이해하고 넘어가도 괜찮(?)을 것 같지만 조금 더 깊이 이해하기 위해 아래 포스팅도 추가적으로 공부해보자.

 

https://velog.io/@wongue_shin/JS%EC%9D%98-%EA%B0%9D%EC%B2%B4%EB%8A%94-hash-table%EC%9D%B4-%EC%95%84%EB%8B%99%EB%8B%88%EB%8B%A4

 

► 코딩테스트 합격자 되기 - 자바스크립트편 08 해시 개념 정리