[자료구조] 해시(Hash)

해시(Hash)는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값이다. 

이를 이용하면, 특정한 배열의 인덱스나 위치, 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다.

 

기존에 사용했던 자료 구조들은 탐색이나 삽입시에 시간복잡도 O(n)이상을 가지지만 해시를 이용하면 즉시 저장하거나 값을 꺼내올 위치를 참조 할 수 있으므로 기존 보다 더 빠른 속도로 탐색이 가능해진다.

 

해시에는 아래의 특징을 보유하고 있다.

1. 무결성

 해시는 key와 value 구조라고 봐도 되는데, 이때 value를 더 짧고 유일한 key 값으로 맵핑해준다는 점에서
 무결성을 지키는 데에 많은 도움이 된다.

2. 보안성

 해시는 기본적으로 복호화가 불가능하다는 특징이 있다. 
 처음부터 복호화가 불가능하게 설계되어 있어 보안에 유리하다.
 실제로 많은 서비스등에서 비밀번호등을 저장할때 해시 암호화를 이용한다.

 

---

해시는 블록체인, IPFS(InterPlanetary File System)등 다양한 분야에서 활용되고 있다.

자료구조 측면에서 살펴보면 해시함수, 해시테이블, 해싱등이 있다.

 

1. 해시 함수

 

해시 함수는 임의의 길이를 가지는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다.

데이터의 효율적인 관리를 위해 사용하는 함수로 매핑 전 데이터(원래 데이터)의 값을 key, 매핑 후 데이터의 값을 hash value, 매핑하는 과정 자체를 hashing이라고 한다.

 

해시 함수는 보통 해시값의 개수보다 많은 키 값을 해시 값으로 대응하기 때문에, 해시 함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시 충돌(collision)이 발생할 수 있다.

John과 Sandra의 해시 값이 충돌하고 있다.

2. 해시 테이블

 

해시 함수를 이용해서 키를 해시 값으로 매핑하고, 이 값을 인덱스 또는 주소로 삼아 데이터의 value를 key와 함께 저장하는 자료구조를 의미한다. 이 때 데이터가 저장되는 곳을 버킷 또는 슬롯이라고 부른다.

해시 테이블의 기본 연산은 다음과 같다. => [삽입, 삭제, 탐색]

위 구조는 인덱스에는 01, 데이터에는 (Lisa smith, 521-1234) 식으로 들어가는 구조이다.

 

 

현재 존재하는 거의 모든 해시 함수는 충돌을 일으킨다. 그럼에도 불구하고 해시 함수를 이용한 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서 이다.

클라우드나 HDD에 존재하는 무한의 가까운 데이터(키)들을 유한한 개수의 해시 값으로 매핑하면서 작은 캐시 메모리로도 프로세스를 관리 할 수 있게 되기 때문에 많이 사용된다.

---

그러면 어차피 많이 사용하기 때문에 조금이라도 충돌을 줄여가면서 쓰고자 하는 노력들이 생겼다.

이 중 간단한 아이디어 하나는 다음과 같다.

(Chaining) 한 버킷당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음으로서 모든 자료를 해시 테이블에 담는 것

해당 버킷에 이미 데이터가 있다면 체인 처럼 노드를 추가 하여 다음 노드를 가리키는 방식 즉 연결리스트로 구현하기 때문에 유연하게 작동할 수 있다. 다만, 메모리 문제를 야기할 가능성이 있다.

 

---

해시 자료구조에 대한 알고리즘 문제는 다음과 같은 것들이 있다.

https://www.acmicpc.net/problem/15829

15829번: Hashing

https://programmers.co.kr/learn/courses/30/lessons/42577

코딩테스트 연습 - 전화번호 목록

 

 

---

[참고 문헌]

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

http://wiki.hash.kr/index.php/%ED%95%B4%EC%8B%9C