Hash

Hash란?

임의의 크기를 가진 데이터(key)를 고정된 크기의 데이터(value)로 변화시켜 저장하는 것

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

Direct Addressing Table

우리가 기존에 일반적으로 사용하는 방법이다. key-value쌍의 데이터를 배열에 저장할 때 key값을 배열의 index로 직접 사용하는 방법이다. 

예를들어 10번방에 25개의 딸기가 있다는 정보를 저장할 때 10번 index에 25를 저장하는 방식을 사용하게 되는 것이다. 이 방법은 똑같은 키 값이 존재하지 않는다면 삽입시 key값을 index로 하여 저장하면 되고 삭제를 할 때는 그 key값에 해당하는 index위치를 지워주면 된다. Key값만 알고 있으면 위치를 바로 찾을 수 있으므로 탐색, 저장, 삭제, 갱신 모두 O(1) 시간에 처리할 수 있다. 하지만 Key값의 최대 크기만큼의 배열을 할당해야하기 때문에 저장해야할 index의 최대 크기가 매우 큰데 실제로 저장할 데이터가 적다면 공간을 많이 낭비할 수 있다는 단점이 존재한다.

 

Hash Table

Hash의 경우 Direct Addressing Table을 사용했을때와 다르게, key값을 직접 이용하지 않고 함수를 통해 계산을 한 후 그 결과값을 인덱스로 사용하는 방식이다. 

여기서 key값을 계산하여 알려주는 함수를 해시 함수(Hash Function)이라고 하며, input은 key값, output은 배열의 index이다. 이런 경우에 k가 h(k)로 해시 되었다고 하고 h(k)는 k의 해시값이라고 한다.

 이렇게 구성하게 되면 공간 낭비가 Direct Addressing Table에 비해 매우 적게 된다. key값의 크기가 아닌 h(k)만큼의 공간에 저장되기 때문이다. 

 

해시 함수(Hash Function)

위에 설명한 것과 같이 Key에 대한 Hash 값을 만드는 함수이다. 계산이 복잡하지 않고 키값에 대해 중복 없이 해시값을 고르게 만들어 내는 함수가 좋은 함수이다. (충돌이 적을수록 좋다는 말이다)

해시 함수에는 대표적으로 나눗셈범(Division Method)와 곱셈법(Nultiplication Method) 2가지 방법이 있다.

 

나눗셈법

원소를 해시 테이블의 크기로 나누어 나머지값을 테이블의 주소로 사용하는 방법이다. 

테이블의 크기보다 원소의 개수가 많으면 충돌이 일어난다.

가장 최적의 Hash Table Size는 키의 개수의 3배이며 2의 지수승에 근접한 소수로 하는 것이 좋다.

 

 

충돌(Collision)

키에 대한 Hash 값이 같은 경우 = 사용하고자 하는 해시 버킷이 이미 사용중인 경우에 발생한다.

해시 테이블에 문제점이 있다면 이 충돌문제이다. 어떤 특정 k라는 값을 해싱하여 h(k)라는 값을 얻었는데 이게 동일한 값을 가지는 경우가 해당한다. k1, k2라는 두개의 값을 해싱하였는데, h(k1)==h(k2)인 경우가 생길 수 있다는 것이다. 어떻게 구현하더라도 완전히 방지하기는 어려우므로 충돌을 방지하기 위한 방법이 필요하다. 하지만 완전히 충돌을 피하는 것은 거의 불가능하므로 충돌을 방지하기보다는 어느정도 허용하지만 최소화하는 방법을 주로 사용한다.

 

해결방안 1 - Chaining

충돌을 허용하지만 최소화 하기 위한 방법인 체이닝 방식이다.

체이닝 방식은 이름 그대로 데이터들을 포인터를 이용해서 체인 형태로 엮어 나가는 형태를 의미한다. 동일한 해시값이 출력되어 충돌이 일어났을 경우에 기존 데이터에 key값을 포인터로 뒤이어 연결하는 방식이다. 

따라서 최초로 h(k)위치에 저장된 데이터를시작으로

hsp1116.tistory.com/35