2021년 10월 09일 TIL

https://d2.naver.com/helloworld/831311

HashMap의 동작 원리에 대해서는 이 글을 참조하여 이해하였습니다.

결국 핵심은, 용적을 리사이징할때 2^N으로 늘리는 것에 있었습니다.

기존 크기가 4라고 가정하고, 커지는 크기가 8이라고 가정했을 때, 용적이 이렇게 2^N으로 늘어나면 배치될 수 있는 위치는 제자리이거나, 혹은 현재 자리에서 늘어난 용적만큼 이동한 인덱스의 위치입니다.

이것을 이해하는데 조금 오랜 시간이 소요됐는데, 직접 나머지연산을 해보면 금방 그렇다는 사실을 알 수 있습니다.

그렇다면 제자리에 배치되는 경우는 어떠한 경우이고, 현재 자리 + 늘어난 용적만큼 이동하는 경우는 어떤 경우인지에 대해서 고민해봐야하는데, 그것도 생각보다 간단하게 찾을 수 있었습니다.

나머지만 보지않고 몫을 보면 됩니다.

ex)

hash value : 9

기존 용적 : 4 -> 몫 2, index 1

resize 후 용적 : 8 -> 몫 1 , index 1

hash value : 5

기존 용적 : 4 -> 몫 1, index 1

resize 후 용적 : 8 -> 몫 0, index 5

이것을 보면 기존 용적에서 몫이 홀수이면 인덱스가 증가하고, 짝수이면 그대로라는 사실을 알 수 있습니다.

이것을 비트연산자로 표현하면, hash 값을 비트로 변환한 다음, 기존 용적에 해당하는 비트가 1이면 index를 증가시키고, 아니면 제자리에 두면 되는 것이다.

세상엔 정말 천재가 많다는 것을 새삼 느꼈다. 이런 것들을 알게되면 정말 재밌고, 나도 언젠가 이런 로직을 고안할 수 있을까 하는 배움의 즐거움이 생기는 듯 하다!