HashMap 해시 색인 알고리즘
HashMap
배열Node[] table
데 이 터 를 저장 하고 해시 코드int hash
배열 색인int index
데 이 터 를 액세스 하기 위해 계산 합 니 다.int capacity
값 은2
(0≤n≤30)(최소 값 은1
최대 값 은1073741824
1),배열 색인int index
최대 값 은(capacity -1) = 1073741823
이 고,해시 코드 범 위 는-2147483648 ≤ hashCode ≤ 2147483647
2(포함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 = 16
3 과 키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
개 비트 가 기호 비트(0
정1
마이너스)이기 때문에 결 과 는 마이너스(0
일 수 있 습 니 다)입 니 다.↩︎ 비트 별 또는
XOR
연산:두 비트 가 동시에0
로 돌아 갑 니 다.그렇지 않 으 면1
로 돌아 갑 니 다.↩︎ 비트 와
AND
연산:두 비트 모두1
일 때1
로 돌아 갑 니 다.그렇지 않 으 면0
로 돌아 갑 니 다.↩︎
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.