해슁의정의

여러개의 명칭(identifier)들이 무작위로 들어있는 테이블에서 특정 명칭을 찾고자 하는 경우

원하는 키값을 가지는 테이블 항목을 검색하기 위해 특정한 변환 함수를 이용하여 키값을 항목 의 주소로 직접 바꿔서 검색하는 방법을 해슁이라 한다. 이때 변환 함수는 해쉬 함수(hash function)라 한다.

해슁의필요성

명칭 테이블에서 키 값과 일치하는 명칭을 찾는 방법으로는 테이블에 있는 각각의 명칭을 키 값과 차례로 비교하는 방법이 있다.

이 방법을 사용하면 최악의 경우 n회의 비교가 필요하다. 해슁을 이용하면 해쉬 함수가 키값을 해당 주소로 단번에 변환해 주므로 매우 빠른 검색이 가능하다.

정적 해슁

정적 해슁은 고정 크기의 테이블을 이용하여 해슁하는 방법으로서 한번 저장된 명칭의 상대적 위치가 변경되지 않는다.

정적 해슁은 다음 순서로 설명한다.

해쉬 테이블(hash 테이블)

해슁을 이용하지 않는 경우에는 명칭들의 모든 가능한 조합을 수용할 수 있도록 명칭 테이블을 만들어야 한다.

조합 가능한 명칭들 중에 실제로 존재하는 명칭들의 수는 매우 적기 때문에 대부분의 공간은 낭비된다.
명칭 테이블의 기억공간 낭비를 막기 위해 해쉬 테이블을 사용한다.
해쉬 테이블은 b개의 버켓(bucket)으로 구성되고, 하나의 버켓은 s개의 슬롯(slot)으로 구성된다. 각각의 슬롯에는 명칭 테이블 항목처럼 하나의 명칭이 저장된다.

< 해쉬 테이블의 구조 >

해쉬 테이블의 크기는 필요에 따라 달리할 수 있는데 일반적인 명칭 테이블보다는 크기가 현저히 작다. 하나의 버켓에 여러개의 슬롯을 두는 이유는 서로 다른 두개의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우 두 명칭을 같은 버켓에 저장하기 위해서이다.

해슁의 문제점

해슁을 하는 경우 서로 다른 두개 이상의 명칭이 해쉬 함수에 의해 동일한 주소로 변환되는 경우가 있다. 이 현상을 "충돌(collision)"이라 한다. 충돌이 자주 발생하면 탐색 시간이 길어지는 등 성능이 저하되므로 해쉬 함수를 수정하거나 해쉬 테이블의 크기를 적절히 조절해 주어야 한다.

충돌이 발생한 경우 같은 버켓에 있는 다른 슬롯에 명칭을 저장하면 된다. 그러나 슬롯의 갯수만큼 충돌이 생기면 빈 슬롯이 소진되어 오버플로우(overflow)가 생길 수 있다. 오버 플로우가 발생하면 해슁에 의해 원하는 명칭을 찾을 수 없게 되므로, 오버 플로우를 해결하기 위한 방법이 고안되어야 한다.

해쉬 함수

해쉬 함수는 입력된 키값을 해쉬 테이블의 주소로 변환시켜주는 함수이다. 해쉬 함수는 가능한 충돌이 적게 발생해야 하므로, 함수의 출력값이 해쉬 테이블의 주소 영역 내에서 고르게 분포되어야 한다.

주로 사용되는 해쉬 함수는 다음과 같다.

mid-square 함수
키 값을 제곱한 후에 중간에 몇 비트를 취해서 해쉬 테이블의 버켓 주소로 만들어 준다. 키 값을 제곱하면 결과값의 중간 비트들은 키 값의 모든 비트들로부터 영향을 받으므로 버켓 주소가 고르게 분산될 가능성이 높다.
다음은 검색 키가 5비트로 구성되어 있고, 버켓 주소도 5비트로 구성된 해쉬 테이블에서 mid-square 함수 해슁을 하는 예를 보여준다.

division 함수
키 값을 해쉬 테이블의 크기로 나누어서 그 나머지를 버켓 주소로 만들어준다.
버켓 주소 = 키 값 % 해쉬 테이블 크기
folding 함수
키 값을 버켓 주소 크기만큼의 비트수를 가지는 부분으로 분할한 후, 분할된 것을 합산하여 버켓 주소를 만들어준다.
다음 그림은 키 값이 "12321631067"이고 버켓 주소가 10진수 3자리로 구성되어 있는 경우의 예를 보여준다.

오버플로우의 해결방법

선형 개방 주소지정법

선형 개방 주소지정법은 충돌이 발생한 경우에 그 위치로부터 비어있는 다른 버켓을 찾아 그곳에 명칭을 저장하는 방법으로서 선형 탐색법(linear probing)이라고도 불린다.
선형 개방 주소지정법을 이용할 때 해쉬 테이블은 1차원 배열 형태를 가진다.

