해시의 원리를 이해하고 문제에서 요구하는 해시 함수를 구현할 수 있습니다.
총 3편으로 준비했습니다.
1. 해시의 개념
2. 해시 함수와 충돌 처리
3. 해시 몸풀기 문제
날마다 엄청난 데이터가 생기고 있고 현대 사회에서 이런 데이터를 효율적으로 저장하거나 탐색하는 건 중요한 문제입니다. 어떤 데이터를 찾는다고 했을 때 쉽게 떠올려볼 수 있는 방법은 처음부터 끝까지 순차 탐색하는 방법입니다. 이 방법을 사용하면 가장 확실하게 원하는 데이터를 찾을 수 있습니다. 하지만 최악의 경우 탐색을 할 때마다 모든 데이터를 살펴봐야 할 수 있으므로 효율적이지 않죠.
이 방법을 개선하려면 찾아야 할 값이 어디에 있는지 알아낼 방법이 필요합니다. 즉, 어떠한 값이 저장되는 위치를 어떤 규칙으로 정할 수 있다면 굳이 탐색을 할 필요 없이 바로 데이터를 찾아낼 수 있을 겁니다. 이런 생각을 바탕으로 만든 자료구조가 해시(Hash)입니다.
해시는 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조입니다. 어떻게 탐색을 빠르게 만들까요? 보통은 인덱스를 활용해서 탐색을 빠르게 만들지만 해시는 키(Key)를 활용해 데이터 탐색을 빠르게 합니다.
※ 해시는 키와 데이터를 일대일 대응하여 저장하므로 키를 통해 데이터에 바로 접근할 수 있습니다. 사람에게는 숫자(인덱스)로 데이터를 관리하는 배열보다 조금 더 접근성이 좋은 자료구조라 할 수 있습니다.
해시 자세히 알아보기
사실 우리 생활에도 해시를 많이 활용합니다. 가장 쉽게 볼 수 있는 해시의 예는 연락처입니다. 연락처는 다음과 같은 그림으로 그려볼 수 있습니다.
그림을 보면 내가 최종으로 얻고자 하는 정보, 즉, 전화번호는 값(Value)이고, 값을 검색하기 위해 활용하는 정보는 키(Key)입니다. 그리고 그 사이에 키를 이용해 해시값 또는 인덱스로 변환하는 해시 함수가 있습니다. 해시 함수는 이렇게 키를 일정한 해시값으로 변환시켜 값을 찾을 수 있게 해줍니다. 해시 함수는 설명할 내용이 많으므로 우선 해시가 이런 식으로 동작한다는 콘셉트만 머릿속에 넣어두고 큰 범위에서 동작만 살펴보겠습니다.
※ 자세한 내용은 ‘2. 해시 함수와 충돌 처리’에서 설명하겠습니다.
해시의 특징
첫 번째, 해시는 단방향으로 동작합니다. 즉, 키를 통해 값을 찾을 수 있지만 값을 통해 키를 찾을 수는 없습니다.
두 번째, 찾고자 하는 값을 O(1)에서 바로 찾을 수 있습니다. 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요 없습니다.
세 번째, 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 합니다.
※ 단방향으로만 동작하는 해시의 특성은 외부에 정보를 안전하게 제공한다는 특징이 있어 네트워크 보안에서 많이 활용됩니다.
해시를 사용하지 않는다면 어떻게 될까?
만약 해시를 사용하지 않는다면 우리는 값의 위치에 대한 어떤 정보도 알 수 없을 겁니다. 그래서 어떤 데이터를 찾으려면 전체 데이터를 확인해보는 방법밖에는 없을 겁니다. 예를 들면 다음과 같이 전체 전화번호를 순차 탐색해 이름에 맞는 전화번호를 찾아야 할 겁니다. 그림으로만 봐도 탐색 효율이 떨어집니다.
반면 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋습니다. 그림에서 해시 테이블(Hash Table)은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷(Bucket)이라고 부릅니다. 이 책에서도 해시 테이블, 버킷이라는 말을 사용하겠습니다.
해시의 특성을 활용하는 분야
해시는 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색할 수 있습니다. 이런 해시의 특성은 데이터를 저장하고 검색하거나, 보안이 필요한 때에 활용됩니다. 코딩 테스트에서는 특정 데이터를 탐색하는 횟수가 많을 경우 해시를 고려하면 좋습니다. 다음은 해시가 활용되는 실제 사례입니다.
비밀번호 관리
사용자의 비밀번호를 그대로 노출해 저장하는 것은 위험하므로 해시 함수를 활용해 해싱한 비밀번호를 저장합니다. 비밀번호가 맞는지 확인할 때도 마찬가지입니다. 사용자가 입력한 비밀번호를 해싱해 확인합니다.
데이터베이스 인덱싱
데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용합니다.
블록체인
블록체인에서 해시 함수는 핵심 역할을 합니다. 각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있습니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
