해쉬(Hash)

Java 해쉬(Hash) 기본 개념과 구조

1. 해쉬(Hash)의 개요

앞에서 데이터를 삽입, 검색, 삭제하는데 사용되는 몇가지 자료구조를 살펴보았다.

리스트, 스택, 큐 등의 자료구조를 배열로 구현하거나 연결 리스트로 구현하는 방법을 보면 삽입과 삭제는 연결 리스트가 효율적으로 동작하고 검색은 배열이 더 효율적으로 동작하는걸 확인할 수 있다.

[자료구조] Java 배열(array)과 리스트(list) 비교

배열은 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다.

반면에 연결 리스트는 삽입, 삭제시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능했었다. 단 처음노드 마지막노드 이외의 위치에서 데이터를 삽입, 삭제할 경우나 데이터를 검색할 경우에는 해당 노드를 찾기 위하여 처음부터 순회검색을 해야하기 때문에 데이터의 수가 많아질수록 효율이 떨어질 수 밖에 없는 구조였다.

이러한 한계를 극복하기 위하여 제시된 방법이 바로 해쉬(Hash)이다.

2. 해쉬(Hash)의 기본 개념

해쉬(Hash)는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.

그리고 데이터의 삽입과 삭제시 기존 데이터를 밀어내거나 채우는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸뒤 이를 인덱스로 사용한다.

특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치이기 때문에 삽입시 다른 데이터의 사이에 끼어들거나 삭제시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제시 데이터의 이동이 없도록 만들어진 구조이다.

해쉬(Hash)가 내부적으로 사용하는 배열을 Hash Table 이라고 하며 그 크기에 따라서 성능 차이가 많이 날 수 있다.

3. 해쉬(Hash) 메소드

해쉬(Hash)는 Hash Table을 이용하여 데이터를 저장한다. 이때 특별한 알고리즘을 이용하여 데이터의 고유한 숫자값을 만들어 인덱스로 사용하는데 이 알고리즘을 구현한 메소드를 Hash Method라고 하며 Hash Method에 의해 반환된 데이터 고유의 숫자 값을 Hash Code 라고 한다.

Java 에서는 Object 클래스의 hashCode() 라는 메소드를 이용하여 모든 객체의 Hash Code를 쉽게 구할 수 있다.

[JAVA] Object 클래스 정리

Hash Method를 구현하는 방법은 여러가지가 있지만 가장 간단한 방법으로는 나머지 연산자를 이용하는 것이다.

데이터의 고유한 hashCode 를 구한 뒤 hashCode를 테이블의 크기로 나머지 연산을 한 결과를 해당 데이터의 인덱스로 사용하는 것이다.

예를들어 "a", "b", "c"의 hashCode가 각각 97, 98 ,99 라고 하고 Hash Table의 크기가 10이라고 했을 때 테이블에 저장될 인덱스는 다음과 같다.

97 % 10 = 7

98 % 10 = 8

99 % 10 = 9

즉, Hash Table의 인덱스 7에는 "a"를 저장하고 8에는 "b", 9에는 "c"를 저장하는 방식이다.

이후에 "a"를 검색할 때에는 "a"의 hashCode를 가지고 나머지 연산을 한 결과인 7번 인덱스를 바로 참조하여 데이터를 꺼낼 수 있다.

또다른 예를 들어 보자

4, 8, 12, 16, 20, 24, 28, 32 라는 hashCode를 가진 데이터가 있다고 했을 때 데이터를 저장하기 위해 Hash Table의 크기를 8로 지정했다면 테이블에 저장될 인덱스는 다음과 같다.

4 % 8 = 4

8 % 8 = 0

12 % 8 = 4

16 % 8 = 0

20 % 8 = 4

24 % 8 = 0

28 % 8 = 4

32 % 8 = 0

데이터를 저장하기 위한 인덱스가 0번과 4번에 집중되는 것을 볼 수 있다.

이처럼 hashCode가 다르더라도 나머지 연산을 한 결과는 같을 수 있으므로 Hash Table의 동일한 인덱스에 저장을 시도하려 할 경우 문제가 발생한다.

이렇게 저장하려는 위치에 이미 다른 데이터가 있어서 저장을 할 수 없는 현상을 충돌(collision)이라고 하며 이런 충돌을 최소화 하기 위한 방법으로는 나머지 연산의 값이 최대한 중복되지 않도록 테이블의 크기를 소수(prime number)로 만드는 것이다.

