(JAVA) HashMap은 테이블 인덱스를 어떻게 구하는가?

HashMap에 대한 내용을 공부하다 HashMap의 테이블 인덱스 값을 구하는 과정이 상당히 복잡하다는 것을 알았다.
해당 내용은 쉽게 까먹어버릴 수 있으니 다음번 리마인드를 위해서 더 나아가 많은 분들께 공유하고자 하는 마음에 포스팅을 하기로 마음먹었다.

 

해시 맵의 테이블 값을 구하는 과정은 크게 세 가지로 나뉜다. 

Key값의 타입에 대한 hash 값 
XOR 연산
현재 HashMap 사이즈와의 & 연산 

이렇게 세 가지 과정으로 이루어진다.
이제 코드와 예시를 통해서 천천히 살펴보도록 하자!

---

너무 많은 코드는 개발자들을 헷갈리게 하므로 인덱스 값을 구하는 코드만 집중적으로 보도록 하자!

 

범위가 너무 넓어지면 오히려 더 헷갈리게 할 수 있으므로 우리는 HashSize가 디폴트 값인 16일 때만을 볼 것이고

Key가 정수일 때만을 볼 것이다.

---

코드를 통해 확인하기

xor 연산

& 연산

 

위의 두 코드는 서론에서 언급한 XOR 연산과 & 연산이다.

 

위의 코드를 함축한 코드를 작성해보겠다.

public class Hash {
    public static void main(String[] args) {
        Integer targetNum =  1;
        int hash = targetNum.hashCode();

        int mapHash = hash ^ (hash >>> 16);

        int tableIndex = 15 & mapHash;

        System.out.println("tableIndex " + tableIndex);
    }
}

 

이 코드를 해석하기 위해서는 아래와 같은 지식이 필요하다.

• Integer의 해시 코드는 자신의 값을 반환한다.
• >>> 연산은 2진수로 변환하여 우측으로 해당 숫자만큼 시프트 한다는 것이다. 
• ^ 연산은 xor 연산으로써 다를 때만 1을 반환하고 나머지는 모두 0을 반환한다.
• & 연산은 같을 때만 1을 반환하고 나머지는 모두 0을 반환한다.

 

위의 지식을 바탕으로 연산을 진행해보자!

---

targetNum이 1일 때

targetNum이 1이면 Integer의 hashCode는 자기 자신을 반환함으로 hash는 1이 된다.

 

 

그리고 하기와 같은 연산을 진행한다.

int mapHash = hash ^ (hash >>> 16);

hash를 1로 치환해서 보면 아래와 같다.

 

1 ^ (1 >>> 16);

 

1 >>> 16을 하게 된다면 1의 위의 모든 값은 0이므로 0을 반환한다.

 

그 결과에 xor 연산을 진행해보자! 

(차이를 뚜렷하게 보기 위해서 4bit로 표현해보자)

1 ^ 0 =  0001 ^ 000 = 0001

 

xor 연산은 앞에서 언급하였듯이 다를 때만 1이고 최종 테이블 인덱스 값은 1이 된다.

최종 결과

---

targetNum이 18일 때

그렇다면 테이블 인덱스는 자기 자신 값을 반환하는 것이구나 라고 오해할 수 도 있기 때문에 이전보다 조금 더 큰 값인 18로 예시를 들어보자!

 

 

int mapHash = hash ^ (hash >>> 16);

hash를 18로 치환해서 보면 아래와 같다.

 

18 ^ (18 >>> 16);

 

18을 2진수로 표현하면 10010이다.

16비트 시프트를 진행하면 0이 된다.

 

해당 결과 값을 xor 연산을 하면 

18 ^ 0 = 10010 ^ 00000 

(5비트 기준)

 

18 자신을 리턴한다.

 

그러면 현재 HashMap 사이즈와 & 연산을 진행해보자!

 

15 & 18 = 01111 & 10010

 

결과는 2를 리턴한다.

최종 결과

---

targetNum이 -1일 때

마지막으로 음수일 때를 살펴보면서 포스팅을 마무리하고자 한다.

 

-1을 비트 연산으로 하는 것이 조금 힘들다. 

이번 기회에 정리해보고자 한다! (다 왔다 파이팅!)

1단계, 1을 8비트로 만들어보자. (- 는 생각하지 않는다.)

00000001


2단계, -1는 음수이기 때문에, 첫 번째 부호 비트를 1로 바꾸자.

10000001


3단계, 0은 1로, 1은 0으로 바꾸자.(1의 보수)
단, 부호 비트는 그대로 유지하자.

11111110


4단계, 3단계 결괏값에 1을 더하자.

11111111

결과 : 11111111

 

이제 -1의 2진수를 구하였으니 위의 과정을 반복하면 된다.

(32비트 기반의 jdk 기준)

 

Shift 연산 진행

11111111111111111111111111111111 >>> 16 

 

결과 : 0000000000000000111111111111111 

 

이것을 10진수로 표현하면 65535가 된다.

 

xor 연산을 진행하자

11111111111111111111111111111111 ^ 0000000000000000111111111111111 

= 11111111111111110000000000000000 

2진수 11111111111111110000000000000000을 10진수로 표현하는 방법이다.
다들 아시다시피 첫 번째 비트가 1이기 때문에 요놈은 음수라는 걸 인지하고 변환 들어가자.

1단계, 1은 0으로, 0은 1로 변환한다.(1의 보수)
00000000000000001111111111111111

2단계, 1단계에서 나온 결과에 1을 더하자. (2의 보수)
00000000000000010000000000000000

3단계, 2단계 결과를 10진 수화하여 '-'기호를 붙이자.
-65536

결과 : -65536

 

 

 

마지막으로 & 연산을 진행하면

15 & -65536 = 

 

01111 & 11111111111111110000000000000000 = 겹치는 비트 중 같은 것이 없기 때문에 0을 리턴한다.

 

즉 테이블 인덱스는 0이 된다.

---

정리

힘든 과정이었다. 

add(1), add(18), add(-1)을 하는 단순한 과정이었음에도 불구하고 테이블 인덱스를 구하기 위한 과정은 상당히 복잡하였다.

복잡함을 느끼는 이유는... 필자가 아마도 비트 연산에 익숙하지 않기 때문이었을 것이다.

 

이것만 기억하자

• xor
• >>>
• &

이 연산을 제대로 할 수 있으면 어렵지 않게 읽을 수 있다.

 

 

이번 기회로 비트 연산에 대한 기본을 공부하였으니 다음 포스팅에서는 이를 기반으로 HashSet에 대해서 심도 있게 다루어 보고자 한다.

---

 

Code Link

github.com/mike6321/PURE_JAVA/blob/master/IntoJAVA/src/main/java/me/choi/datastructure/Hash.java

mike6321/PURE_JAVA

References

ko.calcuworld.com/%EC%88%98%ED%95%99/2%EC%A7%84%EB%B2%95-%EA%B3%84%EC%82%B0%EA%B8%B0/

2진법 계산기 - 계산기

blog.naver.com/PostView.nhn?blogId=cache798&logNo=130001654115

음수 2진수와 10진수간의 변환 방법