해시충돌이란 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다.

해시함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨리고, 암호학적 해시함수의 경우 해시함수의 안정성을 깨뜨리는 충돌공격이 가능할 수 있기 때문에 의도적인 해시충돌을 만드는 것이 어렵도록 설계되어야 한다.

비둘기집 원리에 의해 해쉬맵은 항상 충돌이 예견되어 있다.

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리

해시맵에서 키값은 n자리수인데, 입력할 수 있는 키의 갯수는 무한하니, 비둘기집 원리를 충족한다고 말할 수 있다.

해시 충돌 해결법은 크게 두 가지로 나뉜다.

충돌이 일어나면 다른 인덱스에 저장하도록 조정한다. 해시 값과 실제 저장된 위치가 다를 수 있다.

이미 차지하고 있는 칸의 다음 칸에 값을 저장한다.(+1, +2, ...)

데이터들이 특정 위치에만 밀집하는 현상(primary clustering)이 발생할 수 있고 그렇게 되면 탐색하는데 걸리는 시간이 엄청나게 많이 소요된다.

이미 차지하고 있는 칸에 n^2(n은 충돌횟수)을 더한 칸에 저장한다(+1^2, +2^2, +3^2, ...).

하지만 처음 시작 해시값이 같을 경우, 그 이후의 해시값들도 모두 동일한 값으로 계산되어 충돌이 반복적으로 일어나는 단점(secondary clustering)이 있다.

해쉬 함수를 두 가지를 두고 평소에는 해쉬함수1만 쓰다가 충돌시 해쉬함수2를 써서 새로운 인덱스로 조정한다.

충돌이 일어나도 해당 위치에 저장한다. 다만 다른 방법을 써서 기존 값을 버리거나 덮어씌우지 않게 저장한다. 해시 값과 실제 저장된 위치는 다를 수 없다.

배열의 요소 안에 다시 배열을 만들어 저장한다.

충돌된 값들을 LinkedList로 연결한다.

Open Addressing은 데이터를 삭제할 때 처리가 효율적이기 어려운데, HashMap에서 remove() 메서드는 빈번하게 호출될 수 있기 때문에 Seperate Chaining을 활용한다. 또한 HashMap에 저장된 key-value 개수가 일정 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아진다.

해시 충돌이 일어날 때 LinkedList만 사용한다.

한 버킷(, 즉 같은 해시값)에 key-value쌍이 8개 이상이면 Tree로 변경되고, 6이하면 LinkedList로 변경된다.

8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 key-value 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

그 결과 get()메서드 호출에 대한 기댓값이 Java 7 에서는 E(N/M) 이었다면, Java 8에서는 E(log(N/M))이 되었다.

이 때문에 Java 7의 Entry 클래스 대신 Java 8에서는 TreeNode를 사용할 수 있는 Node 클래스를 사용한다.

해시 버킷(데이터가 저장되는 공간)의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. key-value 쌍 개수가 일정 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다. 기본값은 16이고, 최대 개수는 2^30 이다.

임계점 = load factor * 현재 해시 버킷 개수

load factor의 기본값은 0.75이다. 예를 들면 버킷의 개수가 16개일 때에는 임계점이 12개가 된다.

다만, 버킷 개수가 증가할 때마다 모든 key-value 데이터를 읽어 새로운 Separate Chaining을 구성하는 문제가 있다. 데이터의 개수를 예측 가능하다면, HashMap 생성자의 인자로 초기 해시 버킷 개수를 지정할 수 있다.

// 인자로 사용하는 newCapacity는 언제나 2a이다.
void resize(int newCapacity) {  
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;

        // MAXIMIM_CAPACITY는 230이다.
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];

        // 새 해시 버킷을 생성한 다음 기존의 모든 키-값 데이터들을
        // 새 해시 버킷에 저장한다.
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        // 모든 해시 버킷을 순회하면서
        for (Entry<K,V> e : table) {
            // 각 해시 버킷에 있는 링크드 리스트를 순회하면서
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 해시 버킷 개수가 변경되었기 때문에
                // index 값(hashCode % M)을 다시 계산해야 한다. 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

그런데 이렇게 해시 버킷 크기를 두 배로 확장하는 것에는 결정적인 문제가 있다. 해시 버킷의 개수 M이 2a 형태가 되기 때문에, index = X.hashCode() % M을 계산할 때 X.hashCode()의 하위 a개의 비트만 사용하게 된다는 것이다. 즉 해시 함수가 32비트 영역을 고르게 사용하도록 만들었다 하더라도 해시 값을 2의 승수로 나누면 해시 충돌이 쉽게 발생할 수 있다.

이 때문에 보조 해시 함수가 필요하다.

index = X.hashCode() % M을 계산할 때 사용하는 M 값은 소수일 때 index 값 분포가 가장 균등할 수 있다. 그러나 M 값이 소수가 아니기 때문에 별도의 보조 해시 함수를 이용하여 index 값 분포가 가급적 균등할 수 있도록 해야 한다.

보조 해시 함수(supplement hash function)의 목적은 '키'의 해시 값을 변형하여, 해시 충돌 가능성을 줄이는 것 이다. 이 보조 해시 함수는 JDK 1.4에 처음 등장했다. Java 5 ~ Java 7은 같은 방식의 보조 해시 함수를 사용하고, Java 8부터는 다시 새로운 방식의 보조 해시 함수를 사용하고 있다.

java 8

public int hashCode() {  
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

위 코드는 Horner's method를 구현한 방식으로, 단항식을 재귀적으로 사용하여 다항식 연산을 표현하였다.

String 객체 해시 함수에서 31을 사용하는 이유

• 31이 소수 이며 또한 어떤 수에 31을 곱하는 것은 빠르게 계산할 수 있기 때문이다.
• 31N=32N-N인데, 32는 25이니 어떤 수에 대한 32를 곱한 값은 shift 연산으로 쉽게 구현할 수 있다. 따라서 N에 31을 곱한 값은, (N << 5) – N과 같다. 31을 곱하는 연산은 이렇게 최적화된 머신 코드로 생성할 수 있기 때문에, String 클래스에서 해시 값을 계산할 때에는 31을 승수로 사용한다.

https://stdin2stdout.tistory.com/entry/Q-해쉬-충돌이-무엇이고-해결책을-알고-있나요

https://d2.naver.com/helloworld/831311