Hash 함수

 

해시 테이블

 해시 테이블은 원소의 값에 의해 결정되는 자료구조이다. 즉, 저장된 자료와의 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자리를 찾는다.

해시 함수

 임의의 원소를 해시 테이블에 저장하려면 먼저 해당 원소의 해시값을 계산한다. 해시값은 해시 함수에 의해 계산된다. 해시 함수는 키값을 입력으로 받아 해시 테이블 상의 주소를 리턴하며 다음의 두 가지 성질을 가지도록 만들어야 한다.

• 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
• 계산이 간단해야 한다.

1) 나누기 방법

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

 

 

위의 예제는 해쉬 테이블의 크기가 13 일때 해쉬함수에 25, 13, 16, 5 ,7 의 입력값이 주어진 경우이다. 25는 25mod13=12 이므로 12번째 인덱스에 저장이되었고 13은 13mod13=0 이므로 0번째 인덱스에 저장되었다.

나누기 방법의 해쉬 함수의 식은 다음과 같다.

 

소스 코드

class LinearTable
{
 
   public final int SIZE = 7;
   private HashItem[] table = new HashItem[SIZE];
   
   public int code(String key)
   {
      return (Math.abs(key.hashCode()) % SIZE);
   }
 
}

public boolean add(String key, String data)
{
 
   int probe;
   int code = code(key);
   if ( (table[code] == null) ||table[code].isDeleted() )
   {
      table[code] = new HashItem(key, data);
      probe = -1;
   }
   else
   {
      if (code == (table.length - 1))
         probe = 0;
      else
         probe = code + 1;
   }
   
   while ( (probe != -1) &&(probe != code) )
   {
      if ( (table[probe] == null) ||
           table[probe].isDeleted() )
      {
         table[probe] = new HashItem(key, data);
         probe = -1;
      }
      else
      {
         if (probe == (table.length -1) )
            probe = 0;
         else
            probe++;
      }
   }
   if (probe != -1)
      return false;
   else
      return true;
}

 

2) 곱하기 방법

 곱하기 방법은 이와 반대로 먼저 입력값을 0과 1 사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0~m-1 사이로 팽창시킨다. 이 방법에서는 해쉬 함수의 특성을 결정짓는 0<A<1 의 범위의 상수 A를 미리 준비해야 한다. 임의의 원소 x에 대해 다음과 같은 과정을 거쳐 x의 주소를 결정한다.

• x에 A를 곱한 다음 소수부만 취한다.
• 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.

정리하면, 해쉬 함수는 다음과 같다.

 

 

 

충돌

 해쉬 함수의 충돌은 체이닝 기법, 선형조사 방법등으로 해결할 수 있다

 

1. 선형 조사법

아래 그림에서 key AAA가 해시 테이블에 먼저 데이터를 저장하였고, 뒤 이어 key DDD의 해시 값이 충돌하게 된다. 선형조사법은 바로 옆의 자리가 비었는지 확인 후 비어있으면 그 자리에 데이터를 저장한다. 즉, 그림에선 48 부분에 데이터를 저장한다.

선형 조사법에서 데이터를 찾는 순서는 f(k) + 1 -> f(k) + 2 -> f(k) + 3 -> …. 순으로 진행 된다.

소스 코드

public String retrieve(String key)
{
 
   int probe;
   int code = code(key);
   if (table[code] == null)
      return null;
 
   else if (table[code].getKey().equals(key))
      return table[code].getData();
   
   else
   {
      if (code == (table.length - 1) )
         probe = 0;
      else
         probe = code + 1;
   }
   
 
   while ((probe != -1) && (probe != code))
   {
      if (table[probe] == null)
         return null;
   
      else if (table[probe].getKey().equals(key))
      {
         return table[probe].getData();
      }
 
      else
      {
         if (probe == (table.length - 1) )
            probe = 0;
         else
            probe++;
      }
   }
   
   return null;
}

 

2. 체이닝

체이닝은 닫힌 어드레스 방법으로, 충돌이 발생해도 자신의 자리에 저장하는 방법이다.

즉 동일한 해쉬 값에 대해 여러 값이 저장 될 수 있다.

아래 그림을 보자. AAA는 먼저 해시 테이블에 871이란 데이터를 저장한다. 뒤이어 DDD가 충돌이 발생하는데, 연결리스트를 이용해 동일한 45번 자리에 데이터를 연결시켜 저장한다.