다음은 8보다 큰 소수인 11을 테이블의 크기로 지정했을 때 각 데이터들이 테이블에 저장될 인덱스 값이다.

4 % 11 = 4

8 % 11 = 8

12 % 11 = 1

16 % 11 = 5

20 % 11 = 9

24 % 11 = 2

28 % 11 = 6

32 % 11 = 10

이제는 충돌이 발생하지 않는다. 하지만 Hash Table의 크기를 소수로 만드는 것은 충돌을 줄이는 방법이지 해결하기 위한 방법은 아니다. 추가적으로 10을 저장하려고 한다면 10 % 11 = 10 로 되므로 이미 10번의 인덱스에는 32가 들어있기 때문에 충돌이 발생한다.

이처럼 충돌이 발생할 경우 이를 해결하기 위한 방법이 필요하며 충돌 해결 방법으로 개방주소법과 분리연결법 두가지가 있다.

4. 충돌 해결 방법

Hash Table에 이미 다른 데이터가 저장되어 있을 경우 데이터를 저장하지 못하는 충돌이 발생한다고 했다.

이를 해결하기 위한 방법으로는 개방주소법과 분리연결법이 있지만 개방주소법은 충돌이 많이 일어날 경우 심각한 성능저하가 발생할 수 있기 때문에 분리연결법에 대해서만 확인해 보도록 하겠다.

분리연결법은 Hash Table에 연결 리스트에서 사용하는 Node 객체를 저장하는 것이다. 즉, Hash Table의 셀마다 연결 리스트를 하나씩 저장하도록 하고 충돌이 발새하는 데이터는 연결 리스트의 다음 노드로 계속 추가해 가는 것이다.

이후에 데이터를 검색할 때에는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 hashCode와 저장된 노드의 hashCode를 비교하는 것이다.

5. 분리연결법을 이용한 Hash 구현

