묘공단 (코딩 테스트 합격자 되기 파이썬편)

해시?

해시란 해시 함수를 사용해서 변환한 값을 인덱스 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다. 보통은 인덱스를 이용하여 탐색을 빠르게 하지만 해시는 키를 활용해 데이터를 탐색한다.

해시의 특징

1. 해시는 단방향으로 동작한다. 키를 통해 값을 찾을 수 있지만 값을 통해 키는 찾을수 없다.
2. 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없다.
3. 값을 인데스로 활용하려면 적절한 변환 과정을 거쳐야한다.

해시를 사용하지 않는다면 일어나는 일

만약 해시를 사용하지 않는다면 값의 위치에 대한 어떠한 정보도 알 수 없다. 따라서 아래의 그림과 같이 어떤 데이터를 찾으려면 전체 데이터를 확인해보는 방법밖에 없다. 즉 탐색의 효율이 떨어진다.

반면 해시를 사용하면 순차 탐색을 할 필요 없이 해시 함수를 활용하여 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋다.
아래 그림에서 해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷이라고 부른다.

해시의 특성을 활용하는 분야

• 비밀번호 관리 : 사용자의 비밀번호를 그대로 노출해 저장하는 것은 위험하므로 해시함수를 활용해 해싱한 비밀번호를 저장한다. 비밀 번호가 맞는지 확인할 때도 마찬가지로 사용자가 입력한 비밀번호를 해싱해 확인한다.
• 데이터베이스 인덱싱 : 데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용한다.
• 블록체인 : 블록체인에서 해시 함수는 핵심 역할을 한다. 각 블록은 이전 블록의 해시값을 포함하고 있으며 이를 통해 무결성을 확인할 수 있다.

 

2.해시함수

해시 함수를 구현할 때 고려할 내용

1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다. 그림과 같이 해시 테이블의 크기인 0과 N-1사이의 값을 내야 한다.

   

2. 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다. 충돌의 의미는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미한다.

   

자주 사용하는 해시 함수

 

나눗셈법

나눗셈법은 키를 소수로 나눈 나머지를 활용한다. 이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시한다.

 

곱셈법

 

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

 

m은 최대 버킷의 개수, A는 황금비이다. 황금비는 무한소수로 대략 1.6180339877이다.

1. 키에 황금비를 곱한다

   

2. 1단계에서 구한 값의 모듈러 1을 취한다. 쉽게 말해 정수부분을 버리고 소수 부분만 취한다.

   

3. 2단계에서 구한 값을 가지고 실제 해시 테이블에 매핑한다. 테이블의 크기가 0이면 2단계에서 구한 수에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블에 매핑할 수 있다.

   

문자열 해싱

문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환하여 해싱한다.

 

다음 그림은 알파벳 a부터 z까지 숫자와 매치한 표와 키입니다.

“a”는 매치 표를 보면 1이다. 수식의 s[0]*p^0는 1*1이므로 (31의 0승은 1입니다) 1입니다.

두 번째 문자열 “p”에 대해 연산을 진행한다. “p”는 16이다. 여기에 p^1을 곱하면 496이다.

이렇게 곱한 값들을 더하면 최종값은 4,990,970입니다. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 된다.

 

문자열 해싱

지금까지 알아본 해시 함수는 키의 자료형이 숫자였습니다.

이번에는 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱을 알아보겠습니다. 문

자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱합니다.

 

p는 31이고, m은 해시 테이블 최대 크기입니다. 이 수식이 실제 적용되는 과정을 그림과 함께 알아봅시다.

 

※ p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문입니다.

※ 메르센 소수는 일반적으로 2N-1 형식으로 표시할 수 있는 숫자 중 소수인 수를 말합니다. 메르센 소수는 해시에서 충돌을 줄이는데 효과적이라는 연구 결과가 있습니다.

 

1단계 다음 그림은 알파벳 a부터 z까지 숫자와 매치한 표와 키입니다.

 

02단계 “a”는 매치 표를 보면 1입니다. 따라서 “apple”의 “a”는 1입니다. 그러므로 수식의 s[0] * p0는 1 * 1이므로(31의 0승은 1입니다) 1입니다.

03단계 두 번째 문자열 “p”에 대해 연산을 진행합니다. “p”는 16입니다. 여기에 p1을 곱하면 496입니다.

\

4단계 이렇게 곱한 값들을 더하면 최종값은 4,990,970입니다. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용하면 됩니다.

문자열 해시 함수 수정하기

덧셈을 전부한 다음 모듈러 연산을 하는 왼쪽 수식 대신, 오른쪽 수식처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있습니다.

체이닝으로 처리하기

체이닝은 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법입니다. 체이닝은 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결합니다.

개방 주소법으로 처리하기

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

이중 해싱 방식

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

하지만 단점으로는 
해시 테이블 공간 활용성이 떨어지며 검색 성능이 떨어짐