[자료구조] 실전 알고리즘 Ox15강 해시 (Java)

해시 자료구조는
16자리의 번호의 일부분을 index로 사용하는 자료구조입니다.

해시함수란

임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수

16자리 Hash값을 가진 테이블

모든 해시를 배열로 가지고 있으면 10^16의 배열이 필요합니다. 이는 40페타 바이트를 차지하게 됩니다. 그렇기에 모든 hash값을 사용하는게 아닌 일부분만의 값을 사용하여 해시테이블을 생성합니다. 이 때 해시 테이블은 배열 자료구조로 생성됩니다.

끝 4자리만 사용한 해시테이블

hash값의 일부분만을 사용하여 hash테이블이 구현됩니다.

충돌 회피 1 Chaining

Key가 중복된 노드를 LinkedList로 연결하여 관리합니다. 자바의 STL의 자료구조는 Chaining방식을 가져가고 있습니다.

주의사항

만약 충돌이 빈번할 수록 성능이 안좋아지고 해시 충돌이 한 곳으로 몰렸다면 O(N)의 시간복잡도를 가질 수 있습니다.

충돌 회피 2 Open Addressing

오픈 어드레싱 방식은 해시 충돌이 발생하게 되면 다음 배열에 비어있는 곳에 저장하는 방식입니다.

주의사항

오픈 어드레싱 방식은 값을 삭제하고 나면 더미값을 채워넣던가 혹은 제거된 상태라고 명시해 줄 필요가 있습니다. 하나의 클러스터에 있는 데이터를 조회해야 하기 때문입니다.

여기서 클러스터란 연속적으로 있는 데이터를 얘기합니다. 중간에 Dummy값이 아닌 값이 없다면 조회를 멈추는 방식을 가지기 때문입니다.

Linear Probing

충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식
장점은 Cache hit rate가 높다.
단점은 Clustering이 생겨 성능에 영향을 줄 수 있다.

Quadratic Probing

충돌 발생 시 오른쪽으로 1, 4, 9 ... 칸씩 제곱으로 이동하는 방식
장점은 Cache hit rate가 나쁘지 않지만 Clustering을 어느 정도 회피할 수 있다.
단점 - 해시 값이 같을 경우 여전히 Clustering이 발생한다.

Double Hashing

장점은 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
장점은 Clustering을 효과적으로 회피할 수 있다.
단점은 Cache hit rate가 극악으로 안좋아진다.

Cache hit rate란?

여기서 Cache hit rate란 메모리의 공간지역성과 관련이 있습니다. 공간지역성은 특정 데이터와 가까운 주소가 순서대로 접근되는 경우를 말합니다. 한 메모리의 주소뿐만 아니라 해당 블록을 전부 캐시에 가져옴으로써 Cache hit rate를 높입니다.

해시함수를 구현해야 할 때

Load Factor = 원소의 개수 / 테이블의 크기
삽입이 많아질수록 테이블이 커야한다.

Chaining

LoadFactor 1 이하로 유지되어야 성능이 나온다.

OpenAddressing

LoadFactor 0.75 이하로 유지되어야 성능이 나온다.

자바에서 해시

 

위의 결과를 보면 객체를 비교하면 false hashCode()를 비교하면 true 결과를 반환합니다.
그 이유는 == 연산은 객체의 주소를 비교하여 생성된 객체는 서로 다른 주소를 가져 false가 반환됩니다.
Integer 객체는 내부적으로 int 원시타입 value를 가지고 있고 hashCode()함수를 사용하면 원시값을 반환하기 때문입니다. 원시타입은 메소드 에리어에 저장되며 같은 값을 참조하여 true가 반환됩니다.

 

Integer만 내부에 primitive type의 값을 가지고 있는것은 아닙니다. String과 다른 기본 랩퍼타입도 마찬가지입니다. 이러한 점을 고려하여 HashMap 자료형을 사용해야 합니다.

 

해싱함수 작성

int M = 1_000_003;
int my_hash(int x) {
    return (M + x % M) % M;
}

위의 방식은 모듈러 연산을 통해 해싱을 만드는데 이 때 음수를 모듈러 연산을 하면 음수가 나올 수 있습니다. 그렇기에 테이블 사이즈를 한번 더 더해줌으로써 -, +를 호환하는 함수를 작성할 수 있습니다.

문자열의 해시함수

int M = 1_000_003;
int my_hash(String s) {
    int h = 0;
    for(int c : s.chars()){
        h += c;
    }
    return h % M;
}

이렇게 최대 100자의 문자열을 받는다고 가정한다면 12800까지 밖에 범위가 안 늘어납니다.
이렇게 되면 hash의 값이 중복될 확률이 높아져 해시충돌이 발생할 수 있습니다.

진법을 통한 해시함수

롤링 해시

int M = 1_000_003;
int a = 10;
int my_hash(String s) {
    int h = 0;
    for(int c : s.chars()){
        h  += (h * a + c);
    }
    return c % M;
}

해당 방식은 문자열의 순서를 진법으로 계산하는 방식으로 해시충돌을 피할 수 있지만 오버플로우를 조심해야 합니다.

참조

해시함수 강의