티스토리 뷰
1. 해시 테이블(Hash Table)이란?
해시 테이블이란 키와 값의 대응으로 이루어진 데이터 구조이다. 예를 들어, ISBN 번호가 키라면 그에 대응하는 책 제목이 값이 된다. 만약 ISBN 번호 9791162245651을 키로 입력하면 대응하는 값으로 혼자 공부하는 파이썬이 반환된다.
해시 테이블에서는 해시 함수를 사용하여 키를 특정 버킷에 매핑한다. 버킷은 배열처럼 여러 개로 이루어진 저장 공간이다. 해시 함수는 입력된 키에 대해 인덱스를 계산해 해당 버킷에 데이터를 저장하거나 찾을 수 있도록 한다. 예를 들어, Hanbit이라는 키를 해시 함수에 입력하면 해시 함수가 계산한 인덱스 2에 데이터를 저장하게 된다. 다른 키들도 마찬가지로 해시 함수를 통해 계산된 인덱스를 기반으로 버킷에 저장된다.
2. 해시 함수 (Hash Function)
해시 함수란 임의의 길이를 갖는 데이터를 고정된 크기의 값으로 변환하는 단방향 함수이다. 단방향 함수이기 때문에 해시된 데이터를 통해 원래의 값을 도출하기 어렵다. 해시 함수는 여러 개의 알고리즘이 존재하며, 대표적으로 SHA-1, SHA-256, SHA-512, SHA3, HMAC, MD5 등이 있다. 동일한 데이터라도 사용되는 알고리즘에 따라 서로 다른 해시 값이 도출된다.
해시 함수는 동일한 입력 값이 주어지면 항상 같은 해시 값을 반환한다.
해시 함수는 주로 데이터의 무결성 검증에 사용된다. 예를 들어, 송신자가 수신자에게 이희망이라는 데이터를 전달한다고 가정한다. 송신자는 이 데이터에 해시 함수를 적용하여 aabb라는 해시 값을 얻고 이희망 데이터를 수신자에게 보낸다. 수신자는 이희망 데이터에 동일한 해시 함수를 적용해 해시 값을 계산하고 송신자가 보낸 해시 값 aabb와 비교한다. 만약 두 해시 값이 동일하다면 데이터 전송 과정에서 변경되지 않았음을 의미한다.
참고로 해시 함수는 주로 정수로 된 해시 값을 반환한다. 반환된 해시 값을 배열 형태의 버킷에 저장하기 위해서는 인덱스가 계산되어야 한다. 인덱스를 계산하는 방법으로 mod 연산, 곱셈 방법, 제곱 방법, 폴딩 방법 등이 존재한다.
3. 해시 테이블(Hash Table)의 성능
해시 테이블을 사용하는 이유는 속도가 매우 빠르기 때문이다. 데이터 삽입, 삭제, 조회에서 발생하는 시간 복잡도는 O(1)로, 배열이나 연결 리스트에 비해 훨씬 빠른 속도를 자랑한다. 그러나 해시 테이블에 저장되는 데이터가 많아질수록 메모리 공간을 많이 차지하게 되고 해시 충돌이 자주 발생하게 된다.
3-1. 해시 충돌 (Hash Collision)
해시 충돌이란 서로 다른 키가 동일한 해시 값을 갖는 것을 말한다. 키는 다르지만 동일한 해시 값을 가질 경우 데이터의 무결성 검증에 문제가 발생할 수 있다.
- 송신자가 shattered-1.pdf 파일과 해시 값 3876을 수신자에게 전달한다.
- 전달되는 중간에 shattered-1.pdf 파일이 shattered-2.pdf로 변경된다.
- 수신자는 변경된 shattered-2.pdf 파일을 받고 해당 파일의 해시 값을 계산했을 때 3876이 나온다.
- 수신자는 변경된 파일을 받았으나 해시 값이 동일하기 때문에 중간에 파일이 변경되지 않았다고 판단하게 된다.
- 그러나 실제로는 중간에 파일이 바뀌었음에도 불구하고 동일한 해시 값을 반환하여 데이터 무결성 검증이 제대로 수행되지 않는 문제가 발생한다.
3-2. 해시 충돌 해결하는 2가지 방법
해시 충돌을 해결하기 위해서 체이닝과 개방 주소법이 사용된다.
1. 체이닝 방식은 서로 다른 키가 동일한 해시 값을 반환하는 경우 연결 리스트로 연결하는 방법이다. 예를 들어, 해시 함수 결과로 동일한 인덱스를 갖는 키 39와 13이 있을 경우, 39번 키를 먼저 저장하고 그 뒤에 13번 키를 연결 리스트로 연결한다.
체이닝 방식을 구현하는 아이디어는 간단하지만 연결 리스트의 노드가 많아질수록 데이터 탐색 속도가 느려진다. 해시 테이블을 사용하는 이유는 O(1)이라는 시간 복잡도를 제공하기 때문인데 연결 리스트의 노드가 많아지면 O(N)으로 성능이 저하될 수 있다. 예를 들어, 서로 다른 N개의 키가 동일한 해시 값을 갖는 경우 하나의 연결 리스트에 여러 노드가 연결된다.
2. 개방 주소법 방식은 해시 충돌이 발생하였을 때, 충돌이 발생한 버킷에 저장하지 않고 비어있는 다른 인덱스에 데이터를 저장하는 방식이다. 충돌이 발생했을 때 비어있는 버킷을 찾는 과정을 조사(probe)라고 한다. 개방 주소법에는 다양한 조사법이 존재한다.
선형 조사법(Linear Probe)은 충돌이 발생한 인덱스의 다음 인덱스부터 순차적으로 비어있는 인덱스를 찾는 방법이다. 하지만 이 방법은 데이터 군집화 문제를 발생시킬 수 있다. 즉, 해시 충돌이 발생한 인덱스 주변에 여러 데이터가 몰리게 되면서 탐색이 느려질 수 있다.
또 다른 해싱 충돌 해결 방법으로는 이중 해싱(Double Hashing)이 있다. 이중 해싱은 두 개의 해시 함수를 사용하여 버킷의 인덱스를 계산하는 방법이다. 먼저 첫 번째 해시 함수를 사용하여 버킷을 계산한 후, 충돌이 발생하지 않으면 그대로 저장하고, 충돌이 발생한 경우 다른 해시 함수를 한 번 더 적용한다.
이중 해싱을 사용하면 여러 개의 해시 함수로 무작위로 분산된 인덱스를 계산할 수 있기 때문에 선형 조사법에서 발생하는 군집화 문제를 완화할 수 있다.
참고
https://m.yes24.com/Goods/Detail/130179291