해쉬맵

해쉬맵 정리 - https://d2.naver.com/helloworld/831311

 

해쉬테이블은 NODE객체를 담는 1차원 배열이다. (자바8 이전에는 Entry객체를 담음)

배열에 길이는 최초 16으로 할당되고, 2배씩 증가한다(2의 제곱이라는 것이 중요! 이유는 뒤에 설명)

NODE객체는 hash, key value, next 4개의 멤버변수를 담고있다.

 

Key에서 받아온 해쉬값을 가지고 저장될 인덱스를 결정하는데, 배열의 크기가 16이라면 해쉬%16 해서 나머지값을 인덱스로 두면 된다. 근데 여기서 해쉬%16이 아니라 (16-1) & hash 를 통해 인덱스를 구한다. 배열의 길이가 2의 제곱일 경우 해쉬%배열길이 = (배열길이-1)&hash 이며, and연산을 하는것이 더 빠르다(위에서 중요하다고 한 이유).

(참고: https://stackoverflow.com/questions/27230938/why-hashmap-insert-new-node-on-index-n-1-hash)

 

같은 인덱스에 또 node객체가 들어오면, 앞 노드의 next 멤버변수에 들어가는 형태(링크드 리스트임)