https://product.kyobobook.co.kr/detail/S000210881884
코딩 테스트 합격자 되기: 파이썬 편 | 박경록 - 교보문고
코딩 테스트 합격자 되기: 파이썬 편 | ★ 코딩 테스트 합격자가 되는 가장 확실한 방법! ★ 프로그래머스 제공, 전문가가 모여 엄선한 빈출 100문제로 철저하게 대비하세요신입 사원 코딩 테스트
product.kyobobook.co.kr
해시
해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장하여 빠른 데이터 탐색을 제공하는 함수.
보통은 인덱스를 활용하여 탐색을 빠르게 만들지만 해시는 key 를 활용해 데이터 탐색을 빠르게 한다.
* 해시는 키와 데이터를 일대일 대응하여 저장하므로, 키를 통해 데이터에 바로 접근할 수 있다. 사람에게는 숫자(인덱스) 로 데이터를 관리하는 배열보다 조금 더 접근성이 좋은 자료구조.
해시의 특징
- 해시는 단방향으로 동작한다. 즉 키를 통해 값을 찾을 수 있지만, 값을 통해 키를 찾을 수는 없다.
- 찾고자 하는 값을 O(1)에서 바로 찾을 수 있다. 값을 찾기 위한 탐색 과정이 필요 없다.
- 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 한다.
* 단방향 동작은 외부에 정보를 안전하게 제공한다는 특징이 있어, 네트워크 보안에서 많이 활용된다.
해시를 사용하는 것의 장점
인덱스로 값을 찾을 때 쉽게 떠올려 볼 수 있는 것은 순차탐색이다. 하지만 최악의 경우 탐색을 할 때마다 모든 데이터를 살펴봐야 할 수 있으므로, 효율적이지 않다. 반면 해시를 사용할 때는 순차 탐색할 필요 없이 해시 함수를 활용해 특정 값이 있는 위치를 바로 찾을 수 있다.
아래 그림에서 해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 각 데이터를 버킷 이라고 부른다.
해시 함수
해시 함수를 구현할 때 고려할 내용
- 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안 된다. 예를 들어 N 개의 전화번호가 담긴 해시테이블을 작성할 때, 해시 함수의 결과는 0~N-1이 적절하다.
- 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 한다. 충돌의 의미는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미한다. 해싱 함수의 결과가 곧 저장 위치가 되기 때문에 충돌이 발생한다.
자주 사용하는 해시 함수 알아보기
나눗셈법
키를 소수로 나눈 나머지를 인덱스로 활용한다. 나머지를 취하는 연산을 모듈러 연산(%)이라고 한다.
h(x) = x mod k
x는 키, k는 소수이다.
나눗셈법의 해시 테이블의 크기는 K 이다. 왜냐하면 K에 대해 모듈러 연산을 했을 때 나올 수 있는 값은 0 ~ (K-1) 이기 때문이다. 즉 상황에 따라 아주 많은 데이터를 저장해야 한다면, 굉장히 큰 소수가 필요할 수도 있다.
곱셈법
h(x) = (((x*a)mod 1) * k )
k는 최대 버킷의 개수, A는 황금비 이다. 황금비는 무한소수로 대략 1.1618033... 예제에서는 일부인 0.6183만 사용한다.
- 키에 황금비를 곱한다.
- 구한 값의 모듈러 1을 취한다. 즉 정수 부분은 버리고 소수 부분만 취한다.
- 구한 값으로 실제 해시 테이블에 매핑한다.
곱셈법은 황금비를 사용하므로 나눗셈법처럼 소수가 필요하지 않다. 즉, 해시 테이블의 크기가 커져도 추가 작업이 필요하지 않다.
문자열 해싱
지금까지 알아본 해시 함수의 키는 숫자였으나, 이번에는 키의 자료형이 문자열일 때도 사용할 수 있는 해시 함수인 문자열 해싱을 알아보자. 문자열 해싱은 문자열의 문자를 숫자로 변환하고, 이 숫자들을 다항식의 값으로 변환해서 해싱한다.
p는 31이고 m 은 해시 테이블의 최대 크기이다.
*p를 31로 정한 이유는 홀수이면서 메르센 소수이기 때문이다.
* 메르센 소수는 일반적으로 (2^n)-1 로 표시할 수 있는 숫자 중 소수인 수를 말한다. 메르센 소수는 해시에서 충돌을 줄이는 데 효과적이라는 연구 결과가 있다.
1. 알파벳을 숫자로 매칭
2. 매치한 숫자에 p^n 을 곱함
3. 같은 연산을 나머지 문자열에도 적용
4. 이렇게 곱한 값들을 더해 최종 값을 구하고, 해시테이블의 크기 m 으로 활용
키가 문자열이면 각 문자열의 문자들을 적절한 숫자로 변경한 다음 해시 함수를 적용해야 한다. 이런 변환 가정을 통해 문자열이 키인 데이터에도 해시를 사용할 수 있다. 하지만 해시를 적용한 값이 해시 테이블의 크기에 비해 너무 클 수 있다. 그림을 보면 "apple"라는 간단한 문자열을 해싱했지만, 결괏값은 4,990,970으로 굉장히 크다.
따라서 다음 연산 법칙을 활용해 문자열 해시 함수를 수정할 수 있다.
문자열 해시 함수 수정
덧셈을 전부한 다음 모듈러 연산을 하는 왼쪽 수식 대신, 오른쪽 수식처럼 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있다.
이를 활용해 앞서 본 문자열 해싱 공식을 수정하면 다음과 같다.
충돌 처리
앞서 자주 언급했던 것처럼 서로 다른 키에 대해서 해시 함수의 결괏값이 같으면 충돌이라고 한다. 하나의 버킷에 2 개의 값을 넣을 수는 없으므로, 해시테이블을 관리할 때는 반드시 충돌 처리를 해야한다.
체이닝
체이닝 충돌이 발생하면 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결한다.
위처럼 B와 C에 대해 같은 해시 결과값인 3이 발생한다면, 체이닝은 링크드리스트로 충돌한 데이터를 연결한다. 이후 어떤 데이터가 해시 테이블 상 같은위치에 저장되어야 한다면 이런 방식으로 데이터를 저장한다.
단점
- 해시테이블 공간 활용성이 떨어짐 : 충돌이 많아지면 그만큼 링크드리스트의 길이가 길어지고, 다른 해시테이블의 공간은 덜 사용하므로 공간 활용성이 떨어진다.
- 검색 성능이 떨어짐 : 충돌이 많으면, 최악의 경우 링크드리스트를 탐색하는 시간복잡도는 최악의 경우 O(n)이므로 성능이 떨어진다.
개방 주소법
체이닝에서 링크드리스트로 충돌한 값을 연결한 것과 다르게 빈 버킷을 찾아 충돌값을 삽입한다. 이 방법은 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용한다.
선형 탐사 방식
h(k,i) = (h(k) + i) mod m
m은 수용할 수 있는 최대 버킷. 선형 탐사시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한다.
* 보통 간격은 1로 설정
하지만 한 칸씩 값을 이동하며 해시 테이블 빈 곳에 값을 넣음녀 해시 충돌이 발생한 값끼리 모이는 영역이 생기며 이를 클러스터cluster를 형성한다고 한다. 이런 군집이 생기면 해시값은 겹칠 확률이 더 올라간다.
이중 해시 방식
이중 해싱 방식은 말 그대로 해시 함수를 2개 사용한다. 때에 따라 해시 함수를 n 개로 늘리기도 한다. 두 번째 해시 함수의 역할은 첫 번째 해시 함수로 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 한다. 예를 들어 h1이 1차 해시 함수, h2가 2차 해시 함수이다.
수식을 보면 선형 탐사와 비슷하게 더하는 방식으로 데이터의 위치를 정하지만, 클러스터를 줄이기 위해 m 을 제곱수로 하거나 소수로 한다. 이는 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 해서 클러스터 형성을 최대한 피하기 위함이다.
[코딩 테스트 합격자 되기] 해시 - 1. 해시의 개념 - 골든래빗
어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 굳이 탐색을 할 필요 없이 바로 데이터를 찾아낼 수 있을 겁니다. 이런 생각을 바탕으로 만든 자료구조가 해시(Hash)입니다.
goldenrabbit.co.kr
[코딩 테스트 합격자 되기] 해시 - 2. 해시 함수와 충돌 처리 - 골든래빗
어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 굳이 탐색을 할 필요 없이 바로 데이터를 찾아낼 수 있을 겁니다. 이런 생각을 바탕으로 만든 자료구조가 해시(Hash)입니다.
goldenrabbit.co.kr
'알고리즘' 카테고리의 다른 글
| [코딩테스트 합격자 되기 09] 트리 (4) | 2024.10.13 |
|---|---|
| [코딩테스트 합격자 되기 08] 해시 Q&A (0) | 2024.10.07 |
| [정리] yield 의 동작 방식 (0) | 2024.09.30 |
| [코딩테스트 합격자 되기 07] 큐 (0) | 2024.09.23 |
| [백준] 1914 하노이탑 (0) | 2024.09.22 |