2 차방 취 여 기술 이 HashMap 에서 의 응용

[size = medium] 잉여 계산 은 컴퓨터 에 있어 서 상대 적 으로 느 리 지만 많은 장면 에서 예 를 들 어 순환 대기 열 포인터 의 이동, hashmap 의 해시 작업 은 모두 잉여 연산 을 해 야 한다.
사고의 큰 방향 을 해결 하 는 것 은 곱셈 대신 논리 적 으로 오른쪽으로 이동 하 는 것 과 같다 (x * 2 는 x < 1). 또한 논리 적 연산 을 통 해 나머지 를 대체 할 수 있다.여기 에는 N 이 2 인 차방 (Power of two) 이 있 으 면 X% N = = X & (N - 1) 이라는 규칙 이 있다.
간단하게 검증 해 보 자. N = 256 을 설정 하고 X256 을 설정 하면 모든 높 은 부분 은 256 의 배수 이 고 높 은 부분 은 & 차단 되 며 X 가 X - n * 256 로 전환 되 는 것 과 같 으 며 등식 이 성립 된다.
우 리 는 HashMap 이 이 기술 을 어떻게 활용 하 는 지 볼 수 있 습 니 다. 먼저 HashMap 은 알고리즘 을 통 해 여과 하여 Hash 표 의 용량 을 2 의 차방 배 로 유지 합 니 다.[/size]

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

[size = medium] 물론 API 로 간단하게 실현 할 수 있 습 니 다 [/ size]

    /**
     * Calculate the next power of 2, greater than or equal to x.

     * From Hacker's Delight, Chapter 3, Harry S. Warren Jr.
     *
     * @param x Value to round up
     * @return The next power of 2 from x inclusive
     */
    public static int ceilingNextPowerOfTwo(final int x)
    {
        return 1 << (32 - Integer.numberOfLeadingZeros(x - 1));
    }

[size = medium] 우 리 는 HashMap 의 용량 이 기호 가 있 는 int 형 을 보 았 기 때문에 최대 용량 은 2 의 31 제곱 (최고 위 는 기호 위치) 이라는 것 을 쉽게 알 수 있다.[/size]

    /**
     * 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;

[size = medium] 용량 이 cap 이 고 key 의 hashcode 는 h 라 고 가정 합 니 다. HashMap 은 tab 배열 로 요 소 를 저장 합 니 다. 요 소 는 배열 의 아래 에 표 시 된 위치 index = tab [h & (cap - 1)] 를 사용 합 니 다. 핵심 getNode 방법 을 살 펴 보 겠 습 니 다. [/ size]

final Node getNode(int hash, Object key) {
        Node[] tab; Node first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }