[Java] 자바의 정석 독서 #24 - 해싱과 해싱함수

https://dev-dx2d2y-log.tistory.com/143

[Java] 자바의 정석 독서 #23 - HashSet과 HashMap

저번에는 HashSet과 HashMap에 대해서 알아보았다. HashSet은 내부적으로 HashMap을 사용하고있고, HashSet에 들어오는 요소들을 HashMap의 key로 설정하여 HashMap에 저장하게 되는 것이다. 그리고 HashMap 내부에서는 key 값을 토대로 해시값을 구하여 HashMap 내부에서의 인덱스값을 설정한다.

 

이처럼 HashSet과 HashMap 모두 '해싱'을 기반으로 데이터를 저장하고, 읽어온다.

그렇다면 해싱이란 무엇일까?

---

해싱 / 해싱함수

해싱이란 해싱함수를 통하여 데이터를 해시테이블에 저장하고 검색하는 것을 의미한다.

HashMap에서 해싱을 사용하는 것과 비슷한 메커니즘으로 동작한다.

 

https://blog.naver.com/jh20s/221358860075

데이터의 키를 해싱함수에 넣어서 나온 결과를 배열로 만든 후에, 각 배열의 요소들에 링크드 리스트 형태로 값을 저장한다.

 

해싱함수를 이용한 자료구조는 다음과 같은 LinkedList 구조를 가진다.

왼쪽이 해싱함수를 이용한 해시코드들의 배열이고, 각 해시값의 배열의 요소에 해당하는 원소들이 LinkedList 형태로 저장된다.

 

예를들어, 특정한 사람들을 태여난 연도 순으로 구분하여 해싱함수를 이용한 자료구조에 저장하고 싶다면, 해싱함수를 연도의 십의 자리 수를 뽑아내도록 설계한 다음에 (60년대생이면 6, 90년대생이면 9 이런식으로..) 데이터를 해싱함수에 넣어 해시코드를 받아내도록 설계한다고치면,

 

00년대생부터 90년대생까지 0 ~ 9까지의 해시코드의 배열이 생기게되고, 새로이 2000년생의 사람이 들어오면 0이라는 해시코드가 발급되고 위의 배열에서 0에 해당하는 해시코드 배열의 요소로 들어가게 된다.

 

1996년생이 자신의 기록을 검색하러 왔을 때는 해시코드 9에 해당하는 배열에서 찾는 식으로.. 이렇게 데이터만 있다면 어느 곳에 데이터가 있는지 금방 알 수 있기 때문에 검색과 저장이 용이하다.

---

https://dev-dx2d2y-log.tistory.com/128

[CS] 자바의정석 독서 #19 - ArrayList, Vector, LinkedList

다만 LinkedList는 검색속도가 다소 느리기 때문에.. 만약 한 해시코드의 요소에 엄청나게 많은 값들이 저장되면 저장속도가 매우 느려진다.

 

그래서 가장 이상적인 해시테이블의 데이터구조는 하나의 해시코드에 하나의 데이터만 저장되는 것이다. 1996년생을 해싱하면 9가 나오도록하는 것이 아니라 그냥 주민번호 통째로 key를 만들도록 설정하는 식으로..

 

다만 하나의 데이터에 하나의 해시코드를 일대일로 매칭하는 것은 불가능하다. 해시코드가 4바이트 int형이라 가능한 해시코드의 수가 정해져있지만, 해시코드에 넣을 데이터의 수는 무궁무진하기 때문에 해시값이 아예 겹치지 않는 경우를 설계할 수는 없다. 그래서 서로 다른 데이터를 해싱함수에 넣었을 때 매번 다른 해시코드가 나올 수 없다. 이를 해시충돌이라 한다.

 

그래서 해시코드 배열의 내부값으로 LinkedList를 사용하는 이유가 해싱충돌 때문이다. 반드시 1대1로 해시코드-데이터를 매칭시키게되면 해싱충돌이 일어난 경우에는 데이터의 소실이 생길 수 있는데, LinkedList를 사용하면 해싱충돌이 일어나도 중복저장이 가능하기 때문이다.

LinkedList를 사용하는 이유는 ArrayList보다 삽입/삭제에서 기능이 더 단순하고 빠르기 때문이다.

 