public class Hash {          // 데이터를 저장할 Entry는 값과 다음 Entry를 가진다.     private class Entry{         private int value;         public Entry next;     }          private int size;     private Entry[] hTable;          // Hash Table은 size와 배열 테이블을 생성한다.     public Hash(int size){                  this.size = size;         this.hTable = new Entry[size];     }          // key 값으로 HashTable에 저장될 index를 반환한다.     public int hashMethod(int key){         return key % size;     }          // 저장할 데이터로 key를 추출한다.     // 실제 Hash 에는 특별한 알고리즘이 적용되 hashCode를 얻는다.     public int getKey(int data){         return data;     }          // data를 HashTable에 저장한다.     public int add(int data){                  // data의 hashCode를 key와 저장할 index를 얻는다.         int key = getKey(data);         int hashValue = hashMethod(key);                  // 저장할 Entry 생성         Entry entry = new Entry();         entry.value = data;                           // HashTable의 저장할 index가 비어있다면,  저장하고 끝낸다.         if(hTable[hashValue] == null){                          hTable[hashValue] = entry;             return 0;         }                           Entry pre = null;         Entry cur = hTable[hashValue];                  // 해당 index의 연결리스트는 값의 크기가 작은 값부터 큰 순서로 정렬되어있다.         while(true){                          if(cur == null){     // Hash Table에 저장할 index가 비어있으면                                   hTable[hashValue] =entry;  // 해당 index에 저장                 return 0;                          }else if(cur.value < key){    // 해당 index의 커서 노드의 값이 key보다 작으면                                  // 커서를 하나 뒤로 옮긴다.                 pre = cur;                             cur = cur.next;                          }else{     // 해당 index의 커서 노드의 값이 key 보다 크다.(여기에 저장)                                  // 커서 노드가 HashTable의 첫번째 노드이면                 if(cur == hTable[hashValue]){                                          // 삽입 노드를 첫번째 노드로 삽입하고 다음 노드를 커서노드로 지정한다.                     entry.next = cur;                     hTable[hashValue]= entry;                     return 0;                                      }else{    // 첫번째 노드가 아니면                              // 삽입 노드의 다음 노드로 커서노드를 지정하고                     // 전 노드의 다음 노드를 삽입노드로 지정한다.                     entry.next = cur;                     pre.next = entry;                     return 0;                 }             }         }     }               // data가 있는 위치를 얻는다.     public int get(int data){                  int key = getKey(data);         int hashValue = hashMethod(key);                  // data가 있는 index의 첫번째 노드를 얻는다.         Entry cur = hTable[hashValue];                  while(true){                          if(cur == null){    // index 가 비어있다면 -1 반환                              return -1;                          }else if(cur.value == key){    // 커서의 값과 키가 같으면 0 반환                                  return hashValue;                          }else if(cur.value > key){    // 커서의 값이 키보다 크면 -1 반환                                                     // 리스트는 작은 값에서 큰 값으로 정렬되어있다.                 return -1;                          }else{        // 커서의 값이 키보다 작으면 다음 노드로 커서 이동                                  cur = cur.next;             }                  }     }          // data가 있는 노드를 반환한다.     private Entry getEntry(int data){                  int key = getKey(data);         int hashValue = hashMethod(key);                  // HashTable의 index의  첫번째 노드와 두번째 노드         Entry pre = hTable[hashValue];         Entry cur = pre.next;                  while(true){                          if(cur == null){    // 커서 노드가 null 이면 null 반환                                  return null;                          }else if(cur.value == key){    // 커서 노드의 값이 키와 같으면 전 노드를 반환                                  return pre;                              }else if(cur.value > key){    // 커서의 값이 키보다 크면 null 반환                                  return null;                          }else{            // 커서의 값이 키보다 작으면 커서를 다음으로 이동                                  pre = cur;                 cur = cur.next;             }         }     }          // data 를 제거     public int remove(int data){                  Entry pre = null;                  // data가 있는 노드의 전노드를 가져오고 null이면 -1 반환         if((pre=getEntry(data))== null){             return -1;         }                  // 전 노드가 data의 다음노드를 가리키게 한다.         // data 노드를 건너뛰게 연결한다 (제거)         Entry cur = pre.next;         pre.next = cur.next;         return 0;     }          public String toString(){                  StringBuffer result = new StringBuffer();         Entry cur = null;                  for(int i=0; i<size; i++){                          result.append("[" + i + "]\t");             cur = hTable[i];                          if(cur == null){                 result.append("n ");                              }else{                                  while(cur!=null){                     result.append(cur.value + "");                     cur = cur.next;                 }             }             result.append("\n");         }                  return result.toString();     } }

배열로 되어있는 Hash Table안에 리스트가 있어서 조금 복잡해 보일 수 있다.

Hash Table에 저장할 Entry 는 값과 다음 Entry를 가리킬 변수를 가지고 생성한다.

getKey() 함수는 data 를 가지고 hashCode 를 생성하여 반환한다. 실제 Hash 에서는 특별한 알고리즘으로 hashCode를 생성하지만, 여기서는 data 값을 key로 하겠다.

hashMethod() 는 key를 가지고 Hash Table에 저장할 index를 결정하여 반환한다

Hash에 데이터의 삽입은 키와 인덱스를 가지고 Hash Table에서 해당 인덱스를 확인한다.

해당 인덱스가 비어있으면 Entry를 저장하면 되고, 값이 있다면 첫번째 Entry 부터 순차적으로 탐색하여 key가 삽입될 위치를 찾아 삽입한다. (Entry 리스트는 단순연결리스트이며, 작은값부터 큰 값 순서로 정렬되어 있다.)

해당 데이터의 위치 탐색은 hashMethod()로 index를 얻은 후, 해당 index에 데이터가 있는지 탐색한다.

있으면 index를 반환하면 되고 없으면 -1 을 반환한다.

데이터의 제거를 위해서는 data에 해당하는 index의 Entry 리스트 에서 data의 앞 노드가 다음 노드를 data의 뒷 노드를 가리키게 하면 된다.

 Hash.zip

Hash는 탐색이 빠른 배열의 장점과 삽입/삭제시 데이터의 밀어내기 이동이 필요없는 장점을 이용해 성능을 향상시킨 데이터 저장 방법이다.

위에서 소개한 분리연결법은 배열과 단순연결리스트를 혼합하여 데이터의 삽입/삭제/탐색의 성능을 높인다.

개방주소법은 배열만을 사용하며, 저장 인덱스가 겹칠경우 해당 인덱스의 옆 인덱스에 저장하는 방식이다. 이때 옆 인덱스와의 데이터 충돌이 또다시 일어나면 다시 옆 인덱스로 저장한다. 따라서 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생하는 단점이 있다.

출처 : http://hyeonstorage.tistory.com/265