자료구조 - 해시(Hash)란?

해시(Hash)

 

---

• 해시란 ?

 

 해시를 정리해둔 글을 살펴보면  "해시는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말합니다. 쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수입니다. " 라고 말합니다.

 

해시를 많이 사용해본 저도 한 번에 이해하기 어려운 문장입니다. 

 

제가 이해하고 있는 개념으로 해시의 사용을 설명해보자면 다음과 같습니다. (개인적인 견해이므로 맹신하지는 말아주세요)

 

 

1.  어떠한 값(데이터)을 해시화하여 만들어진 결괏값 그 자체.

    대표적으로 정보의 암호화를 예시로 들겠습니다.회원가입시에 사용자의 민감정보인 비밀번호화 같은 데이터들은 날 것 그대로 데이터베이스에 저장할 수 없습니다. 당연히 보안에 취약하기 때문이죠. 이를 해결하기 위해 해시 암호화 알고리즘을 사용하여 민감정보들을 해시처리하여 저장히게 됩니다.  여기서 알 수 있는 해시의 특징은 단방향성을 띄고 있다는 점입니다. 예를 들어 "1"이라는 값을 해시처리하여 "gsagsdreq" 라는 값으로 사용한다고 가정할 때, 어떤 해시 함수를 사용했는지 모른다면 "gsagsdreq"라는 값으로 "1"이라는 원래의 값을 도출하기는 불가능에 가깝습니다. (100% 불가능인지는 확실하지 않습니다.)

 

 

2.  어떠한 Key값(데이터)을 해시화하여 만들어진 결괏값과 Value의 매핑

 

  이 때의 해시값은 주로 Key와 Value로 이루어진 데이터에 사용합니다. Key값을 Index로 하여 검색 및 저장이 O(1)로 매우 빠르게 수행되는 자료구조입니다. 제가 주로 사용하는 언어인 Python에서 Dictinary와 같은 자료구조의 Dic[Key] = Value의 형태 또는 Dic = {  Key : Value  }의 사용에서 쓰이는 방법이 해시입니다.

 

---

• 해시함수란? 

 

 해시함수는 해시값을 만들기 위해 사용되는 함수입니다. 

해시함수는 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 해시함수라고 할 수 있습니다. (충돌이 일어나지 않을수록 좋다)

주로 사용되는 방법으로는 나눗셈법(Division Method)와 곱셉법(Multiplication Method)이 있습니다.

 

 

1. 나눗셈법 (Division Method)

 

 원소를 해시테이블의 크기로 나누어 나머지값을 테이블의 주소로 사용하는 방법으로 테이블의 크기보다 원소의 갯수가 많으면 충돌이 일어난다

 

 

2. 곱셈법 (Multiplication Method)

 

 숫자로 된 키가 k이고 A는 0과 1 사이의 실수일 때 곱셈법은 다음과 같이 정의됩니다. m이 얼마가 되든 크게 중요하지는 않으며 보통 2의 제곱수로 정한다고 합니다. 

또한, 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해시함수라고 합니다.

h(k)=(kA mod 1) × m

 

---

• 해시테이블 (Hash Table)

 

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있는 자료구조입니다. 

위 2번에서 언급한 개념이라고 생각하면 됩니다. 이는 Key값을 해시함수로 해시화하여 Index로 접근하기 때문에 검색 및 데이터의 수정에서 O(1)로 매우 빠른 성능을 보여줍니다. Key값에 매핑되어 데이터가 저장되어있는 부분을 버킷이라고 합니다. 

 

이미지 출처: https://mangkyu.tistory.com/102 [MangKyu's Diary]

 

 

---

• 해시충돌(Hash Collision) 

 

 해시 충돌이란 다른 키값을 가진 데이터가 같은 해시값을 가지게 되어 충돌하는 현상입니다.

 

 만약 N의 사이즈를 가진 해시테이블에 N+1개의 데이터를 해싱하여 넣는다면 비둘기집의 원리에 의해 반드시 해시 충돌이 일어나게 됩니다. 

해시충돌의 해결방법으로는 크게 Chaining과 Open Addressing의 두 가지 방법이 있습니다.

 

 

1. Chaining 

 

• 충돌이 일어날 경우 데이터들을 포인터를 이용해 서로 링크드 리스트(체인)형태로 연결하는 것
• key값을 포인터로 이어서 연결
• 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐
• JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있다

 

2. Open Addressing

 

• 모든 데이터를 테이블에 저장하는 방법
• 사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용
• 포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다
• 하지만 테이블의 크기가 커질수록 장점이 사라진다

---