Map Hash(Hash Table, Hash Function)

정의

map키(key) 역할을 하는 데이터와 값(value) 역할을 하는 데이터를 짝 지어(=연결 지어) 저장하는 데이터 구조를 말한다.

키는 저장된 데이터의 구별에, 값은 그 키와 연결되어 저장된 데이터를 뜻한다. 키는 데이터 구별에 사용되기 때문에 중복되지 않는다.

 

map 인터페이스를  구현한 Concrete Class들에는 Hashmap HashTable등이 있다.

두 구현 클래스의 차이도 있겠지만 아래표로 간단하게 보고,  일단 Hash에 대해서 알아보자!

 

 

Hash를 사용하는 대표적인 자료구조는 map(c++, java), dictionary(python)등이 있다. 이외에도 hash를 사용하는 곳은 많지만, 일단은 대표적인 자료구조인, map을 중심적으로 hash를 알아보자.

 

Hash란 무엇인가?

 

고기와 감자를 잘게 다져 섞어 요리라는 뜻을 가지고 있다. 이와 유사하게, hash는 일반적으로 무언가를 잘게 쪼갠 후에 결과물을 생성하는 것이다. 컴퓨터 공학에서는 원본 데이터를 쪼개고 다지고 특정한 일련의 과정을 거처 일정한 기준의 결과물을 생성하는것을 의미한다.

그렇다면, 이러한 결과물을 생성하는 과정을 hash Function 이라 부르며, 결과물을 이용하여 데이터를 저장하는 자료구조를 hash Table이라 부른다.

 

Hash Function

 

- 임의 길이의 데이터를 넣어도 해시 함수는 항상 일정한 길이의 결과값을 출력

- 입력 데이터에서 해시값으로의 변환은 쉽고, 해시함수가 같다면 항상 동일한 값을 출력한다.

- 해시값에서 원래 데이터로의 역변환은 거의 불가능

- 해시 함수는 서로 다른 입력에 대해 동일한 해시값을 출력할 수 있다.(해시 충돌)

 

* hash function 은 여러가지 종류가 존재한다.

* m은 hash table의 capacity

perfect hash function - 입력과 출력값이 1:1 매칭이며 이상적인 형태이며, 현실에 없다. 

universal hash function - 서로 다른 입력에 출력이 같을 확률이 1 / m

c-universal hash function - 서로 다른 입력에 출력이 같을 확률이 C / m (C는 임의 상수.)

기타 division hash function, additive hash function 등 여러 해시함수가 존재한다.

 

좋은 해시함수란? 사용목적에 맞는 적절한 연산시간과 적은 충돌가능성을 고려하여 골라서 사용한다. 

 

 Hash Table

 

기본적으로 Hash Table에는 hash function 와 Array 이라는 두 가지 주요 구성 요소가 있습니다.

배열의 최대 크기(hash table의 capacity)는 해시될 것으로 예상되는 데이터의 양에 따라 다릅니다.

record = <key, value, hash code>

 

즉, key: value 데이터에서  key를 hash function에 넣어 hash code(해쉬함수의 결과물) 생성이후,

저장될 배열의 크기로 모듈러연산(%)을 수행한다. 이후  <key, value, hash code>를 저장한다. 

 

해시 테이블은 해시 함수를 사용하여 record를 삽입되거나 검색될 배열의 인덱스를 계산합니다. 

해시 테이블에서 record를 검색하는 데 필요한 평균 시간 복잡도는 합리적인 가정 하에서 O(1)이다.

하지만 서로다른 입력에 대해서 해시함수는 중복되는 결과값을 반환 할 수도 있다.

그럼 저장될 배열의 인덱스가 서로 동일하게 되는데 이것을 해시 충돌이라고 하며 다음 글에서 해결해 보겠다.