자바 프로 그래 밍: String 클래스 의 hashCode () 방법 에 대한 상세 한 설명

\ # \ # # hash 의 정의 Hash 는 일반적으로 '해시' 로 번역 되 고 '해시' 로 직접 음역 되 는 것 도 있 습 니 다. 즉, 임의의 길이 의 입력 (프 리 맵, pre - image 라 고도 함) 을 해시 알고리즘 을 통 해 고정 길이 의 출력 으로 바 꾸 는 것 입 니 다. 이 출력 은 해시 값 입 니 다.이러한 전환 은 압축 맵 이다. 즉, 해시 값 의 공간 은 보통 입력 공간 보다 훨씬 작 고 서로 다른 입력 은 같은 출력 으로 흩 어 질 수 있 기 때문에 해시 값 에서 유일한 입력 값 을 정할 수 없다.쉽게 말 하면 임의의 길이 의 메 시 지 를 일정한 길이 의 메시지 요약 으로 압축 하 는 함수 입 니 다.
자바 에서 hash 값 의 의미

hash 값 은 주로 해시 저장 구조 에서 대상 의 저장 주 소 를 확정 하고 대상 의 조회 효율 을 향상 시 키 는 데 사용 된다. 예 를 들 어 HashMap, HashTable 등 이다.

만약 에 두 대상 이 같다 면 이 두 대상 의 hash 값 은 반드시 같다.

대상 의 equals 방법 을 다시 쓰 려 면 대상 의 hashCode 방법 을 최대한 다시 쓰 십시오.

두 대상 의 hash 값 이 같다 고 해서 반드시 두 대상 이 같다 는 것 은 아니다.

String 의 hashCode
hash 값 의 의 미 를 이해 한 후에 hash 계산 을 할 때 우 리 는 중복 hash 값 을 생산 할 확률 을 최대한 줄 이 고 데 이 터 를 더욱 분산 시 키 기 를 바 랍 니 다. 만약 에 반복 hash 값 이 너무 많 으 면 해시 저장 구조 에서 같은 hash 값 이 매 핑 되 는 대상 도 많아 서 조회 효율 을 낮 출 수 있 습 니 다.그리고 equals () 계산의 정확성 도 떨어진다.
다음은 String 류 의 hashCode () 방법 을 분석 합 니 다. 코드 는 다음 과 같 습 니 다.

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;
}

hashCode () 를 소개 하기 전에 이 방법 에서 사용 하 는 속성 을 알 아 보 겠 습 니 다.
value: private final 로 장 식 된 char 배열 입 니 다. String 류 는 이 배열 을 통 해 문자열 이 존재 합 니 다.

private final char value[];

hash: private 수식 int 변수 로 String 대상 의 hashCode 를 저장 합 니 다.

private int hash; 

다음은 hashCode () 의 실현 논 리 를 다음 과 같이 분석 합 니 다.
판정 조건 분석
hash 값 이 0 과 같 지 않 고 value. length 가 0 보다 크 면 hash 값 계산 을 합 니 다.여기 에는 두 가지 조건 이 포함 되 어 있 습 니 다. 첫 번 째 판정 조건:

h == 0

왜 h == 0 시 hashCode () 계산 을 합 니까?h 는 int 형식의 값 입 니 다. 기본 값 은 0 입 니 다. 따라서 0 은 hash 계산 을 실행 하지 않 았 을 수도 있 지만 hash 계산 을 실행 하지 않 았 다 고 표시 할 수 없습니다. 왜냐하면 hash 계산 후 0 값 이 발생 할 지 여 부 를 아직 확정 하지 못 했 기 때 문 입 니 다.
hash 계산 을 실행 하면 0 값 의 hash 가 발생 하지 않 습 니까?hash 의 계산 논리 에 따 르 면 val[0] = 0 시 공식 h = 31 * h + val[i]; 에 따라 계산 하면 h 의 값 은 0 과 같다.val[0] = 0 어떻게 설명 할 까요?ASCII 표를 보면 null 의 ASCII 값 이 0 입 니 다.분명히 val [0] 에 서 는 null 을 저장 할 수 없 기 때문에 hash 계산 후 0 값 이 발생 하지 않 습 니 다. h == 0 는 hash 계산 을 했 는 지 여 부 를 판단 하 는 조건 으로 할 수 있 습 니 다.
다른 판정 조건:

value.length > 0

문자열 의 길이 가 0 이면 hash 계산 을 하지 않 는 다 는 것 이다.
계산 공식 분석
다음은 hash 계산 공식 을 분석 하 겠 습 니 다.

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

hash 의 계산 절 차 를 모 의 해 보 겠 습 니 다.

String name = "liu"；

value = {'l', 'i', 'u'};
hash = 0;
value.length = 3;

//    ：
val = value;
val[0] = "l";
val[1] = "i";
val[2] = "u";

h = 31 * 0 + l = l;

h = 31 * (31 * 0 + l) + i = 31 * l + i;

h = 31 * (31 * (31 * 0 + l) + i) + u = 31 * 31 * l + 31 * i + u;

추론 해 낸 수학 공식 은 다음 과 같다.

val[0]*31^(n-1) + val[1]*31^(n-2) + ... + val[n-1]  

왜 31 일 까? 왜 32 가 아니 지?31 은 소수 이기 때문이다.무엇이 소수 입 니까? 왜 소 수 를 선택 합 니까?
소 수 는 질 수 라 고도 부른다. 1 보다 큰 자연수 에서 1 과 이 정수 자 체 를 제외 하고 다른 자연수 에 의 해 정 제 될 수 없 는 수 를 말한다.
소수 의 특성 에 따라 소수 와 곱 한 결 과 는 다른 방식 보다 유일 성 이 생기 기 쉽다. 즉, hash 값 이 중복 되 는 확률 이 비교적 적다.
소수 가 많은 데 왜 31 일 까요?
31 의 바 이 너 리 는 11111 로 5 개의 바 이 너 리 를 차지 하고 곱셈 연산 을 할 때 (x << 5) - x 로 전환 할 수 있다.
자바 에서 곱 한 숫자 가 너무 많 으 면 메모리 가 넘 치 는 문 제 를 일 으 켜 데 이 터 를 잃 어 버 리 는 곱셈 요 소 를 고려 해 야 합 니 다.
대수 상승 은 메모리 가 넘 치고 17 도 소수 인 데 왜 17 이 아 닙 니까?
나 도 속 았 어.
31 에 대하 여 대충 정리 하 다.

31 은 하나의 소수 로 소수 와 곱 한 결 과 는 다른 방식 보다 유일 성 이 생기 기 쉽다.

자바 에서 곱 한 숫자 가 너무 많 으 면 메모리 가 넘 치 는 문제 가 발생 하여 데 이 터 를 잃 어 버 립 니 다.

상기 두 가지 측면 에서 이 인자 의 값 을 고려 하 다.
참고 자료

Why does Java’s hashCode() in String use 31 as a multiplier

왜 hashcode 를 정의 할 때 31 이라는 숫자 를 사용 합 니까?

hashcode 에서 31 계 수 를 사용 하 는 문제