Hash 충돌 & 양수 변환 & loadFactor

💡 해시 충돌

• 서로 다른 값의 키가 일치하는 경우를 의미한다
• 충돌이 일어나지 않게 Folding 하는 방법
  • 함수를 구현할때 충돌을 피하고자 할때 어떻게 분포를 더 넓게 할지 생각하기
• 아래 사진은 전화번호를 받아서 3분할한 합을 키 배열에 저장하는 도중 Folding이 발생한 사진이다

번호를 3분할한것의 합을 키로 지정, 충돌 발생

• hashCode에서의 충돌문제를 해결한 문자열 표현
• 문자는 유니코드로 변환하여 숫자로 나타낼 수 있고, 각 문자를 변환 후 그 숫자들을 합하면 된다
  하지만 그렇게 했을 경우 단순히 문자의 위치와 관계없이 같은 문자열이 있다면 해시 충돌이 발생한다
• 문자의 위치에 따라 상수 g를 곱하는 횟수를 다르게 해서 충돌 문제 해결
  • 116 + g(104 + g(105 + g(115)))

    // 문자열을 기반으로 정수를 계산해주는 hashCode
    public int hashCode(String s) { // this 가 입력으로 들어온다고 가정
        int g = 31;
        int hash = 0; // 키 배열에 저장될 반환값

        // 상수 g를 문자의 위치만큼 제곱한뒤 곱한다
        for (int i=s.length()-1; i>=0; i--) { // s, i, h, t
            hash = g * hash + s.charAt(i);
        }
        return hash;
    }

 

같은 문자열이지만 문자의 위치에 따라 다른 결과값 반환, 충돌 문제 해결

 

해시 충돌 방지를 위한 해시 크기 최적화

• ex 1: 해시의 크기를 홀수로 설정하여 % 연산자를 사용했을 때 다양한 결과가 출력되도록 한다
  • hashCode() 에서 반환된 정수값으로 배열의 인덱스값으로 쓸 수 있도록 최적화 (정수는 음&양수 둘다 해당 가능)
  • 테이블 크기 최적화 (테이블의 크기를 홀수 & 소수로 설정)
• ex 2: 해시의 크기를 소수로 설정하여 나머지 값이 더 다양한 결과가 출력되도록 함
• 테이블 크기를 늘리는것과 왜 충돌이 발생할까?
  • hashCode는 키 값에서 정수값을 계산하는데 이때 해시 테이블의 길이를 벗어나지 않기 위해서
    테이블 길이로 해시함수의 리턴값의 나머지 연산한다
  • 예를 들어, 테이블의 크기가 6이고 특정 해시 함수를 사용했을때
    2배의 배수를 반환한다면 2,4,6,8 등을 반환하는데 이것을 해시 테이블 사이즈에 맞게 조정(%)하면
    2%6 = 2  |  4%6 = 4  |  6%6 = 0  |  8%6 = 2  |  10%4 = 4 로 변한다

딱봐도 충돌이 발생할 것 같다

• 이때, 테이블의 크기를 소수로 만들면 값이 균등하게 들어간다
  (소수는 1과 자기 자신을 제외한 수의 배수가 될 수 밖에 없기 때문)
• 배수가 나오는 경우의 수를 최대한 줄일때 충돌을 최대한 방지할 수 있게 된다
• 홀수로 설정하는 경우도 마찬가지로 모든 짝수는 최소공약수인 2를 공유하기 때문이다

---

💡 2의 보수 성질을 이용한 해시값의 양수 변환

• 배열의 인덱스는 음수가 될 수 없기 때문에 양수로 변환을 해줘야 한다
• 해시 결과값(음수)과 0x7FFFFFFF를 And연산 해주고 양수로 변환된 값에 테이블의 사이즈를 % 하면 됨

// data의 index 결정
int hashval = data.hashCode(s);
hashval = hashval & ox7FFFFFFF;
hashval = hashval % tableSize;

---

💡 loadFactor()  - 적재율

• 테이블에 데이터가 얼마나 있는지 알려주는 메서드
• 0 = 비어있다 / 1 = 꽉 찼다