명칭을 삽입하는 경우

  1. 해당 키 값을 가지는 명칭을 해쉬 함수로 변환하였을 때 그 위치의 버켓이 비어있으면 삽입한다.
  2. 버켓이 비어있지 않으면 그 위치부터 해쉬테이블을 차례로 조사하여 빈 버켓을 찾은 후 그 위치에 명칭을 삽입한다.
  3. 해쉬 테이블의 끝까지 빈 버켓이 없으면 테이블의 처음부터 원래 삽입한 위치까지 빈 버켓을 찾는다.
  4. 빈 버켓이 전혀 없는 경우는 명칭을 삽입할 수 없으므로 오류 발생을 고지한다.

명칭을 검색하는 경우

  1. 해당 키 값을 가지는 명칭을 해쉬 함수로 변환하여 얻어진 위치에 원하는 명칭이 들어있는지 조사한다.
  2. 원하는 명칭이 없다면 삽입시에 충돌이 발생한 것이므로, 그 위치부터 차례로 해당 명칭을 검색한다.

선형 개방 주소 지정법의 장단점

장점

단점

체인 이용법

충돌이 발생한 경우에 동일 버켓에 들어가야할 명칭들을 연결 리스트로 저장해 두는 방법이다.

체인 이용법을 이용할 때는 해쉬 테이블의 각 버켓이 하나의 연결 리스트가 된다.

명칭을 삽입하는 경우

  1. 해당 키 값을 가지는 명칭을 해쉬 함수로 변환하여 주소를 얻어낸 후 그 위치에 있는 연결 리스트에 삽입한다.

명칭을 검색하는 경우

  1. 해당 키 값을 가지는 명칭을 해쉬 함수로 변환하여 주소를 얻어낸다.
  2. 얻어진 위치의 연결 리스트에 노드가 한개 뿐이면 충돌이 발생하지 않은 것이므로 그 값을 읽어온다.
  3. 얻어진 위치의 연길 리스트에 노드가 두개 이상이면, 그 연결 리스트의 노드들을 차례로 검색하여 그 값을 읽어온다.

체인 이용법의 장단점

장점

단점

동적 해슁

동적 해슁의 필요성

항목과 삽입과 삭제가 빈번히 발생하는 응용에는 정적 해슁이 적합치 적합치 못하다. 고정된 크기의 해쉬 테이블을 사용하는 정적 해슁의 경우, 삽입이 많아지면 테이블이 가득차서 사용이 불가능하고 삭제가 많아지면 많은 공간이 사용되지 않으므로 낭비가 발생한다. 이러한 응용에 적합하도록 고안된 것이 동적 해슁(dynamic hashing) 또는 확장성 해슁(extendible hashing)이다.

동적 해슁의 구성

동적 해슁을 위해서 해쉬테이블 대신에 트라이(trie)라는 자료구조를 이용한다.

트라이는 입력키의 각 비트값에 따라 2개의 가지로 분기되도록 만들어진 것이다. 위의 그림은 두 비트의 키를 가지는 트라이다. 키 값의 우단 비트(LSB)부터 검사하여 그 값이 0이면 첫번째 레벨에서 위쪽으로 분기하고 , 1이면 아래쪽으로 분기한다. 그 다음에는 오른쪽 끝에서 두번째 비트를 검사하여 그 값이 0이면 두번째 레벨에서 윗쪽으로 1이면 아래쪽으로 분기한다. 실제 항목들이 저장되는 부분은 해쉬 테이블의 버켓처럼 여러개의 슬롯이 존재한다. 동적 해슁에서는 버켓을 페이지라 부른다.

동적 해슁에서의 검색

위에 나열된 것처럼 6비트로 이루어진 6개의 명칭이 트라이에 저장되어 있다고 하자. 트라이의 말단에 있는 페이지에는 두개의 슬롯이 있다. 이러한 경우 4개의 페이지에 명칭들을 저장할 수 있으므로 두비트의 키가 필요하다.

검색을 위해서 우단의 두 비트를 검사하여 비트값에 따라 위, 아래로 분기한다. 해당 페이지를 찾은 후 페이지내의 스롯에 저장된 명칭들을 차례로 비교하여 원하는 명칭을 검색해낸다.

동적 해슁에서의 삽입

<삽입전>

위의 그림에 나온 트라이에 "110101"이라는 명칭을 삽입해 본다. 먼저 명칭이 삽입될 페이지를 찾는다. 우단의 두 비트를 이용하여 검색하면 3번 페이지가 해당되는데 이 페이지에는 더이상 명칭을 저장할 슬롯이 없기 때문에 둘로 분할해야 한다. 페이지가 분할되어 레벨이 한 단계 깊어지면 검색에 필요한 비트 수가 한개 늘어난다.

<삽입후>