해싱

바라는 것이 있다면 절대 잊지 말 것.

해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조를 해시 테이블이라 부르며, 해시 테이블을 이용한 탐색을 해싱이라 한다. 해싱은 많은 응용 프로그램에서 사용된다. 예를 들어서 컴파일러가 사용하는 심볼 테이블, 철자 검사기, 데이터베이스 등에서 해싱을 사용한다.

해싱은 일상생활에서서의 정리 정돈으로 비유할 수 있다. 우리 주위에는 정리 정돈을 잘하는 사람도 있고 그렇지 않은 사람도 있다. 정리 정돈을 잘하는 사람은 물건들을 항상 제자리에 둔다. 예를 들면 열쇠는 항상 책상위에 두는 식이다. 정리정돈을 잘 못하는 사람은 물건들을 섞여있는 상태로 두었다가 필요할 때 하나씩 탐색한다. 해싱은 물건을 잘 정리하는 것과 같다. 각 물건마다 고유한 위치가 있고 그 위치에 그 물건을 보관하는 것이다. 그 물건이 필요하면 바로 그 위치를 찾아가면 된다. 해싱은 보통 사전이라는 자료 구조를 구현할 때의 최상의 선택이 된다.

사전은 (키,값) 쌍의 집합이다.

사전은 키와 관련된 값을 동시에 저장하는 자료구조이다. (키, 값) 쌍을 저장할 수도 있고 (키,값 )쌍을 삭제할 수도 있으며 키를 가지고 값을 검색할 수 있다. 사전은 맵(map)이나 테이블(table)로 불리기도 한다.

• 키(key) : 사전의 단어처럼 항목과 항목을 구별시켜주는 것
• 값(value) : 단어의 설명에 해당한다.

* 추상자료형                         
객체 : 일련의 (key, value) 쌍의 집합
연산 : 
  add(key, value) : (key, value)를 사전에 추가한다.
  delete(key) : key에 해당되는 ( key, value )를 찾아서 삭제한다. 고나련된 value를 반환하다. 만약 탐색이 실패하면 NULL을 반환한다. 
  search(key) : key에 해당되는 value를 찾아서 반환한다. 만약 탐색이 실패하면 NULL을 반환한다. 

해싱의 기본적인 아이디어는 간단하다. 만약 어떤 회사의 직원이 100명이라고 하자. 100명의 직원들은 0에서 99까지의 아이디를 부여받는다. 직원들에 대한 정보를 가장 빠르게 저장하고 탐색하려면 어떻게 해야할 까? 쉽게 생각할 수 있지만 단순히 크키가 100인 배열을 만들면 됩낟. 자료를 저장하거나 탐색하려면 직원의 아이디를 키로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 된다. 이들 연산들의 시간 복잡도는 명백하고 O(1)이다. 즉 상수 시간 안에 종료할 수 있다. 그러나 현실적으로는 탐색 키들이 문자열이거나 매우 큰 숫자이기 때문에 탐색 키를 직접 배열의 인덱스로 사용하기에는 무리가 있으므로 각 탐색 키를 작은 정수로 사상시키는 어떤 함수가 필요하다.

해싱이란 이런식으로 어떤 항목의 키만을 가지고 바로 항목이 들어있는 배열의 인덱스를 결정하는 기법이다. 해시 함수란 키를 입력으로 받아 해시 주소를 생성하고 이 해시 주소를 해시 테이블의 인덱스로 사용한다.
해시 함수란 키를 입력으로 받아 해시 주소를 생성하고 이 해시 주소를 해시 테이블의 인덱스로 사용한다. 이 배열의 인덱스 위치에 자료를 저장할 수도 있고 거기에 저장된 자료를 꺼낼 수도 있다.

add(key, value) :
    index <- hash_function(key)
    ht[index] = value;

search(key) :
    index <- hash_function(key)
    return ht[index];

해시 함수Permalink

해싱에서는 키 값을 해시 테이블의 주소로 변환하는 해시 함수가 잘 설계되어야만 탐색의 효율이 증대될 수 있다.

• 충돌이 적어야 한다.
• 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다.
• 계산이 빨라야 한다.

제산 함수Permalink

