sun cloud

Hash

앞서 연결리스트에 알아봤습니다. 연결 리스트는 포인터를 사용하여 여러 개의 노드를 연결하는 자료 구조로써 크기가 정해져있지 않고, 데이터의 추가와 삭제 또한 상수 시간으로 가능하며 스택과 큐를 만들 수 있었습니다.

하지만 리스트 내의 특정 데이터를 찾을 때에는 첫 번째 노드부터 하나씩 확인을 해야하기 때문에 O(n)의 시간복잡도를 가지게 되고, 이를 통해 특정 요소를 검색할 경우 연결 리스트가 비효율적이라는 것을 알 수 있었습니다.

해시는 이와 대비됩니다. 해시는 `key`와 `value`를 가지며, 특정 `value`는 그와 연관된 `key`를 통해 검색이 가능하므로 `O(n)`의 시간복잡도를 가지며, 데이터를 빠르게 추가하거나 제거하는 것 또한 가능합니다.



Hash Functions

1
2
3
4
5
6

# 예시용 해시함수 수도 코드
hashCode (String id)
    remove cscc
    convert to int
    cnt - 10
    return int

해시 함수를 작성할 때에는 아래의 사항들을 고려해야 합니다.

  1. 데이터의 속성 (자료구조 해시는 해시 함수에 대한 정보가 없습니다. 예를 들어, CSSC 아이디를 통해 CSSC를 제거하는 해시 함수가 있다면 CSSC 아이디라는 데이터가 있어야만 함수가 작동합니다.)

  2. 연산이 빨라야 합니다.

  3. 두 요소가 “같다면” 같은 값을 반환해야 합니다

  4. 동일한 실행 환경에서 같은 객체라면 같은 값을 반환해야 합니다.

  5. 코드를 새로 실행하면 객체가 같더라도 다른 값이 나올 수 있습니다. (hashCode 메소드를 오버라이드하지 않으면, 새롭게 실행할 때마다 객체는 다른 위치에 저장됩니다.)

  6. 코드에서 최대한 충돌이 일어나지 않도록 해야 합니다.

강의 내용만으로 온전한 이해가 어려워 추가적으로 찾아본 결과, 해시함수는 다음의 특징을 갖습니다.(해시함수 - 해시넷)

  • 일방향 함수(one-way function)로 다양한 길이의 입력을 고정된 짧은 길이의 출력으로 변환하는 함 수로 데이타의 무결성 검증, 메세지 인증에 사용한다
  • 다양한 가변 길이의 입력에 적용될 수 있어야 한다.
  • 고정된 길이의 출력을 만든다.
  • 주어진 입력값을 해시하는 것은 쉽다.
  • 해시 결과값으로 입력값을 계산하는 것은 불가능 하다.
  • 동일한 해시값을 가지는 서로 다른 메시지 쌍이 없다.

당장은 위의 내용들을 완벽히 이해하기 어렵지만, 남은 강의들을 통해 차차 이해해보도록 하겠습니다.



Collision

image

 

서로 다른 값을 가진 키가 일치하는 경우를 해시 충돌이라고 합니다. 예를 들어, 위 사진에서는 전화번호를 3분할한 것의 합을 키로 지정하였습니다. 그런데 키가 2386으로 같아 해시 충돌이 발생합니다.

  • 추가적으로 찾아본 결과, 해시 충돌 이란 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다고 합니다. 입력값은 다른데 출력값이 같다는 것은 데이터가 집중된다는 것이고, 해시테이블의 성능을 저하시킵니다. 그리고 이를 예방하기 위해 체이닝, Open Addressing 등의 방식이 사용된다고 합니다.(해시 충돌 - 해시넷) 남은 수업을 통해, 해시 충돌에 대한 자세한 이해와 해결 방법에 대해서도 살펴보겠습니다.


위에서는 숫자를 예시로 들었는데, 이번에는 문자열을 해시로 나타내는 연습을 해보겠습니다.

문자는 ASCII코드로 변환하여 숫자 형태로 나타낼 수 있습니다. 그래서 위와 같은 방식으로 문자를 숫자 형태로 반환한 뒤 숫자의 합을 저장하는 방식으로 나타낼 수 있는데, 이렇게되면 앞에서와 비슷하게 해시 충돌이 발생합니다.

