JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)

java에서 HashMap의 용량은 16이다. 그리고 이 용량을 꼭(MUST) 2의 거듭제곱으로 하라고 한다.

왜 그럴까? 컬랙션 프레임워크의 HashMap 클래스를 살펴보자.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

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

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //The next size value at which to resize (capacity * load factor).
    int threshold;

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);
      this.loadFactor = loadFactor;
      this.threshold = tableSizeFor(initialCapacity);
    }	

    //Returns a power of two size for the given target capacity.
    static final int tableSizeFor(int cap) {
      int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

	...

}

tableSizeFor 함수는 cap 이상인 2의 거듭제곱 중 가장 작은 수를 반환한다. 때문에 HashMap 생성 시 초기 용량을 어떤 숫자를 입력하더라도 2의 거듭제곱으로 테이블의 크기를 세팅하는 것을 볼 수 있다.

ex) initialCapacity 가

• 4 이면 4
• 5이면 8
• 15 이면 16

이렇게 하는 2가지 이유가 있다.

 

 

1. 빠른 인덱스 계산

해쉬 테이블의 인덱스는 해쉬 코드를 용량으로 나눈 나머지가 된다. 배열 용량이 2의 거듭제곱이면 AND 연산을 통해서 쉽게 변환할 수 있다. 용량이 2의 n 승이라면 해쉬 코드의 이진법 표현에서 n 번째 자릿수까지만 인덱스로 사용되기 때문이다.

서술형으로 보면 이해가 잘 안 갈 수 있으니 예시를 통해 알아보자

   - 해시 코드 : 311( 100110111(2) )

   - 용량 : 16( 10000(2),  2의 4승 )

이라고 해보자.

인덱스 = 해시 코드 & (용량-1) = 100110111(2) & 01111(2) = 0111(2) = 7

즉, 해시 코드 바이너리의 1에서 4번째 자릿수까지가 인덱스가 된다.

 

 

2. 사이즈를 늘릴 때 빠름 

용량을 늘릴 때도 기존 테이블을 이용해서 쉽게 할 수 있다. 해시 테이블의 크기가 2의 n 승에서 n+1 승으로 증가할 때 해시 코드의 n+1 자릿수가 0이면 인덱스를 그대로 유지하고, 1이면 인덱스에 2의 n승을 더해주면 된다. 아래 예를 통해 확인해 알아보자.

ex) 용량이 16( 10000(2), 2의 4승 ) 일 때 같은 인덱스 7을 갖는 해시 코드 2개가 있다.

• 311( 100110111(2) )
• 295( 100100111(2) )

여기서 용량을 16( 10000(2), 2의 4승 )에서 32( 100000(2), 2의 5승 )로 증가한다고 이라고 해보자.

311의 인덱스 = 00110111(2) & 11111(2) = 10111(2) = 23

295의 인덱스 = 100100111(2) & 11111(2) = 00111(2) = 7 가 된다.

해시 코드 바이너리의 5번째 값이 1이니 기존 인덱스에서 16(2의 4승)만 더하고 0 이면 기존 인덱스 유지한다.

 

참고 사이트 : https://www.javarticles.com/2012/11/hashmap-faq.html

HashMap Interview Questions - Java Articles

 

---

 

마무리.

컴퓨터는 숫자로 모든 것을 계산하고 그 숫자는 2진수이다. 

 

 

 

---

자료구조 시리즈

1. 자료구조의 종류와 개념 - 자료구조(1)

2. JAVA ArrayList - 자료구조(2)

3. JAVA LinkedList - 자료구조(3) 

4. JAVA ArrayList와 LinkedList 성능 비교 - 자료구조(4)

5. JAVA Queue 그리고 offer, poll , peek - 자료구조(5)

6. JAVA 왜 Stack 은 Array로, Queue는 LinkedList로 구현 했을까? - 자료구조(6)

7. JAVA Hash 그리고 HashMap 과 HashTable - 자료구조(7)

8. JAVA HashMap 과 HashSet의 성능 비교 - 자료구조(8)

9. JAVA HashMap의 용량은 왜 2의 거듭제곱일까? - 자료구조(9)