나머지 연산자를 사용하여 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법이다. 즉 키 k에 대하여 해시 함수는

h(k) = k mod M

으로 하는 것이다. 여기서 M은 해시 테이블의 크기로서 해시 함수의 값의 범위는 0 ~ ( M ~ 1)이 된다. 따라서 해시 테이블의 인덱스로 사용하기에는 이상적인 값이 된다. 이는 가장 일반적인 해시 함수로서 해시 테이블의 크기 M는 주로 소수로 선택한다. 이 방법은 다양한 응용분야에서 쉽게 적용할 수 있을 뿐만 아니라, 해시 주소를 상당히 고르게 분포시키는 좋은 방법이다.

int hash_function(int key){
  int hash_index = key % M;
  if ( hash_index < 0 ) {
    hash_index += M;
  }
  return hash_index;
}

폴딩함수Permalink

폴딩 함수는 주로 키가 해시 테이블의 크기 보다 더 큰 정수일 경우에 사용된다. 예를 들어 키는 32 비트이고 해시 테이블의 인덱스는 15 비트 정수인 경우이다. 만약 이런 경우, 키의 앞의 16비트를 무시하고 뒤의 16비트를 해시 코드로 사용한다면, 앞의 16비트만 다르고 뒤의 16 비트는 같은 키의 경우, 충돌이 발생할 것이다. 따라서 키의 일부만 사용하는 것이 아니고 키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR 같은 부울 연산을 하는 것이 보다 좋은 방법이다. 이것을 폴딩이라고 한다.

hash_index = (short)( key ^ (key >> 16))

폴딩함수는 키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용한다. 키를 나누고 더하는 방법에는 이동 폴딩과 경계 폴딩이 대표적이다. 이동 폴딩은 키를 여러 부분으로 나눈 값을 더하여 해시 주소로 사용하고, 경계 폴딩은 키의 이웃한 부분을 거꾸로 더하여 해시 주소를 얻는다.

폴딩 함수는 주로 탐색 키가 해시 테이블의 크기보다 더 큰 정수 일 경우에 사용된다. 예를 들어 탐색 키는 32비트이고 해시 테이블의 인덱스는 16비트 정수인 경우를 고려하자. 이 경우, 탐색 키의 앞 16비트를 무시하고 뒤 16비트는 해시 코드로 사용한다면, 앞의 16 비트만 다르고 뒤의 16 비트는 같은 탐색이 인 경우 충돌이 발생할 것이다. 따라서 탐색 키의 일부만 사용하는 것이 아니고 탐색 키를 몇 개의 부분으로 나누어 이를 더하거나 비트별로 XOR 같은 부울 연산을 하는 것이 더욱 바람직하다. 이 것을 폴딩이라고 한다.

hash_index = (short)(key ^ ( key >> 16 ))  

중간 제곱 함수Permalink

중간 제곱 함수는 키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 제곱한 값의 중간 비트들은 대게 키의 모든 문자들과 관련이 있기 때문에 서로 다른 키는 몇 개의 문자가 같을 지라도 서로 다른 해싱 주소를 갖게된다. 키 값을 제곱한 값의 중간 비트들의 값은 비교적 고르게 분산된다.

비트 추출 방법Permalink

비트 추출 방법은 해시 테이블의 크기가 M=2^k 일 때 키를 이진수로 간주하여 임의의 위치의 k 개의 비트를 해시 주소로 사용하는 것이다.

숫자 분석 방법Permalink

숫자 분석 방법은 숫자로 구성된 키에서 각각의 위치에 있는 수의 특징을 미리 알고 있을 때 유용한다. 키의 각각의 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법이다.

탐색키가 문자열 일 경우 주의할 점Permalink