“this”라는 문자열을 각각 116, 104, 105, 115의 ASCII코드로 나타내면 합이 440이 나오는데, “hits”, “shit” 역시 마찬가지의 값을 나타내 충돌이 나타나는 것이죠.

이 상황을 해결하기 위해 상수의 제곱을 이용해서 각 문자의 위치를 구분할 수 있습니다.

image

이를 식으로 나타내면, 116 + g(104 + g(105 + g(115)))로 표현할 수 있습니다.

해시 함수로 나타내면 아래와 같습니다.

1
2
3
4
5
6
7
8
9

// 문자열을 정수로 계산해주는 함수(문자의 위치를 구분)
public int hashCode(String s) {
    int g = 31;
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
        hash = g * hash + s.charAt(i);
    }
    return hash;
}

문자열을 정수로 반환받는 해시 함수 예제를 살펴봤습니다. 반환받은 정수는 배열의 인덱스로 사용하게 되는데, 여기서 최적화가 필요합니다. 왜냐하면, 테이블에 이미 요소가 들어있는데 같은 위치에 다른 요소를 추가하려고 하는 해시 충돌 상황이 발생할 수 있기 때문입니다.

이러한 충돌을 피하기 위한 방법으로 테이블 크기를 최적화하는 방법이 있습니다.

그리고 테이블 크기는 1) 홀수로 설정하거나, 2) 소수로 설정하여 나머지(% 연산자 사용)가 다양한 값이 나오도록 해 최적화를 할 수 있습니다.


해시 함수의 반환값은 정수이기 때문에 0을 포함한 양수 또는 음수를 반환할 수 있습니다. 그리고 음수에 대한 나머지 연산은 사용하는 프로그래밍 언어에 따라 바뀌지만, 자바에서는 음수가 반환될 수 있습니다.(-10 % 3의 결과값은 -1입니다)

배열의 인덱스로 사용하기 위해서는 양수이어야 하기 때문에 해시 함수에서 나온 결과값을 양수로 바꾸는 방법을 알아보겠습니다.

자바에서는 음수를 표현할 때 2의 보수를 활용합니다. 첫 번째 비트가 0이면 양수, 1이면 음수입니다. 그래서 첫 번째 비트가 1인 경우 0으로 바꾸기 위해 & 연산을 활용해보겠습니다.(-1 & 0x7FFFFFFF 의 결과값은 2147483647입니다. 결과값의 크기는 중요하지 않습니다.)

1
2
3
4
5

public int hashCode(String s) {}

int hashval = data.hashCode(s)
hashval = hashval & 0x7FFFFFFF
hashval = hashval % tableSize


λ(적재율)

테이블에 데이터가 얼만큼 있는지 알 수 있는 LoadFactor(= 적재율)에 대해 알아보겠습니다.

적재율은 λ(람다 )로 표기하고 항목 수를 자료 구조의 크기만큼 나눈 값입니다.

  • λ = 0인 경우, 데이터가 없다는 뜻이고, λ = 0.5라면 반이 차 있다는 뜻입니다.

그리고 자료구조가 해시 충돌을 해결하는 방법에 따라 적재율은 달라집니다. 적재율이 0.6이나 0.7을 넘으면 테이블의 크기를 조절할 필요가 있다고 볼 수 있습니다.


해시 충돌 해결

해시 함수는 문자열을 정수형으로 반환합니다. 문자열로 나타낼 수 있는 정수에는 한계가 있기 때문에 충돌은 발생할 수 밖에 없고, 이를 해결하기 위한 방법으로 linear probing(선형 조사법), quadratic probing(2차식 조사법), double hashing(이중 해싱) 등이 있습니다.


  1. 선형 조사법(linear probing)

우선 하나의 배열에 해시 함수의 결과값을 저장하는 상황을 가정해보겠습니다.

1
2
3
4
5
6
7

int h = x.hashCode();
h = h & 0x7FFFFFFF;
h = h % tableSize;

int h = y.hashCode();
h = h & 0x7FFFFFFF;
h = h % tableSize;

여기서 결과값이 동일하다면 먼저 위치한 요소의 다음 칸을 확인해서 빈 칸에 값을 저장할 수 있습니다. 빈 칸에 위치시킨 다음에는 위치가 바뀌었다는 사실을 알려야 하겠죠.

