* 해싱의 원리
해싱(Hashing)은 데이터의 규묘에 관계없이 삽입, 검색, 삭제를 일정시간 내에 할 수 있는 알고리즘 이다. 키값을 데이터가 저장된 위치(배열의 첨자)에 직접 연관 짓는 것이 해싱의 원리로 선형탐색, 이진탐색과는 근본적으로 다르다.
100개의 사이즈를 가지는 배열안에 데이터를 저장한다고 했을 때를 생각해 보자. 여기에 들어갈 수 있는 키값(배열의 첨자)은 0~99 까지의 정수이다. 그러나 이 것은 어디까지나 인위적인 설명을 하기위한 설정으로 실제로 키값을 배열의 첨자로 바로 쓰는 경우는 거의 없다. 그래서 키값 X를 배열의 첨자로 변환하는 함수 h(x)를 사용한다. 이 함수를 해시함수(hash function)라 한다. 또 해시함수가 반환하는 값을 해시 값(hash value)이라고 한다.
해시함수 h(x)가 준비되면 키값을 이용하여 배열에 데이터를 저장할 수 있다. 데이터를 저장할 배열 table이 있다고 하면 table[h(x)] 와 같은 방식으로 저장된다.
* 충돌
해싱의 원리를 설명했지만, 해싱에는 중대한 결함이 있다. 그것은 키값은 다르지만 해싱함수에 의해 같은 해시값을 생성할 가능성이 있다는 것이다.
다음은 100개의 배열에 저장하기 위해 간단 해시함수를 만들어 one ~ ten 까지의 키를 테스트 한 결과이다.
|
public class HashTest { public static void main(String[] args) { HashTest hash = new HashTest(); System.out.println("one
= " + hash.hash("one")); System.out.println("two
= " + hash.hash("two")); System.out.println("three
= " + hash.hash("three")); System.out.println("four
= " + hash.hash("four")); System.out.println("five
= " + hash.hash("five")); System.out.println("six
= " + hash.hash("six")); System.out.println("seven
= " + hash.hash("seven")); System.out.println("eight
= " + hash.hash("eight")); System.out.println("nine
= " + hash.hash("nine")); System.out.println("ten
= " + hash.hash("ten")); } int hash(String key) { int sum = 0; for (int i = 0; i < key.length(); i++) { sum += (int) key.charAt(i); } return sum % 100; } } |
위 예제에 대한 결과값은 다음과 같다.
| one = 22 two = 46 three = 36 four = 44 five = 26 six = 40 seven = 45 eight = 29 nine = 26 ten = 27 |
위 결과에서 five, nine의 값이 26이 되어버렸다. 이와 같이 다른 키에 대해 같은 해시값을 얻는 경우를 충돌 이라고 한다. 충돌이 일어났을 때 대책을 세우지 않는다면 해싱은 사용 할 수 없다.
충돌에 대한 대책은 두가지가 있다. 첫번째로 같은 해시값을 가지는 데이터를 연결리스트로 연결시켜 두는 것이다. 이를 체인화(Chaining)이라 부른다. 두번째 방법은 해시값에 대응하는 배열이 이미 차있다면 어떤 절차에 따라 다른 배열에 데이터를 저장하는 것이다. 이를 오픈어드레싱(open Addressing) 이라 부른다.
Prev
Rss Feed
