[PART3] 데이터베이스/자료구조 - TERMS 06

[ TERMS 06 ]  해시

해시 과정을 설명해주는 이미지 (출처 : https://www.prasams.com/the-basics-of-hashing-a-key-concept-in-computer-science/)

 

1. 해시(Hash)의 정의

 해시는 데이터를 저장하고 검색할 때 사용하는 자료 구조 중 하나이다. 정확하게는 특정한 함수를 사용하여 추출한 값을 활용하는 것이다. 해당 함수는 해시 함수라 불리며 해시 함수는 입력되는 데이터들끼리 충돌이 발생하지 않게 정리하는 알고리즘이다. 해시 함수의 구현 방법에 따라 사용 용도와 성능이 달라진다.

 

2. 해시는 어떻게 접하게 될까?

 해시는 주로 양이 많은 데이터를 저장하거나 검색할 때, 해시를 암호처럼 활용해서 데이터를 보호할 때 접하게 된다. 메시지 인증 코드, 디지털 서명, 비밀번호 등 암호학, 검색 자료 구조를 다룰 때 접하는데 이는 소프트웨어의 변경을 검출할 때 활용되는 방법이다. 응용 소프트웨어를 배포할 때 파일이 변조되는 경우가 종종 있다. 개발자는 이런 문제를 예방하기 위해 해시 값을 비교하여 파일이 변경되었는지 검사한다.

 

3. 해시 알아보기

>  개념

 해시는 입력 데이터를 고정된 길이의 데이터로 변환한 값이다. '해시 값, 해시 코드, 체크섬'이라고도 부르며 해시 함에 의해서 얻어지는 결과 값이다. 간단하게 말하자면, 데이터의 키 값이 해시 함수를 통해서 변환된 간단한 정수이다. 이렇게 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용된다.

해시를 활용하여 비밀번호를 저장하는 과정을 설명하는 이미지 (출처 : https://www.simplilearn.com/tutorials/cyber-security-tutorial/sha-256-algorithm)

 

>  구성 요소

• 해시 함수(Hash Function)

 해시 함수는  입력받은 데이터를 해시 값으로 출력시키는 알고리즘이다. 이렇게 출력된 해시 값은 알고리즘에 따라 다양한 형태를 보이기 때문에 목적에 맞게 다양하게 설계되고 자료 구조, 캐시, 검색, 에러 검출 등 여러 분야에서 유용하게 사용된다. 보통 복잡하지 않은 알고리즘으로 구현되기 때문에 CPU, 메모리 같은 시스템 자원을 덜 소모한다는 특징이 있다. 입력된 데이터가 같으면 해시 값도 항상 같으며, 고른 범위에 균일하게 분포한다.

 

• 해시 테이블(Hash table)

 해시 테이블은 키와 값을 함께 저장해 둔 데이터 구조이다. 데이터가 행과 열로 구성된 표에 저장되었다고 이해하면 쉽다. 여기서 값이 저장되는 공간을 버킷(bucket) 또는 슬롯(slot) 이라고 한다.

Index	Name
1	James
2	Bori
3	Johny
4	gg
5	Soo

 

 해시 테이블은 신속한 저장 및 검색을 위해 만들어졌다. 해시 값을 인덱스로 환산해서 저장하는 것이 기본 원리이며, 필요한 데이터를 찾을 때 순서를 지킬 필요없이 저장 위치를 즉시 알아낼 수 있다. 그렇기 때문에 데이터의 양이 많아져도 검색에 소요되는 시간은 항상 같다. 즉, 데이터의 양과 상관없이 빠르게 검색할 수 있다.

 해시 테이블은 데이터를 저장할 때 위치가 무작위로 지정되기 때문에 여유 공간이 생기는데, 이것은 장점이 될 수 있따. 데이터가 입력되지 않은 여유 공간이 많을수록 문제없이 좋은 성능을 발휘하기 때문이다.

 

>  해시를 구하는 과정

• 해싱(Hashing)

해싱의 과정을 요약한 이미지 (출처 : https://byjus.com/gate/hash-function-in-data-structure-notes/)

 해싱은 앞에서 설명한 해시 함수를 통해서 해시 값을 출력하고, 해시 테이블에 저장하고, 검색하는 모든 과정을 말한다. 자료 구조 중 배열(array)과 연결리스트(linked list)의 단점을 보완하기 위해 두 가지를 조합한 형태이다.

해싱의 예시 이미 (출처 : https://www.spiceworks.com/it-security/data-security/articles/what-is-hashing/)

 위의 그림을 통해서 해싱을 이해하자면 각 이름은 키, 그리고 스토리지에 저장되어 있는 전화번호는 키 값이다. 먼저 이름들을 해시 함수를 통해서 정수인 해시 값으로 출력한다. 그런 다음 서로 다르게 나온 해시 값을 인덱스로 환산한다. 환산이 되면 해당 인덱스에 맞게 해시 테이블에 저장된다. 이제 James의 전화번호를 검색하면 해당 인덱스에 바로 접근할 수 있다. 이렇게 해싱을 통해 각 사람들의 번호를 쉽게 검색할 수 있다.

 

• 해싱 구현 기법

 해싱을 구현하는 방법은 정적 해싱, 동적 해싱 두 가지가 있다. 정적 해싱은 해시 테이블의 버킷 개수를 고정한 후 사용하는 기법이다. 이는 주로 데이터의 개수를 이미 알고 있을 때 사용한다. 동적 해싱은 '확장성 해싱'이라고도 하며, 데이터의 개수를 정확하게 모를 때나 데이터의 양이 가변적일 때 사용하는 기법이다. 기본 원리는 해시 테이블의 크기를 변화시키는 것이다.

 

4. 해시를 사용하는 이유

 자료 구조에는 해시와 유사한 배열과 연결리스트 등이 있다. 배열은 내부 인덱스를 이용하여 자료 검색을 한 번에 이루어지게 하여 빠른 검색에 장점이 있다. 그러나 데이터를 삽입하거나 삭제할 때는 데이터를 이동시켜야 해서 많은 시간이 소요된다. 연결리스트는 데이터를 삽입하거나 삭제할 때 빠른 처리가 가능하다는 장점이 있지만, 검색할 때 처음부터 순회 검색을 해야 하는 단점이 있다. 이 때문에 배열과 연결리스트는 데이터의 양이 많아질수록 효율이 떨어지게 된다. 이러한 단점을 보완하기 위해 해시를 사용한다. 또한 해시를 암호처럼 활용해서 데이터를 보호할 수도 있다.

 

5. 해시 더 알아보기

>  해시를 사용할 때 발생하는 문제

• 해시 충돌

 해시 함수를 통해서 해시 값을 출력했을 때 두 개 이상의 같은 해시 값을 출력해서 한 버킷에 데이터가 집중되는 경우가 있다. 이를 '충돌(collision)이 발생했다'라고 하여 '해시 충돌'이라고 부른다.

해시 충돌의 예시를 보여주는 이미지 (출처 : https://www.geeksforgeeks.org/what-is-hashing/)

 

 충돌이 발생하는 첫 번째 이유는 해시의 표현 범위가 작기 때문이다. 키는 데이터 형태가 문자열인 경우도 있고, 표현 가능한 범위가 무한이다. 반면 해시는 '정수'개 밖에 제공하지 못한다. 그래서 아무리 해시 함수의 알고리즘을 잘 짜도 표현하는 데 한계가 있다. 두 번째 이유는 해시 테이블의 인덱스의 개수보다 키의 개수가 많기 때문이다.

 

• 해시 충돌 해결하기

 해시 충돌이 많을수록 해시 테이블의 성능이 저하되기 때문에 해시 충돌을 최소화해야 한다. 해시 충돌을 최소화하는 첫 번째 방법은 체이닝(Chaining)방식으로, 해시 충돌이 발생하면 키에 해당하는 데이터들을 연결하는 방법이다. 충돌 발생시 해당 버킷을 연결리스트 방식으로 추가한다. 체이닝 기법은 삭제 또는 삽입이 간단하지만, 작은 데이터들을 저장할 때는 오버헤드가 부담이 된다.

체이닝 방식을 설명하는 이미지(출처 : https://www.geeksforgeeks.org/implementation-of-hash-table-in-python-using-separate-chaining/)

 

 두 번째 방법은 개방 주소법(Open Addressing) 방식으로, 해시 충돌이 발생하면 선형 탐색(Linear Probing), 제곱 탐색(Quadratic Probing), 이중 해싱(Double Hashing) 등을 통해서 해시 테이블 내의 주소를 탐색한 후 빈 버킷에 데이터를 저장하는 방식이다. 개방 주소법의 장점은 체이닝 처럼 포인터와 추가적인 메모리가 필요없어 오버헤드의 부담이 적다는 것이다.

선형 탐색으로 개방 주소법을 적용한 사례의 이미지 (출처 : https://en.wikipedia.org/wiki/Open_addressing)

 

 선형 탐색은 해시 함수로부터 얻어 낸 주소에서 다음 주소로 이동한 후 탐색하는 방법이다. 다음 주소로 이동할 때 일정한 폭으로 이동한다는 특징이 있다. 제곱 탐색은 선형 탐색과 유사하나 이동폭이 제곱수로 늘어나서 탐색하는 방법이다. 마지막으로 이중 해싱은 충돌이 발생하면 제2의 해시 함수를 만들어서 새로운 해시 값을 계산하는 방법이다.

 

>  함께 알아 두면 좋은 용어

• 자료 구조
• 배열
• 연결리스트
• 해시 맵(HashMap)