자바 HashMap의 capacity 는 왜 항상 2의 n승일까?

HashMap 의 코드를 보면 capacity 의 초기값, 최댓값은 power of two( 2ⁿ ) 가 되어야 하고,

resize 메소드 또한 power of two( 2n ) 의 값을 리턴한다고 적혀있습니다.

openjdk11 코드를 사용하였습니다.

// HashMap.java 코드

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;


/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() { ... }

HashMap 은 왜 capacity 를 2ⁿ 으로 증가시킬까요?

그 이유는 HashMap 에서 데이터를 저장할 index를 연산할 때

2ⁿ - 1 을 이진수로 표현 시 모두 1 인 특성을 사용하기 때문입니다.

 

 

2ⁿ - 1 과 &(AND) 비트연산

---

어떤 값 N 과 2ⁿ - 1 을 & 연산하면 어떻게 될까요?

값은 항상 2ⁿ - 1 이하가 나옵니다. 계산의 예시를 들어보겠습니다.

100 과 2⁴ - 1 을 & 연산해보겠습니다.

0110  0100
0000 1111     &
------------------
0000 0100  

값은 4가 나옵니다.

위 계산에서 볼 수 있듯이 어떤 값이던 2⁴ - 1 과 & 연산하면 2⁴ - 1 이하가 나옵니다.

이와 같은 특성을 HashMap 에서 사용합니다.

 

 

HashMap 에서 2ⁿ -1 과 & 연산

---

HashMap 은 저장할 데이터를 Node 클래스의 인스턴스로 만들고 Node 배열에 저장합니다.

그래서 HashMap 코드를 보면 table 이라는 Node 배열 변수를 볼 수 있습니다.

transient Node<K,V>[] table;

이 배열의 크기는 2ⁿ 의 크기로 증가합니다.

 

HashMap 에 데이터를 삽입하는 코드를 보고 어떻게 구현되어 있는지 확인해 보겠습니다.

put 메소드는 putVal 메소드를 바로 호출합니다.

여기서 key 값은 hash 메소드를 통해 가공되어 전달되는데 이 부분은 뒤에서 확인해 보겠습니다.

putVal 메소드의 표시된 부분에서 & 연산을 통해 index 값을 구합니다.

n 이 Node 배열의 길이이고 2의 거듭제곱 (2^x) 이기 때문에 

임의의 hash 값과 n -1 값을 & 연산하면 Node 배열의 유효한 index 값을 구할 수 있습니다.

 

그렇다면 putVal 메소드로 전달되는 hash 값은 어떤 값인지 알아보겠습니다.

 

 

HashMap 에서 hash 메소드

---

hash 메소드의 코드는 아래와 같습니다.

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

hash 메소드에서는 key 인스턴스를 그대로 받아서 hash 값을 연산하여 리턴합니다.

하지만 key 의 hashCode 메소드의 리턴값을 그대로 사용하지 않고 shift 와 xor 연산하는 것을 볼 수 있습니다.

 

이런 연산을 하는 이유는 위에서 수행한 (n - 1) & hash 연산의 충돌을 최대한 피하기 위함입니다.

n - 1 이 작으면 상위에 있는 비트는 무시되기 때문에 이를 shift 로 퍼뜨려서 충돌을 피하기 위한 연산이라고 합니다.

아래 표는 추가 연산이 없을 경우 충돌이 일어나는 케이스를 보여줍니다.

hash	hash(2진수)	hash & 25 -1	(hash ^ hash >>> 16) & 25 -1
65,537	0000 0000 0000 0001 0000 0000 0000 0001	1	0
131,073	0000 0000 0000 0010 0000 0000 0000 0001	1	3
262,145	0000 0000 0000 0100 0000 0000 0000 0001	1	5

 

 

 

결론

---

HashMap 의 capacity 를 2ⁿ 으로 증가하는 이유는

임의의 hash 값과 & 연산을 통해 유효한 범위의 index 값을 도출해 내기 위함입니다.

 

그리고 key 인스턴스의 hashCode 값을 그대로 사용하지 않고 shift 와 xor 를 사용하여

& 연산 시 상위 비트를 개입시켜 충돌을 회피하도록 구현되었습니다.

 

 

 

출처

Learning HashMap