테이블과 해쉬

박정훈·2021년 4월 22일
0

data_structure

목록 보기
1/2

테이블

아래 조건을 만족하는 표만 자료구조의 관점에서 테이블이라고 한다.

  • 표에 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다.
  • 키가 존재하지 않는 값은 저장할 수 없다.
  • 모든 키는 중복되지 않는다.

자료구조의 테이블은 사전구조라고도 불린다. 더불어 맵(map)이라 불리기도 한다.

테이블에서 의미하는 키는 데이터를 찾는 도구가 되어야 한다.

테이블의 문제

  • 테이블의 키의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다.
  • 테이블의 키의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

해쉬 함수(hash function)

넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.

서로 다른 두 개의 키가 해쉬 함수를 통과하였는데, 그 결과가 동일할 수 있다. 이러한 상황을 가리켜 충돌(collision)이라 한다. 충돌은 배열의 길이를 늘리는 등의 방법으로 피해야할 상황이 아니라 해결해야 하는 상황이다.

충돌의 해결방법에 따라서 테이블의 구조가 달라지는 경우가 있을 정도로 충돌의 해결방법은 테이블에 있어서 큰 의미를 갖는다.

좋은 해쉬 함수의 조건

  • 좋은 해쉬 함수를 사용한 결과
    데이터가 테이블의 전체 영역에 고루 분포된다. 고루 분포된다는 것은 그만큼 충돌이 발생할 확률이 낮다는 것을 의미한다. 충돌의 해결책이 마련되어 있다 하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있다.
    결국 좋은 해쉬 함수는 충돌을 덜 일으키는 해쉬 함수라고도 말할 수 있다.

  • 좋지 않은 해쉬 함수를 사용한 결과
    테이블의 특정 영역에 데이터가 몰린다. 해쉬 함수가 특정 영역에 데이터가 몰리도록 해쉬 값(해쉬 함수가 만들어 낸 값)을 생성했기 때문이다. 그만큼 충돌이 발생할 확률이 높다.

-> 좋은 해쉬 함수를 디자인 하는 방법은?
정답은 없다. 키의 특성에 따라서 달라지기 때문이다.

일반적으로 다음 사항을 고려해서 해쉬 함수를 정의하자.

좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다.

적은 수의 데이터(키의 일부분을 조합하여)를 조합하여 해쉬 값을 생성하는 것보다 많은 수의 데이터를 조합하여(키 전부를 조합하여)해쉬 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있다.

자릿수 선택(Digit Selection)과 자릿수 폴딩(Digit Folding)방법

  • 자릿수 선택
    키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 방법

  • 자릿수 폴딩
    273419라는 숫자가 있다고 하자. 이 때, 27, 34, 19로 3등분 하고 가운데로 접는다고하면 3개의 숫자가 모두 겹치게 되고 이를 모두 더하면 80이 된다. 이를 해쉬 값이라하면 이는 여섯 자리의 숫자를 모두 반영하여 얻은 결과라 할 수 있다.
    이렇듯 폴딩은 종이를 접듯이 숫자를 겹치게 하여 더한 결과를 해쉬 값으로 결정하는 방법이다.

해쉬함수를 디자인 할 때에는 다양한 방법이 있지만 키의 특성과 저장공간의 크기를 고려하는 것이 우선이다.

충돌 문제의 해결책

충돌이 발생하면 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾아야 한다.

선형 조사법과 이차 조사법

충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 선형 조사법이다.

k의 키에서 충돌 발생시 선형 조사법의 조사 순서는(빈자리를 찾는 순서는) 다음과 같이 전개된다.

f(k) + 1 -> f(k) + 2 -> f(k) + 3 -> f(k) + 4 -> ...

그런데 이러한 선형 조사법은 충돌의 횟수가 증가함에 따라서 클러스터(cluster)현상, 즉 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다는 단점이 있다. 그리고 이러한 클러스터 현상은 충돌의 확률을 높이는 직접적인 원인이 된다.

위의 단점을 극복하기 위해 나온 방법

좀 더 멀리서 빈 공간을 찾자

  • 이차 조사법
    충돌 발생시 이차 조사법의 조사 순서는 다음과 같이 전개된다.

    f(k) + 1^2 -> f(k) + 2^2 -> f(k) + 3^2 -> f(k) + 4^2 -> ...

