Hash

Monday. July 22, 2019 - 2 mins

1. Hash란?

해시란 임의길이의 데이터를 고정된 데이터의 크기로 변환하는 것을 말한다. 변환된 데이터를 우리는 해시코드, 해시섬으로 말할 수 있다. 해시코드를 사용함으로써 특정 배열의 인덱스를 찾거나 그 배열안에 있는 값을 얻어낼 수 있다. 해시를 이용하면 특정 데이터에 대한 값을 바로 찾아 낼 수 있기 때문에 빠른 속도로 일을 처리할 수 있다.

2. Hash Function

해시함수는 여러가지가 있지만 그중에서 division method에 대해서 설명을 하자면 modular연산을 통해서 인덱스를 색출해내는 방법이다. Key값을 k라고 한다면 인덱스는

 int index = hashFunction("key") % m ;

식으로 얻어 낼 수 있고 index의 범위는 0 ~ m전까지의 수로 나타내어진다. 여기서 우리는 modular 연산하는데 있어서 m의 값을 정하는게 중요한데 보통 key값의 3배가 정당하다고 한다.혹은 2의 지수승에 근접한 수가 좋다고한다. 또한 해시함수는 임의의 키값에 대해서 임의의 해시값이 고르게 분포되어 질 수 있도록 하는게 좋은 해시 함수이다.
이렇게 해시함수로 얻어낸 HashCode는 데이터에 대한 고유한 정숫값을 말한다. 객체를 비교할 때 우리는 equals()를 사용하여 객체를 비교하는데 이 때 HashCode를 보고 비교하게 된다. 그렇지만 String 클래스에서는 조금 다르다. HashCode는 객체마다 고유한 정숫값을 가지고 있다고 했지만 실제로

String a = "Java";
String b= new String("Java");

//a, b 객체는 서로다른 객체이므로 고유한 정숫값을 가져야하는게 맞지만
//실제 해쉬코드 값은 같은 값을 보여주게 된다.
a.hashCode() = 3254818
b.hashCode() = 3254818

이러한 이유는 String 클래스에 제공하는 hashCode()의 구현이 실제로 Object클래스의 hashCode()와는 다르게 재정의 하여 구현이 되어 있기 때문이 다. 또한 다른 객체라 하더라도 hashCode값은 동일할 수 있는데 이렇기에 우리는 equals를 통해 false값이 나오더라도 hashCode의 값이 꼭 다를 필요 가 없다는것을 알아야한다.

3. Collision (충돌)

Hash 함수로 얻어낸 해시코드의 값을 사용하여 HashTable을 만들어 값을 저장하는경우 같은 해시코드값에 대하여 충돌이 일어날 수 가 있다. key값이 다르더라도 해시코드가 같은 값을 주는 경우가 있다. 그렇기에 우리는 최소한의 충돌을 해결하며 일을 처리해야 한다.

3-1. Open Addressing

Linear Probing: 해시함수에서 같은 index가 나왔을경우 그 다음 index에 저장하는 방식이다. 이러한 방법은 데이터가 적을 경우 효율적이다. 데이터가 많게 되면 캐쉬 적중률 (hit ratio)가 낮아지기 때문이다. 또한 데이터가 많으면 삭제를 할경우 처리하기가 까다롭기 때문에 데이터가 적은 경우 사용하는 것이 적절한 방법이다. 이러한 방법은 Linear Clustering 문제가 발생할 수 있는데 key값이 계속해서 겹칠경우 데이터가 응집할 수 있고 이러한 경우 데이터가 많은 경우에 탐색하는데 있어서 굉장히 많은 시간을 소요할수 있다.

[참고] https://en.wikipedia.org/wiki/Linear_probing
Qudratic Probing: Linear Probing에서 발생하는 Clustering문제를 해결하기 위한 방법으로 해시함수를 이차식으로 만듬으로써 충돌을 최소화하는 것이다.

  h(i,k) = ( h'(k) + c1*i^2 + c2*i) mod m

Doubling Hashing: 이 방법은 해쉬함수 두개를 이용하여 충돌을 회피하는 방법으로 충돌이 발생 했을경우 두번째 해시함수를 사용하여 나온 값만큼 이동하여 충돌을 회피하는 방법이다.

3-2. Chaining

인덱스가 겹칠경우 그 위치에 있는 데이터의 키값의 포인터로 다음 노드를 생성하고 그 노드의 주소값을 가지고 있게 함으로써 충충돌 문제를 해결할 수 있다. 또한 삭제할 경우 그 처리가 간단하다는 점이 있다. 그러나 이 방법 역시도 하나의 인덱스에 데이터가 밀집 될 경우가 있어 그 경우에는 트리로 구현하는 것이 더 좋다고 한다.

[참고] https://www.cnblogs.com/davenkin/p/java-collections.html

최근 알고리즘 문제를 풀면서 해쉬를 언제 어떻게 사용해야하는지 익히는 중인데 이 포스팅을 하면서 해쉬의 개념을 다시 알게 되면서 도움이 되고 있는것 같다. 문제를 풀면서 새롭게 알던것을 계속해서 추가하면서 수정할 것이다.

TaeSeong Min

A Man who develops the software with coffee