키들이 정수 일 대는 비교적 쉽게 해시주소로 변환할 수 있다. 그러나 많은 경우, 키들은 문자열일 수 잇다. 따라서 문자열로 부터 좋은 해시 주소를 생성하는 것이 중요하다. 대재 문자열 안의 문자에 정수를 할당하여 바꾸게 된다. 예를 들면 a 부터 z에 1부터 26을 할당할 수 있다. 그러나 가장 보편적인 방법은 문자의 아스키 코드 값이나 유니 코드 값을 사용하는 것이다. 가장 간단한 방법은 첫 번째 문자의 아키스 코드 값이나 유니 코드 값을 사용하는 것이다. 예를 들어 문자열을 해시 주소로 바꾼다고 생각해보자. 이 방법을 사용하면 “book” 과 “cup”은 구별 할 수 있다. 그러나 “cup”과 “car”는 구별이 불가능하다. 따라서 충돌을 막기 위해서는 문자열 안의 모든 문자를 골고루 사용해야 할 것이다. 가장 보편적인 방법은 각 문자의 아스키 코드 값을 모두 더하는 것이다. 그러나 문제점은 키들이 동일한 문자로 이루어져 있지만 위치가 다른 경우, 즉 “cup”과 “puc”와 같은 키들은 구분할 수 없을 겻이다. 또한 아스키 문자 코드 범위가 65에서 122이기 때문에 약 3자리로 이루어진 키의 경우, 195 에서 366으로 해시코드가 집중될 것이다. 더 좋은 방법은 글자 들의 아스키 코드 값에 위치에 기초한 값을 곱하는 것이다. 즉 문자열 s가 n개의 문자를 가지고 있다고 가정하고 s안의 i번째 문자가 u라고 하면 해시 주소는 다음과 같이 계산하는 것이다.

int hash_function(char *key){
  int hash_index = 0;
  while(*key)
    hash_index = g * hash_index + *key++;
  return hash_index;
}

개방 주소법Permalink

충돌과 오버플로우Permalink

충돌이란 서로 다른 키를 갖는 항목들이 같은 해시주소를 가지는 현상이다. 충돌이 발생하고, 해시 주소에 더 이상 빈 버킷이 남아 있지 않으면 오버 플로우가 발생한다. 오버 플로우가 발생하면 해시테이블에 항목을 더 이상 저장하는 것이 불가능해진다. 따라서 오버 플로우를 효과적으로 해결하는 방법이 필요하다.

• 개방 주소법 : 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장한다.
• 체이닝 : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시테이블 구조를 변경한다.

개방 주소 법에는 선형 조사법, 이차 조사법, 이중 해싱법, 임의 조사법등이 있다.

• 선형 조사법 : 만약 충돌이 ht[k]에서 발생했다면 ht[k+1]이 비어 있는지를 살펴본다. 만약 비어있지 않다면 ht[k+2]를 살펴 본다. 이런식으로 비어잇는 공간이 나올 때 까지 계속하여 조사하는 방법이다.
• 이차 조사법 : 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다.
• 이중 해싱법 : 오버플로우가 발생함에 따라 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이 방법들은 항목들을 해시 테이블에 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있다.

체이닝Permalink

선형 조사법이 탐색 시간이 많이 걸리는 이유는 충돌 때문에 해시 주소가 다른 키 하고도 비교를 해야 하는데 있다. 만약 해시 주소가 같은 키만을 하나의 리스트로 묶어둔다면 불필요한 비교는 하지 않아도 될 것이다. 리스트는 그 크기를 예측할 수 없으므로 연결 리스트로 구현하는 것이 바람직하다.

해싱의 응용 분야Permalink

해싱은 방대한 양의 데이터에 엑세스해야하는 상황에서 널리 사용된다.

해싱은 데이터베이스 인덱싱에 사용된다. 일부 데이터 베이스 관리 시스템은 별도의 인덱스 파일을 사용한다. 데이터가 파일에서 추출되어야 할 때, 탐색키는 먼저 인덱스 파일에서 검색되고, 검색 결과로부터 데이터베이스 파일에서의 정확한 위치를 알 수 있다. 인덱스 파일의 키정보는 종종 해시 테이블로 구현된다.

해싱 기술은 컴파일러에서 심볼 테이블을 구현하는데 사용된다. 컴파일러는 소스 프로그램에서 사용자가 정의한 모든 식별자의 기록을 유지하기 위하여 심볼 테이블을 사용한다. 심볼 테이블에서는 해싱을 사용하여 변수의 이름이나 함수의 이름을 빠르게 찾을 수 있다. 해싱은 인터넷 검색엔진에서 널리 사용된다.