HashMap 실현 원리 개술

1. 데이터 구조 초기 화 HashMap 은 배열 과 링크 두 가지 데이터 구조의 조합 으로 HashMap 을 초기 화 할 때 먼저 배열 Entry 를 초기 화 합 니 다. 이 배열 의 모든 요 소 는 정적 내부 클래스 Entry 입 니 다.

 /**
     * An empty table shared by all zero-capacity maps (typically from default
     * constructor). It is never written to, and replaced on first put. Its size
     * is set to half the minimum, so that the first resize will create a
     * minimum-sized table.
     */
    private static final Entry[] EMPTY_TABLE
            = new HashMapEntry[MINIMUM_CAPACITY >>> 1];

/**
     * Constructs a new empty {@code HashMap} instance.
     */
    @SuppressWarnings("unchecked")
    public HashMap() {
        table = (HashMapEntry[]) EMPTY_TABLE;
        threshold = -1; // Forces first put invocation to replace EMPTY_TABLE
    }

static class Entry<K,V> implements Map.Entry<K,V> {  
        final K key;  
        V value;  
        final int hash;  
        Entry next;  
..........  
} 

2. put 방법 HashMap 에서 put ("key", "value") 방법 을 호출 할 때 먼저 들 어 오 는 key 에 따라 해당 하 는 hash 값 을 계산 한 다음 에 얻 은 hash 값 을 (배열 길이 - 1) 와 연산 하여 이 key 에 대응 하 는 Entry 요 소 를 배열 에서 표시 합 니 다.이 아래 표 시 된 곳 에 요소 가 존재 한다 면 이 요소 가 존재 하 는 요소 의 key 값 과 같 는 지 판단 합 니 다.같 으 면 이 키 에 대응 하 는 value 값 을 바 꾸 고 키 는 변 하지 않 습 니 다.key 가 다 르 지만 key 에 대응 하 는 hash 값 이 같 으 면 배열 에서 같은 위치 에 있 는 요 소 는 링크 형식 으로 저장 되 고 이 위치 에 가장 먼저 들 어간 것 은 링크 의 꼬리 부분 에 넣 고 새로 추 가 된 것 은 링크 의 머리 에 넣 습 니 다.

/**
     * Maps the specified key to the specified value.
     *
     * @param key
     *            the key.
     * @param value
     *            the value.
     * @return the value of any previous mapping with the specified key or
     *         {@code null} if there was no such mapping.
     */
    @Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry[] tab = table;
        int index = hash & (tab.length - 1);
        for (HashMapEntry e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }

3. get () 방법 HashMap 에서 get ("key") 방법 을 호출 할 때 역시 key 에 대응 하 는 hash 값 을 먼저 계산 하고 hash 값 에 따라 key 에 대응 하 는 Entry 요소 가 배열 에 있 는 위 치 를 찾 은 다음 에 key 의 equals 방법 을 통 해 해당 하 는 요 소 를 찾 습 니 다.

/**
     * Returns the value of the mapping with the specified key.
     *
     * @param key
     *            the key.
     * @return the value of the mapping with the specified key, or {@code null}
     *         if no mapping for the specified key is found.
     */
    public V get(Object key) {
        if (key == null) {
            HashMapEntry e = entryForNullKey;
            return e == null ? null : e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry[] tab = table;
        for (HashMapEntry e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

4. HashMap 확장 HashMap 초기 화 시 기본 capaticy 는 16 이 고 loadFactor 는 0.75 입 니 다. HashMap 의 용량 이 16 * 0.75 = 12 보다 클 때 HashMap 은 배열 확장 을 해 야 합 니 다. 배열 의 크기 는 16 * 2 = 32 로 변 합 니 다. 즉, 원래 의 배로 확 장 됩 니 다.그러나 배열 의 길이 가 변 할 때 HashMap 의 각 요소 의 위치 도 달라 집 니 다. 그 이 유 는 요소 의 위 치 는 key 에 대응 하 는 hash 값 과 배열 의 길이 - 1 에 따라 & 작업 을 하여 얻 은 것 입 니 다. 확장 후 배열 의 길이 가 바 뀌 면 모든 요소 가 배열 에 있 는 위 치 를 다시 계산 해 야 하기 때 문 입 니 다. 이것 은 시간 이 많이 걸 리 는 작업 입 니 다.따라서 HashMap 에서 요소 의 개 수 를 미리 알 고 있다 면 capacity 나 loadFactory (일반적으로 이 값 을 바 꾸 지 않 음) 를 바 꾸 어 HashMap 의 확장 을 피하 고 HashMap 의 작업 효율 을 높 일 수 있 습 니 다.예 를 들 어 이미 알 고 있 는 요 소 는 60 개 입 니 다. 확장 을 피하 기 위해 capacity * 0.75 > 60 이 고 capacity 가 2 인 n 제곱 이면 capacity 는 128 을 취 하 는 것 이 좋 습 니 다. 즉, new HashMap (128) 입 니 다.

/**
     * Constructs a new {@code HashMap} instance with the specified capacity and
     * load factor.
     *
     * @param capacity
     *            the initial capacity of this hash map.
     * @param loadFactor
     *            the initial load factor.
     * @throws IllegalArgumentException
     *                when the capacity is less than zero or the load factor is
     *                less or equal to zero or NaN.
     */
    public HashMap(int capacity, float loadFactor) {
        this(capacity);

        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Load factor: " + loadFactor);
        }

        /*
         * Note that this implementation ignores loadFactor; it always uses
         * a load factor of 3/4. This simplifies the code and generally
         * improves performance.
         */
    }

요약: 본 고 는 주로 HashMap 의 데이터 저장 구조, put, get 방법, 그리고 HashMap 확장 의 기본 원 리 를 말한다.