하지만 이차 조사법 역시 해쉬 값이 같은 경우에 빈 슬롯을 찾아서 접근하는 위치가 동일하다. 그래서 선형 조사법보다는 낫지만 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생활 확률은 여전히 높다.

이러한 문제를 해결하기 위해 이중 해쉬 방법이 있다.

1차 해쉬 함수: 키를 근거로 저장위치를 결정하기 위한 것
2차 해쉬 함수: 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것

이중 해쉬 예시

1차 함수: h1(k) = k % 15
2차 함수: h2(k) = 1 + (k % c)

c는 해쉬의 크기보다는 작으면서 소수인 수로 정한다. 1차함수에서 % 15를 보고 해쉬의 크기가 15라고 예상할 수 있다. c는 15보다 작은 소수들 중에서 고르면 된다. 7로 예시를 진행해보자.

h2(k) = 1 + (k % c)
먼저 1을 더하는 이유는 2차 해쉬 값이 0이 되는 것을 막기 위해서이다. 충돌 발생 이후에 다른 자리를 살펴야 하는데 0이 되어버리면 다른 자리를 살필 수 없다.

c의 값을 해쉬의 크기보다 작은 소수로 하는 이유

  1. 가급적 2차 해쉬 값이 1차 해쉬 값을 넘어서지 않게 하기 위해서이다. 빈 자리를 찾기 위해서 해쉬의 범위를 여러 번 살펴야할 수도 있기 때문에 이것을 방지하기 위해서이다.
  2. 소수를 선택했을 때 클러스터 현상의 발생 확률이 현저히 낮다는 통계를 근거로 정한 것이다.

ex)

h1(3) = 3 % 15 = 3
h1(18) = 18 % 15 = 3
h1(33) = 33 % 15 = 3

충돌 1
h2(18) = 1 + (18 % 7) = 5 
h2(33) = 1 + (33 % 7) = 6

충돌 n
h2(18) -> h2(18) * 2  -> h2(18) * 3 -> h2(18) * 4 -> ...
h2(33) -> h2(33) * 2  -> h2(33) * 3 -> h2(33) * 4 -> ...

위에서 보듯이 1차 해쉬 값이 같아도 2차 해쉬 값이 다르다. 2차 해쉬값을 찾고도 충돌이 일어난다면 2차 해쉬 값의 크기만큼 건너 뛰면서 빈 자리를 찾는다. 키가 다르면 건너 뛰는 길이도 달라진다. 따라서 클러스터 현상의 발생 확률을 현저히 낮출 수 있다.
실제로 이중 해쉬는 이상적인 충돌 해결책으로 알려져 있다.

체이닝(Chaining)

앞서 알아본 유형의 충결 해결책들을 열린 어드레싱 방법이라고 한다. 이는 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨 있다.
체이닝 같은 유형의 방법을 가리켜 닫힌 어드레싱 방법이라고 한다. 여기에는 무슨 일이 있어도 자신의 자리에 저장을 한다는 의미가 담겨 있다. 즉, 충돌이 발생해도 자신의 자리에 들어간다는 의미이다.

체이닝을 배열로 구현한다면 2차원 배열로 구현을 하면 된다. 하지만 이는 충돌이 발생하지 않는 경우 메모리 낭비가 심하고, 충돌의 최대 횟수도 미리 결정을 해야 한다는 부담이 있기에 좋지 않은 방법이다.
따라서 체이닝은 연결 리스트를 이용해서 슬롯을 연결한다.

체이닝 방법을 적용하면 하나의 해쉬 값에 다수의 슬롯을 둘 수 있다. 따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야 한다는 불편이 따른다. 하지만 해쉬 함수를 잘 정의한다면, 그래서 충돌의 확률이 높지 않다면 연결된 슬롯의 길이는 부담스러운 정도가 아닐 것이다.

열린 어드레싱 방법을 택하는 경우에는 슬롯의 상태 정보를 표시해야 하지만, 닫힌 어드레싱 방법을 택하는 경우에는 슬롯의 상태 정보를 표시할 필요가 없다.

profile
정팔입니다.

0개의 댓글