Hash(해시)

해시함수: 데이터의 정보를 보장하고 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 함수, 보통 key, value값이 있는 Set이나 Map을 이용하여 매핑을 하는데, 매핑 전 원래 데이터 값을 key로 매핑 후 데이터 값을 value, 매핑하는 과정 자체를 해싱이라 한다.  

해시함수를 사용하는 목적

- 메시지의 오류나 변조를 탐지할 수 있는 무결성을 제공하기 위해서 사용된다. 

해시함수를 이용해 해시값으로 바꾸는 과정

 * 데이터를 문자열로 받게 되었을 때 문자 한글자의 아스키 코드 값을 더하는 과정을 통해 문자열을 정수 값으로 바꿔나는 과정을 예시를 통해 기록하겠습니다.

 

 1. 'hello'라는 문자열이 데이터 값으로 들어옴 

 2. 'h=104,' 'e=101' , 'l=108', 'l=108', 'o=111', 각 문자들이 지니고 있는 아스키 코드로 변환

 3. 104+101+108+108+111='532', 532이라는 정수값을 해시코드로 변환 

 

* 해시함수는 여러가지 방법으로 구현할 수 있는데, 적절한 해시 함수를 구현하는 것은 개발자의 역량에 달려있다.

해시코드를 저장하는 해시테이블 

해시테이블: 해시코드로 나올 수 있는 경우의 수는 어마어마하기 때문에, 저장할 배열의 크기는 물리적인 한계가 존재한다.
 이때 사용되는 것이 해시 테이블인데, 색인(index) 혹은 주소 삼아 해시값의 키(key)와 밸류(value)를 함께 저장하는 자료구조, 검색과 저장이 용이하다. 

- 해시 테이블 -

해시테이블에서는 다음 그림과 같이 해시값이 저장됩니다.

 

index: 01

key: Lisa Smith

value: 521-8976

- 저장되는 구조 -

<해시테이블의 장점> 

  1. 적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 적합한 자료구조이다. 

  2. 하드디스크, 클라우드에 존재하는 무한 데이터들을 유한 데이터 개수의 해시 값으로 매핑하여, 해시테이블을 통해 관리하게 되면, 작은 메모리로도 프로세스 관리가 가능해진다. 

 

충돌

 1. 충돌 이유

- 해시함수는 해시값의 개수보다 많은 키값을 해시값으로 변환하기 때문에, 서로 다른 두개의 키가 같은 해시 값으로 변환되는 해시충돌이 발생하게 된다.

- 해시 충돌 문제 -

 

 2. 충돌문제 해결 방법

  가. 체이닝

   1) LinkedList를 선언한다.

   2) 충돌된 각각의 데이터들을 리스트에 저장한다.

   3) 만약 데이터를 검색하는 경우 먼저 해시테이블에 있는 인덱스에 접근한다.

   4) 그 이후, 인덱스의 존재하는 LinkedList의 데이터들을 하나씩 조회한다.

 

- 체이닝 방법 -

 

  나. Open Addressing + 선형탐사 or 제곱탐사

Open Addressing: 해시함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용

탐사: 삽입, 삭제, 탐색을 수행하기 위해 해시 테이블 내 새로운 주소를 찾는 과정

   1) 선형탐사 

    가) 해당 index 또는 주소에 다른 해시 값이 저장되어 있다면 해당 해시 값에 고정폭(예컨대 1칸)을 옮겨 다음 index 또는 주소에 접근한다.

    나) 만약 옮긴 곳에 또 다른 해시 값이 저장되어 있다면 고정폭으로 또 옮겨 접근을 시도한다. 

    다) 이를 계속 반복한다.

- 해시테이블을 이용해 해시 값 저장 -

해시 값이 해시 테이블에 잘 저장이 되다가 해시 값 92를 저장하는 과정에서 충돌이 발생할 경우 해시 테이블에 index 2번 다음 index 값인 3번에 저장하게 되는 방법을 Open Addressing 이라 한다. 

- 해시 값이 충돌이 발생한 경우 다음 주소로 해시 값을 저장 -

  해시 값이 해시 테이블에 잘 저장이 되다가 해시 값 92를 저장하는 과정에서 충돌이 발생할 경우 해시 테이블에 index 2번 다음 index 값인 3번에 저장 되는것을 볼 수있다.

   

 2. 제곱탐사 

  가) 선형 탐사와 비슷하지만, 고정폭의 값이 1이 아닌 제곱 수로 옮겨 해시 값의 중복을 피한다. 

 

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

 

<Data structures> chapter 5, 해시(Hash) end

---