image

이 상황에서 데이터를 찾게 된다면, 찾는 값이 맞는지 뒤로 한 칸씩 확인해야 하고, 이를 선형 조사법이라고 합니다.

이 방식은 제거할 때에도 주의해야 하는데, 단순히 삭제에서 그치면 다른 값의 확인이 어려워지므로 무언가가 있었지만 이제는 비었다는 표시를 해야 합니다.


  1. 2차식 조사법(quadratic probing)

선형 조사법은 단순하지만 데이터가 집약되기 때문에 비효율적인 방법이 될 수 있습니다.

이러한 문제를 해결하기 위해 2차식 조사법을 사용할 수 있습니다.

다른 요소를 넣으려하는데 이미 차 있다면, 다음 칸에 저장하는 것이 아니라 그 값의 제곱만큼 더하는 방식입니다.

다음 칸 대신 1부터 순서대로 제곱하여 더한 칸을 확인하며, 테이블의 끝을 넘어가면 % 연산을 이용해 다시 테이블의 범위 안으로 들어오게 합니다.


  1. 이중 해싱(double hashing)

이중 해싱은 2개의 hashCode 함수가 필요합니다. 그리고 두 함수는 서로 달라야하고, 두 번째 함수는 0을 반환해선 안 됩니다.

그래서 첫 번째 hashCode의 결과로 채우려는 공간이 이미 차 있다면, 두 번째 hashCode를 호출해서 두 개의 hashCode 결과값을 더해서 위치시키게 합니다.

image

이중 해싱은 아예 다른 해시 함수를 사용할 수 있기 때문에 데이터를 더 골고루 넣을 수 있습니다. 그래서 이중 해싱은 테이블이 더 빠르게 차지만 해시 함수가 2개가 필요하다는 단점이 있고, 선형&2차식 조사법은 적재율이 증가하기에 테이블 크기를 바꿔줘야 합니다.



체이닝

해시는 사실상 하나의 배열로 구성되어 있고, 그 배열에 요소를 추가하는 방식입니다. 문제는 특정 위치에 요소를 추가함에 따라 배열이 점점 채워지는 것 입니다.

그렇다면 배열의 위치마다 새로운 자료 구조를 만들어서 많은 데이터를 수용하게 할 수 있지 않을까요?

연결 리스트를 사용하면 됩니다. 연결 리스트를 사용한다면 hashCode의 반환값이 다양할 때 요소의 추가, 제거, 검색에 상수 시간이 소요됩니다.

image

체이닝(Chaining)은 요소마다 연결 리스트를 만들어 수많은 데이터를 수용할 수 있게 하는 방법으로, 체인 해시는 가장 안정적이고 보편적으로 사용되는 자료 구조 중 하나입니다. (강의를 맡으신 교수님께서는 이를 최고의 자료 구조라고 평하셨습니다. 참고로, 파이썬의 딕셔너리도 체인 해시를 기반으로 만들어졌다고 하며 자바에서도 API를 활용해 쉽게 해시를 만들 수 있습니다)

체이닝을 하면 수용 가능한 요소 개수에 제한이 없어지고 크기 조정도 자주 할 필요가 없어집니다.

적재율 λ는 항목의 개수를 가능한 체인 개수로 나눈 값입니다. 체인 1개에 여러 항목을 넣을 수 있어 λ는 1보다 큰 수가 될 수 있습니다.

하지만 hashCode가 같은 숫자만 반환하여 하나의 체인이 너무 길어지면 결국 연결 리스트와 시간 복잡도가 같아지는 문제가 발생합니다.

image

위의 그림과 같이 hashCode가 같은 숫자만 반환한다면 시간 복잡도가 상수 시간이 아닌 O(n)이 되는 것이지요.

그래서 hashCode가 매번 다른 값을 반환한다면 가장 좋은 상황이 될 것 입니다.



참고

자바로 구현하고 배우는 자료구조 > 3.해시(Hash) : 부스트코스

해시 함수 - 해시넷

해시 충돌 - 해시넷

맨 위로 이동하기

DataStructure 카테고리 내 다른 글 보러가기

댓글남기기

참고