해시 표 의 간단 한 이해

해시 표 는 조회 속도 가 빠 르 고 효율 이 높다 는 장점 을 가지 고 배열 을 바탕 으로 특정한 상황 에서 링크 (빨 간 검 은 나무) 를 결합 한 데이터 구조 이다.
디자인 아이디어:
영어 알파벳 a - zzzzzz 의 문자열 을 배열 로 저장 하려 면 총 26 ^ 8 가지 결과 가 있 으 며, 알파벳 absdaw 를 조회 하려 면 배열 을 옮 겨 다 니 는 것 만으로 속도 에 영향 을 미친다.
영감 이 스 쳐 지나 갑 니 다. 모든 자모 와 배열 아래 표 시 를 연결 할 수 있다 면 빠르게 조회 할 수 없 으 며, 모든 문자 에 유일한 ASCII 값 이 있 습 니 다.
사고방식 1: 자모의 모든 문 자 를 추출 하여 ASCII 값 으로 변환 한 후 추가

   public int wordToNum(String word){
        int total = 0;
        for (int i = 0; i < word.length(); i++) {
            total += word.charAt(i) - 96;   //a ASCII 97，      96
        }
        return  total;
    }

문제: 서로 다른 자모 가 종종 같은 아래 표 에 대응 하 는 것 을 쉽게 발견 할 수 있다.
사고 2: 중복 성 문 제 를 해결 하기 위해 모든 문자 ASCII 값 을 직접 추가 하지 않 고 가 멱 차방 입 니 다.

    public int wordToNum(String word){
        int len = word.length();
        int total = 0;
        for (int i = 0; i < len; i++) {
            total += Math.pow(26,i)*(word.charAt(i) - 96);
        }
        return total;
    }

문제: 배열 이 매우 커 질 것 이 며, 심지 어 는 배열 이 허용 하 는 상한 선 (int 범위) 을 초과 할 수도 있다.
해결 방법: 나머지 압축 배열 용량 (나머지 최대 값 은 volume - 1)

return total % volume

용량 을 압축 한 후에 도 서로 다른 자모 가 같은 아래 표 시 를 대응 할 수 있다 (확률 이 적다).
후 사람들 은 두 가지 처리 방법 을 제시 했다.
1. 주소 법 열기       1.1 선형 탐지: 아래 표 시 된 공간 이 차지 하 는 것 을 발견 하면 빈 공간 이 있 을 때 까지 한 공간 을 탐지 합 니 다 (집적 효과 가 발생 하기 쉽 습 니 다: 대량의 데 이 터 는 한 지역 에 집중 합 니 다)       1.2 2 차 탐지: 1, 4, 9... 의 보폭 으로 뒤로 탐지 하여 빈자리 가 있 을 때 까지 탐지 합 니 다.       1.3 재 해시: 계 산 된 Hash 값 은 Hash 에 있 고 빈자리 가 있 을 때 까지 2. 링크 법:       간단 한 설명: 즉, 중복 되 는 아래 에 링크 를 걸 어 다음 에 표 시 된 나머지 값 을 저장 하 는 데 사용 합 니 다.
주: 1.7 의 HashMap 밑바닥 은 바로 체인 테이블 을 추가 하 는 것 입 니 다. 하 나 는 체인 테이블 이 한도 값 을 초과 하면 체인 테이블 1.8 의 HashMap 밑바닥 을 줄 이기 위해 수 조 를 확대 합 니 다. 하 나 는 빨간색 과 검은색 트 리 입 니 다. 하 나 는 체인 테이블 이 한도 값 을 초과 하면 체인 테이블 대신 빨간색 과 검은색 트 리 를 생 성 합 니 다.