해시
해시의 개념
날마다 엄청난 데이터가 생기고 있고 현대 사회에서 이런 데이터를 효율적으로 저장하거나 탐색하는 건 중요한 문제입니다.
이전 배열의 경우 특정한 값을 탐색할 때 인덱스를 사용할 수 있었고 그렇지 않다면 순차적으로 하나씩 탐색하는 것 밖에 없습니다. 하지만 이러한 방식은 모든 데이터를 찾아봐야하기에 효율적이지 않습니다.
위와 같은 질문에서 탄생한 것이 바로 자료구조 해시입니다.
해시는 해시 함수를 사용하여 반환한 값을 인덱스로 삼아 키와 값을 저장하여 빠른 데이터 탐색을 제공하는 자료구조입니다. 이들은 보통 키를 활용하여 데이터 탐색을 빠르게 합니다.
해시 자세히 알아보기
실생활에서도 해시를 많이 사용하고 있습니다. 가장 쉽게 볼 수 있는 예시는 연락처입니다.
다음과 같이 표로 나타낼 수 있습니다.
키 | 해시 함수 | 인덱스 | 값 |
|---|---|---|---|
김동률 | -> | 0 | 010-XXXX-XXXX |
김태형 | -> | 1 | 010-XXXX-XXXX |
장범준 | -> | 2 | 010-XXXX-XXXX |
이승기 | -> | 3 | 010-XXXX-XXXX |
해당 해시에서 최종적으로 얻고자 하는 전화번호는 값이고 해당 값을 검색하기 위해 활용하는 정보는 키의 역할을 하는 이름입니다.
해시의 특징
해시는 단방향으로 동작합니다. 해시는 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾지는 못합니다.
찾고자 하는 값을 찾는 시간 복잡도는
입니다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없습니다.
만약 해시를 사용하지 않으면 어떻게 될까요?
위와 같이 전화번호부를 사용한다고 가정을 해보겠습니다. 만약 전화번호부에 사람이 1000명이 있다고 했을때 만약 마지막에 적혀져 있다면 모든 전화번호를 순회를 하면서 이름을 검색을 해야합니다. 하지만 만약 고유한 해시 값으로 시간 복잡도
해시의 특성을 활용하는 분야
해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있습니다. 만약 특정 데이터를 검색하는 코딩 테스트 문제가 있다면 해시를 고려하는 것이 좋습니다.
다음은 해시를 사용하는 예시 분야입니다.
비밀번호 관리: 비밀번호를 그대로 노출하는 것은 위험합니다. 따라서 해시 함수를 이용하여 해싱한 비밀번호를 저장합니다.
데이터베이스 인덱싱: 데이터베이스에 저장된 데이터를 효율적으로 검색하기 위해서 해시를 활용합니다.
블록체인: 해시 함수는 블록체인의 핵심 역할을 합니다. 이전 블록의 해시 값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있습니다.
해시 함수
자바스크립트에서는 객체 즉 오브젝트라는 자료형을 제공합니다. 해당 자료형은 해시와 거의 동일하게 동작하므로 해시를 쉽게 구현할 수 있습니다.
해시 함수를 구현할 때 고려할 내용
해시 함수가 변환한 값은 인덱스로 활용해야 하기 때문에 테이블의 크기를 벗어나서는 안됩니다. 만약 해시 테이블의 크기가 N이라면 0과 N - 1 사이의 값을 내야 합니다.
변환한 값의 추돌을 최대한 적게 발생해야 합니다. 충돌의 의미는 서로 다른 두 키에 대해 해싱 함수를 적용한 결과 동일한 것을 의미합니다.
자주 사용하는 해시 함수 알아보기
나눗셈법
키를 소수로 나눈 나머지를 활용합니다. 이처럼 나머지를 취하는 연산을 모듈러 연산이라고 하며 연산자는 %로 표시합니다.
나눗셈법을 수칙으로 작성하면 다음과 같습니다.
x는 키, k는 소수 입니다. 키를 소수로 나눈 나머지를 인덱스로 사용하는 것입니다.
나눗셈법에 소수가 아닌 15를 사용하면 어떻게 될까?
소수를 사용하는 이유는 다른 수를 사용할 때보다 충돌이 적기 때문입입니다. 만약 소수가 아닌 15를 나눗셈법에 적용한다고 했을 때 3, 6, 9, 12, 0와 같이 해시 값이 충돌과 반복이 될 수 있습니다.
곱셈법
나눗셈법은 때에 따라 큰 소수를 사용해야 하는데 큰 소수를 구하기 어렵다는 단점이 있습니다. 곱셈법은 나눗셈 법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않습니다.
곱셈법을 수칙으로 작성하면 다음과 같습니다.
문자열 해싱
함수의 키가 문자열일 경우 사용할 수 있는 문자열 해싱을 알아보겠습니다. 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식으로 변환해서 해싱합니다.
충돌 처리
해시에서는 언급했던 것처럼 서로 다른 키에 대해서 함수의 결괏값이 같으면 충돌이라고 합니다. 하나의 버킷에 2개의 값은 넣을 수 없으므로 반드시 충돌 처리를 해야합니다.
체이닝으로 처리하기
체이닝은 충돌이 발생하면 해당 버킷에 연결 리스트로 같은 해시 값을 가지는 데이터를 연결합니다.
해시 테이블 공간 활용성이 떨어짐
충돌이 많아질수록 연결 리스트의 길이가 길어지고 테이블의 공간은 덜 사용하므로 공간 활용성이 떨어집니다.
검색 성능이 떨어짐
충돌이 많으면 연결 리스트 자체의 한계 때문에 검색 성능이 떨어집니다. 연결 리스트로 연결한 값을 찾으려면 연결 리스트의 맨 앞 데이터 부터 검색해야 하기 때문입니다.
개방 주소법으로 처리하기
빈 버킷을 찾아 충돌값을 삽입합니다. 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 더 효율적으로 사용합니다.
선형 탐사 방식
충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동합니다.
m은 수용할 수 있는 최대 버킷입니다. 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산을 적용한 겁니다.
이중 해싱 방식
해시 함수를 2개 사용하는 것을 말합니다. 때에 따라 해시 함수를 N개로 늘리기도 합니다. 두 번째 해시 함수의 역할을 첫 번째 해시 함수의 충돌이 발생하면 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할을 합니다.
수식을 보면 선형 탐사와 비슷하게 더하는 방식으로 데이터의 위치를 정하지만 클러스터를 줄이기 위해 m을 소수로 합니다. 이는 주어지는 키마다 점프하는 위치를 다르게 해서 클러스터 형성을 최대한 피하기 위함입니다