해시
오늘의 주제인 해시 자료구조는 흔히 JS에서는 객체, Python에서는 딕셔너리로 사용되며 key:value 형식의 요소들을 저장하는 자료구조입니다.
특정 요소에 바로 접근하는것을 목적으로 만들어져 요소의 삽입, 삭제, 탐색에 O(1)이라는 아주 좋은 시간 복잡도를 가지지만 그만큼 공간 복잡도를 포기한 자료구조입니다.
해시는 배열과 몇가지 차이점이 있습니다.
배열은 순차적이며 0부터 시작하는 숫자로만 이루어진 인덱스를 사용하지만
해시는 삽입순서를 기준으로 키가 정렬되고 키(인덱스)의 타입에 대한 영향을 받지 않습니다.
또한, 해시는 무결성을 검사하거나 클라우드, 블록체인, Git, DB등 다양한 분야에서 사용되고 있습니다.
해시의 구성요소
해시는 크게 해시 테이블, 해시 함수로 이루어져 있으며 이 외에도 해시 값, 버켓, 엔트리와 같은 요소들로 구성되어 있습니다.
해시 테이블 (Hash Table)
해시 맵이라고도 불리는 해시 테이블은 객체를 구현하는 자료구조로서 키와 값을 한 쌍으로 매핑해놓은 추상 데이터 타입입니다.
해시 테이블은 해시 함수를 통해 얻은 해시 값을 키로 사용하여 데이터를 저장 및 탐색합니다.
해시 함수 (Hash Function)
해시 함수는 데이터를 해시 테이블에 저장할 때와 탐색할 때 호출되는 함수를 말합니다.
데이터의 정보를 바탕으로 특정연산을 수행한 뒤 해시 테이블에 저장될 때 사용될 해시 값을 반환합니다.
데이터의 삽입, 삭제, 탐색시에 호출되기 때문에 해시 자료구조의 성능은 해시 함수와 직결되어 있습니다.
따라서, 해시 함수는 가능한 가볍고 빠른 연산이 이루어져야 하며 데이터가 테이블 전체에 고르게 저장될 수 있도록 적절한 해시 값을 반환해주어야 합니다.
해시 값 (Hash Value)
해시 코드, 체크 섬, 해시라고도 불리는 해시 값은 해시 함수에서 반환된 값으로 객체의 키, 배열의 인덱스와 같은 역할을 하며 데이터를 저장하고 탐색할 때 사용됩니다.
버켓 (Bucket)
특정 요소의 키(인덱스)를 지칭합니다.
엔트리 (Entry)
특정 요소의 값을 지칭합니다.
해시 함수의 특징 4가지
해시 함수는 다음과 같은 4가지 특징을 가지고 있습니다.
1. 고정된 길이의 출력값을 반환한다.
인풋의 크기가 어떻든 항상 고정된 길이의 해시 값을 반환합니다.
| 입력 값 | 출력 값 |
|---|---|
| a | CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB |
| abcdefghijklmnopqrstuvwxyz | 71C480DF93D6AE2F1EFAD1447C66C9525E316218CF51FC8D9ED832F2DAF18B73 |
위 예시는 해시를 이용한 암호화 알고리즘인 SHA-256을 사용한 결과 값입니다.
2. 동일한 입력값에 대해 항상 동일한 출력 값을 반환한다.
동일한 데이터를 해시 함수에 넣었을 때 수백, 수천번이 수행되더라도 항상 같은 결과값이 나와야만 합니다.
즉, 해시 함수가 결과값을 생성하는 과정에서 외부로부터 영향을 받지 않아야 합니다.
만약, 외부 영향으로 인해 같은 인풋임에도 다른 결과값이 나와버린다면 정상적으로 데이터를 탐색할 수 없게 됩니다.
3. 결과 값을 토대로 입력 값을 유추할 수 없다.
이는 해시 값이 노출되었을 때 원본 데이터를 보호하기 위함입니다.
4. 입력값의 작은 변화만으로도 완전히 다른 결과값이 출력된다.
| 입력 값 | 출력 값 |
|---|---|
| hello world | B94D27B9934D3E08A52E52D7DA7DABFAC484EFE37A5380EE9088F7ACE2EFCDE9 |
| hello worlds | 8067F1AE16F20DEA0B65BFCBD50D59014D143C8ECEBAB179D923F6EF244B40F8 |
위 두 개의 입력값은 s 한 개의 차이지만 완전히 다른 결과값이 나오는것을 볼 수 있습니다.
해시 충돌 (Collision)
해시 함수는 일반적으로 입력 값의 범위가 출력 값의 범위보다 크기 때문에 서로 다른 입력값임에도 같은 출력 값이 나올 수 있습니다.
만약, 숫자 데이터의 100을 나눈 나머지를 반환하는 해시 함수가 있다고 가정해보겠습니다.
데이터가 겹치지 않도록 1, 102, 3005와 같은 데이터들만 들어오면 좋겠지만
만약, 102, 103, 104와 같은 데이터가 들어오게 될 경우 세 개의 인풋이 모두 같은 해시 값을 반환받게 됩니다.
이렇게 서로 다른 데이터가 같은 해시 값을 가짐으로 인해서 데이터 저장시 충돌이 발생하는것을 해시 충돌이라고 합니다.
그래서, 해시 자료구조는 이러한 해시 충돌 상황을 대비해 여러 방법을 사용하고 있으며
어떤 방법을 사용하느냐에 따라 시간 복잡도는 사실 O(1)이 아닌 O(n)까지 될 수 있지만
이는 해시 함수의 로직을 피해가는 케이스만 골라서 데이터가 들어오지 않는 한 드문 일이기에 일반적인 시간 복잡도인 O(1)로 표기하고 있습니다.
그럼, 해시 충돌을 해결하는 방법에는 어떤 종류가 있는지 알아보겠습니다.
해결방법의 종류
- 체이닝 (Chaining)
링크드리스트 자료구조와 비슷하게 해시 충돌이 발생 할 경우 해당하는 요소들을 리스트 형태로 연결시키는 방법입니다.
간편한 해결 방법이지만 O(1)의 시간 복잡도를 가지는 해시 자료구조의 장점을 해친다는 단점이 있습니다.
- 개방 주소 (Open Addressing)
개방 주소 방법은 해시 충돌이 발생했을 때 특정 알고리즘을 이용해 기존 위치에서 벗어나 다른 위치에 데이터가 저장되도록 하는 방법이며 크게 3종류로 나눠집니다.
- 선형 조사 (Linear Probing)
선형 조사는 해시 충돌이 발생했을 때 해시 값의 다음 위치를 확인해보고 비어있다면 해당 위치에 저장하는 방법입니다.
만약, 해시 값이 0인 상태에서 충돌이 발생했다면 다음 위치인 1을 확인해보고 빈 자리를 찾을 때까지 다음 위치를 확인하는 방식입니다.
다만, 이 방법의 문제점은 데이터가 특정 위치 주변에 쏠리는 현상이 발생한다는 것인데
이러한 현상이 심화된다면 데이터에 대한 접근 및 탐색 비용이 증가한다는 단점이 있습니다.
- 이차원 조사 (Quadratic Probing)
이차원 조사는 위에서 말했던 특정 구간에 데이터가 쏠리는 단점을 보완한 방법입니다.
해시 충돌이 발생했을 때 한칸씩 이동하는게 아닌 n의 제곱으로 기존 위치에서 점프하는것을 말합니다.
선형 조사에 비해 넓은 폭을 가지게 되어 선형 조사의 문제점이 다소 완화될 수 있지만
같은 해시 값을 가지는 데이터가 많아진다면 이 또한 탐색에 대한 비용이 계속해서 증가하게 됩니다.
- 더블 해싱 (Double Hashing)
더블 해싱은 이름처럼 2개의 해시 함수를 사용하는것을 말합니다.
첫 번째 해시 함수는 고정된 길이의 해시 값을 반환하는 역할이며
두 번째 해시 함수는 해시 충돌이 발생했을 때 기존 위치에서 얼만큼의 보폭으로 데이터를 점프 시킬지 보폭을 반환합니다.
보통 두 개의 함수 로직 자체를 완전히 다르게 작성하기 때문에 두번 다 해시 값이 중복되는 경우는 극히 드물다고 할 수 있습니다.
