HashMap 해시 색인 알고리즘

HashMap 과 hashCode
  • 집합HashMap배열Node[] table데 이 터 를 저장 하고 해시 코드int hash배열 색인int index데 이 터 를 액세스 하기 위해 계산 합 니 다.
  • 용량int capacity값 은2(0≤n≤30)(최소 값 은1최대 값 은10737418241),배열 색인int index최대 값 은(capacity -1) = 1073741823이 고,해시 코드 범 위 는-2147483648 ≤ hashCode ≤ 21474836472(포함0값 의 총 개 수 는‭4294967296‬용량int capacity최대 값 의4배)입 니 다.용량 및 최대 색인 수치 표
  • 해시 맵 해시 인덱스
    int h = key.hashCode();
    int hash = h ^ (h >>> 16);
    int index = (capacity -1) & hash;
    Node<K,V> node = table[index];
    

    가정 용량int capacity = 163 과 키Integer key = 1234567890:
  • 산열 코드 계산int hash = h ^ (h >>> 16):부호 없 이 오른쪽으로 이동>>>연산 4 를 사용 하여 산열 코드h의 높 은 위치(앞 16 비트)를 얻 고,비트 별 이동 또는XOR연산 5 스 포일 러 산열 코드int hash의 낮은 부분(즉hash = h 16 + 16 (h 16 + h 16 ))을 사용 하여 높 은 위치 와 낮은 위치 가 동시에 충돌 할 확률 을 낮 춥 니 다.

  • 코드
    십 진법
    2 진법
    h
    1234567890
    01001001100101100000001011010010
    (h >>> 16)
    18838
    00000000000000000100100110010110
    hash = h ^ (h >>> 16)
    1234586436
    01001001100101100100101101000100
  • 계산 배열 색인int index = (capacity -1) & hash:한정 배열 색인int index최대 치 는2(0≤n≤30)- 1이 고,사용 위치 및AND연산 6 을 통 해 배열 색인 값 범 위 를0 ≤ index ≤ (capacity -1)로 확보 합 니 다.배열 색인 바 이 너 리 표
  • 코드
    십 진법
    2 진법
    (capacity -1)
    15
    00000000000000000000000000001111
    hash
    1234586436
    01001001100101100100101101000100
    index = (capacity -1) & hash
    4
    00000000000000000000000000000100
  • 액세스 배열 데이터Node node = table[4].

  • (끝)
    용량int capacity최소 치 는1최대 치 는HashMap.MAXIMUM_CAPACITY = 1073741824입 니 다.↩︎ int최소 치 는Integer.MIN_VALUE = -2147483648최대 치 는Integer.MAX_VALUE = 2147483647입 니 다.↩︎
    용량int capacity기본 값 은HashMap.DEFAULT_INITIAL_CAPACITY = 16입 니 다.↩︎
    부호 없 이 오른쪽으로 이동>>>연산:왼쪽1개 비트 부터 보충0,1개 비트 가 기호 비트(01마이너스)이기 때문에 결 과 는 마이너스(0일 수 있 습 니 다)입 니 다.↩︎
    비트 별 또는XOR연산:두 비트 가 동시에0로 돌아 갑 니 다.그렇지 않 으 면1로 돌아 갑 니 다.↩︎
    비트 와AND연산:두 비트 모두1일 때1로 돌아 갑 니 다.그렇지 않 으 면0로 돌아 갑 니 다.↩︎

    좋은 웹페이지 즐겨찾기