[JAVA] HashMap

 

저번 시간을 통해 hash 함수로 hashCode를 구하고,

hashCode로 hashIndex를 구하는 과정을 대략적으로 보았습니다.

실제 hashMap은 어떻게 구현 했는지 살펴 보겠습니다.

key 값으로 String이 들어온 경우 hashCode를 어떻게 구하는지 알아 보겠습니다.

 

[String hashCode]

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
         h = 31 * h + getChar(value, i);
    }
    return h;
}

 

String은 값 자리의 char값을 통해 hashCode를 구합니다.

각자리의 char 값을 통해 hash를 누적 하며 31과 곱해 주는것을 볼수 있습니다.

왜 31을 곱할까요?

그 이유는 짝수를 곱하여 오버 플로우가 발생하면 오른쪽은 0이 되고 정보의 손실이 발생 하기 때문 입니다.

0000 1111 = 15
0001 1110 = 30 ( 15 << 1 )
0011 1100 = 60 ( 15 << 2 )
0111 1000 = 120 ( 15 << 3 )
....
0000 0000 = 15 << 8

 

짝수를 곱하면 정보의 손실로 해쉬 충돌 가능성이 높아 지게 됩니다.

그런데 왜 홀수 중 31을 곱해야 할까요?

이펙티브 저자님의 말로는 큰 의미는 없지만 관례적으로 그렇게 사용 했다고 합니다.

 

 

[ HashMap.hash ]

static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

방금 구한 String key hashCode를 통해서 부호 없는 우측 쉬프트 연산 후 XOR 연산을 하고 있습니다.

왜 이렇게 쉬프트 연산을 하고 XOR 연산을 해야 할까요?

단순히 hashCode % map.length 하면 안될까요?

그 이유는 예시로 길이가 4라고 하면 나머지 연산은 hashCode의 하위 비트만 사용 되기 때문 입니다.

그레서 해쉬의 균등한 분포를 위해 상위 비트와 하위 비트를 섞는 과정을 하는것 입니다. 

예시로 2비트를 옮겨 XOR 연산을 해보겠습니다.

 

1110
XOR
0011 ( h >>> 2 )
= 1101

 

하위 비트와 상위비트가 섞이는 것을 볼수 있습니다.

 

 

[ HashMap putVal ]

if ((p = tab[i = (n - 1) & hash]) == null)
	tab[i] = newNode(hash, key, value, null);

 

섞은 hashCode를 hashMap의 Index 범위인 n - 1 과 and ( & ) 연산을 통해 hashIndex를 구하게 됩니다.

 

참고 : https://velog.io/@indongcha/hashCode%EC%99%80-31