Hash와 Hash Table
업데이트:
개요
해시란 무엇일까. 먼저 해시 함수(Hash Function)란 주어진 키나 문자열의 문자들을 다른 고정된 길이의 데이터(Hash)로 변환하는 단방향 함수를 말하며 이 과정을 해싱(Hashing)이라 한다.
특징
✨ 무결성
위에서 해시는 특정 데이터를 상징하는 더 짧은 (고정된) 길이의 데이터로 변환하는 것이라고 했다. 이 때 원본 데이터가 조금이라도 달라질 경우 상징하는 데이터도 그 달라진 데이터에 따라 달라지기 때문에 무결성을 지킬 수 있다.
✨ 보안성
해시는 단방향이기 때문에 복호화가 불가능하다. 다시 말해 동일한 해시값을 만들어낼 수 있는 원본 데이터의 가짓수가 무수히 많다. 때문에 쉽게 복호화를 할 수 없다는 점에서 강한 보안성을 가지게 되는 것이다.
✨ 비둘기집 원리
비둘기가 5마리, 상자가 4개일 때 비둘기를 아무리 잘 나눈다고 해도 한 상자에는 2마리가 들어가게 되는 현상을 말한다. 이는 서로 다른 입력 값의 해시 결과 값이 동일한 문제(해시 충돌)가 발생할 수 있다는 가능성을 의미한다.
활용
✨ Hash Funtion
위에서 Hash Function 은 key를 Hash 로 변환하는 단방향 함수라고 했다. 이 해시 함수는 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수이기에, 서로 다른 데이터가 동일한 해시값을 가질 수 있다. 이런 해시 충돌이 발생할 수 있다는 단점을 갖고 있지만 결정론적 작동, 무결성, 보안성 등의 특징이 있어 자료구조나 캐시, 중복/유사 레코드 검색, 에러 검출 등에 사용된다.
💡 자료구조? 원하는 값을 최대한 효율적으로 찾기 위해서 필요한 데이터 저장 구조
✨ 보안
해시의 복호화가 불가능하다는 특징 때문에 보안 분야에서도 많이 사용된다. 원래의 정보가 손실되고 해시값만 갖고 복원하는 것이 불가능해서 비밀번호, 전자서명, 전자투표 등과 같은 민감한 정보의 무결성을 검증할 때 사용된다.
✨ Hash Table
해시 테이블은 키-값 쌍의 데이터 구조로 매우 빠른 데이터 검색을 위해 사용된다. 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색 속도를 빠르게 하는 것이다.
해시 함수를 사용해 키를 해시값으로 매핑하고, 이 해시값을 인덱스나 주소로 삼아 데이터의 값을 키와 함께 저장한다. 해시 충돌을 해결하기 위해 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 알고리즘에는 Division Method, Digit Folding, Multiplication Method 등이 있다.
장점
👍 많은 데이터를 적은 리소스로 관리할 수 있어 효율적이다.
👍 인덱스에 해시값을 사용하면 모든 데이터를 탐색하지 않고도 삽입이나 삭제를 수행할 수 있다.
👍 언제나 동일한 해시값을 리턴하고, 그 인덱스만 알고 있다면 해시 테이블의 크기에 상관없이 데이터에 빠른 접근이 가능하다.
👍 키와 해시값 사이에 선형적인 연관이 없기 때문에 해시값만 갖고 키를 온전히 복원하기 어렵다. (보안성이 좋다.)
👍 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들어 데이터를 축약할 수 있다.
단점
👎 항목 수가 적다면 검색 알고리즘이 더 효율적일 수 있다.
👎 해시 충돌이 발생할 수 있다.
👎 순서 또는 관계가 있는 배열에는 어울리지 않는다.
👎 공간 효율성이 떨어진다.
👎 해시 함수의 의존도가 높다.
활용
✅ 연관배열
✅ 데이터베이스 색인화
✅ 캐시
✅ 세트
✅ 개체 표현
✅ 독특한 데이터 표현
✨ Direct-Address Table
: 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블
💡 버킷? 하나 이상의 레코드 단위
키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않는다. 그러나 이 방식은 메모리 낭비이기 때문에 보통 키 개수보다 적은 해시 테이블을 사용한다. 그렇기 때문에 해시 충돌이 발생하는 것이다.
해시 충돌
해시 충돌을 해결하는데는 다양한 방법이 있지만 이번 글에서는 분리 연결법과 개방 주소법을 알아보려고 한다.
분리 연결법 Separate Chaining
동일한 버킷의 데이터에 대해 연결(Linked) 리스트, 트리 등의 자료구조를 활용해 다음 데이터의 주소를 저장한다.
장점
👍 간단한 구현
👍 추가적인 메모리 사용 X
👍 쉬운 원소 삭제
단점
👎 캐시 효율성 감소 (데이터가 많아질 경우)
개방 주소법 Open Addressing
추가적인 메모리를 사용하는 분리 연결법과 다르게, 비어있는 해시 테이블의 공간을 활용한다. 아래 3가지 방식으로 개방 주소법을 구현하게 된다.
- ✅ Linear Probing
-
현재 버킷 인덱스로부터 고정폭 만큼 이동하여 차례대로 검색, 비어 있는 버킷에 데이터를 저장
- ✅ Quadratic Probing
-
해시의 저장 순서 폭을 제곱으로 저장
- ✅ Double Hasing Probing
-
해시된 값을 한 번 더 해싱하여 해시의 규칙성을 제거 → 더 많은 연산
댓글남기기