이렇게되면 입력된 데이터를 받아 해시코드를 만들어내면 해시코드 배열의 몇 번째 인덱스에 데이터가 있는지 곧바로 알 수 있고, 그렇기 때문에 이상적이다. 그래서 해시테이블을 제대로 활용하려면 해시테이블의 크기를 적절하게 지정해야하고, 해시함수가 서로 다른 key에 대하여 중복된 해시코드를 반환하지 않도록 유의해야한다.

---

그래서 가장 중요한 것이 해싱함수의 알고리즘이다. 위에서는 간단한 해싱함수의 예시를 들었지만, 실제로는 훨씬 더 복잡하며, 개발자가 직접 설계하지도 않는다.

 

    public int hashCode() {
        int h = hash;
        if (h == 0 && !hashIsZero) {
            h = isLatin1() ? StringLatin1.hashCode(value)
                           : StringUTF16.hashCode(value);
            if (h == 0) {
                hashIsZero = true;
            } else {
                hash = h;
            }
        }
        return h;
    }

final class StringLatin1 {
    public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }
}

final class StringUTF16 {
    public static int hashCode(byte[] value) {
        int h = 0;
        int length = value.length >> 1;
        for (int i = 0; i < length; i++) {
            h = 31 * h + getChar(value, i);
        }
        return h;
    }
}

String 클래스의 해시함수인 hashCode() 메서드

 

https://dev-dx2d2y-log.tistory.com/124

[CS] 자바의 정석 독서 #16 - String 클래스 파헤치기

컴팩트 문자열 때문에 Latin1과 UTF16 인코딩방식에서 해시코드 알고리즘이 다른데, 대체적인 알고리즘은 String의 각 문자의 0xff (16진수 255, 이진수 11111111)와 비트연산자 &를 수행한다. C언어의 그것과 같다. 비트가 같으면 1, 다르면 0이 비트에 저장된다.

 

그래서 최종적으로 저장된 수가 해시코드가 된다.

Latin1과 UTF16으로 나뉘는 이유는, UTF16은 2개의 바이트를 하나의 문자로 삼기 때문에 UTF16의 내부 byte 배열보다 실제 문자열의 크기가 2배 작다. 그래서 2로 나누고,

 

    @IntrinsicCandidate
    // intrinsic performs no bounds checks
    static char getChar(byte[] val, int index) {
        assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";
        index <<= 1;
        return (char)(((val[index++] & 0xff) << HI_BYTE_SHIFT) |
                      ((val[index]   & 0xff) << LO_BYTE_SHIFT));
    }

getChar() 메서드에서 2배 줄여서 들어온 바이트 배열을 다시 2배로 만들어서 2개의 바이트에 대하여 동시에 비트연산을 수행해 반환한다.

 

그렇기 때문에 서로 다른 String 객체더라도 문자열만 같다면 같은 해시코드를 같는다.

---

저번에도 글을 썼지만 HashSet은 hashCode() 메서드를 사용하여 두 객체의 해시코드를 비교하고, 해시코드가 같을 경우 해시충돌을 방지하기 위해 equals() 메서드를 사용하여 최종적으로 해시코드와 저장된 값이 같아야 같은 객체로 인식한다. HashMap에서도 같은 방법으로 key를 구분한다. 그렇기 때문에 이미 존재하는 key에 대한 값을 저장하면 기존 값을 덮어쓰기한다.

 

그래서 equals() 메서드를 재정의하면 hashCode() 메서드도 재정의해야한다. 그래야만이 HashSet과 HashMap에서 같은 객체라고 인식할 것이다.

---

암튼 이렇게 해싱과 해시코드에 대해서 알아봤는데,

해시코드는 특정한 값을 해싱함수에 넣었을 때 나오는 결과값으로, 같다고 여겨지는 객체마다 같은 해시코드가 나오도록 설정할 수 있다.

 

이렇게 나온 해시코드들은 HashMap에서 배열로 저장되며, 각 배열의 요소들은 LinkedList로 구성되어있다. 가장 이상적인 HashMap의 구조는 해시코드 하나당 하나의 데이터를 매핑하는 것이지만, 현실적으로 불가능하기 때문에 해시충돌을 고려하여 LinkedList로 구성되어있는 것이다.

 

이렇게 해시코드를 사용하면 데이터와 해싱함수만 알 수 있다면 HashMap에서 어디에 데이터가 있는지 알기 쉽다는 장점이 있다.