[Java] 해쉬맵(HashMap)에 대하여 심층적으로 알아보자

HashMap 이란?

 HashMap은 Map interface를 implements 한 클래스로서 key와 value의 쌍으로 이루어지며 hash 알고리즘을 사용하는 클래스

 

 

 

HashMap 특징

 

1. Hash table based implementation of the Map interface.

    해쉬 맵은 맵 인터페이스를 기반으로 구현

 

2. This implementation provides all of the optional map operations, and permits null values and the null key.

    해쉬맵은 맵의 수행을 모두 지원하며, key와 value에 null을 허용

 

3. This class makes no guarantees as to the order of the map.

    해쉬맵은 맵의 순서를 보장하지 않음

 

4. This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

    해쉬 함수가 복수의 버킷으로 요소를 적절히 분산 시키는 것을 상정해, 기본 수행(get, set)에 일정 시간 의 퍼포먼스 제공

   

5. An instance of HashMap has two parameters that affect its performance: (initial capacity, load factor) HashMap의 인스턴스에는, 성능에 영향을 주는 2개의 파라미터 초기용량, 부하계수가 존재

   초기 용량 - 버킷의 갯수

   부하계수 - 버킷에 들어가는 entry갯수와 버킷의 총수의 비율

   부하계수가 클수록(버킷에 들어가는 entry 갯수가 많아짐) 메모리 절약, 하지만 검색이 힘듬

   부하계수가 작을수록 (버킷이 많을수록) 검색을 빠르지만, 메모리상의 낭비가 일어남

   최적의 값은 0.75

 

6. Note that this implementation is not synchronized.

    해쉬맵은 동기화되지 않음.

 

 

 

 

HashMap 구조

 

1. 버킷 - entry들이 저장될 공간

 

2. entry - 한개의 key에 매핑되는 요소

 

 

transient Entry table[];                                                       // 버킷 배열

 

Entry(int i, Object obj, Object obj1, Entry entry)                    // entry 객체 구조

{

    value = obj1;

    next = entry;

    key = obj;

    hash = i;

}

 

HashMap 기본 상수 및 변수

static final int DEFAULT_INITIAL_CAPACITY = 16;                   // 기본 버킷수

static final int MAXIMUM_CAPACITY = 1073741824;                // 최대 버킷수

static final float DEFAULT_LOAD_FACTOR = 0.75F;                 // 기본 부하계수

transient Entry table[];                                       // 버킷 배열

transient int size;                                                              // 맵 크기(총 엔트리 갯수)

int threshold;                                                                    // 한계값

final float loadFactor;                                         // 부하계수

transient int modCount;

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = 2147483647;

transient boolean useAltHashing;

final transient int hashSeed;

private transient Set entrySet;

private static final long serialVersionUID = 362498820763181265L;

 

 

- HashMap 생성자 -

 

public HashMap(int i, float f)

{

    hashSeed = Hashing.randomHashSeed(this);

    entrySet = null;

    if(i < 0)                   //  해쉬맵 버킷수 유효성 체크

        throw new IllegalArgumentException((new StringBuilder()).append("Illegal initial capacity: ").append(i).toString());

    if(i > 1073741824)          //  해쉬맵 버킷 갯수가 1073741824를 넘길경우 1073741824로 재설정  

        i = 1073741824;

    if(f <= 0.0F || Float.isNaN(f))     // 부하계수 유효성 체크

        throw new IllegalArgumentException((new StringBuilder()).append("Illegal load factor: ").append(f).toString());

    int j;                              // 최종으로 만들어지는 버킷의 수

    for(j = 1; j < i; j <<= 1);         // 사용자가 입력한 버킷의 수를 기반으로 생성해야할 버킷의 수를 구하는 반복문

    loadFactor = f;                     // 부하계수

    threshold = (int)Math.min((float)j * f, 1.073742E+009F);       // 한계값 설정

    table = new Entry[j];               // 버킷 생성

    useAltHashing = VM.isBooted() && j >= Holder.ALTERNATIVE_HASHING_THRESHOLD;     // alt해싱 사용여부

    init();         // HashMap 내에서는 아무런 프로세스 없음

}

 

 

- put 함수 -

/**

 * put

 *

 * @param  obj - key

 * @param  obj1 - value

 * @return 이미 존재하는 key일경우 이전 value 값

 */

public Object put(Object obj, Object obj1)

{

    if(obj == null) {

        return putForNullKey(obj1);     //    만약 null인 경우 해당하는 버킷에 value put

    }

    int i = hash(obj);                  // 2. key의 해시값 구함

    int j = indexFor(i, table.length);  // 3. key의 해시값에 해당하는 버킷 인덱스 구함

   

    // 4. 버킷네 이미 존재하는 key인지 조사하며 이미 존재하는 key일경우 새로운 값 입력후 기존값 반환

    for(Entry entry = table[j]; entry != null; entry = entry.next)      // 해당 entry가 저장될 버킷에서 엔트리가 null일때까지 루프돔

    {

        Object obj2;  // entry.key -> 버킷내에 존재하는 엔트리들의 키가 저장될 변수

        if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2))) // 버킷내에 존재할경우  

        {

            Object obj3 = entry.value;      // 기존 value값을 새로운 value로 입력후 기존 value 리턴

            entry.value = obj1;

            entry.recordAccess(this);

            return obj3;

        }

    }

 

    modCount++;                 // 5. ?

    addEntry(i, obj, obj1, j);  // 6. 새로운 key일경우 j의 버킷에 entry 추가

    return null;

}

 

/**

 * addEntry

 *

 * @param  i    - key의 hash값

 * @param  obj  - key

 * @param  obj1 - value

 * @param  j    - hash값에 해당하는 버킷 인덱스

 */

void addEntry(int i, Object obj, Object obj1, int j)

{

    if(size >= threshold && null != table[j])       // 해쉬맵 크기가 임계값 이상일경우

    {

        resize(2 * table.length);                   // 해쉬맵 크기 늘림

        i = null == obj ? 0 : hash(obj);            // key가 null인경우 0, 아닌경우 해시값 구함

        j = indexFor(i, table.length);              // key의 해시값에 해당하는 버킷 인덱스 구함

    }

    createEntry(i, obj, obj1, j);

}

 

/**

 * createEntry

 *

 * @param  i    - key의 hash값

 * @param  obj  - key

 * @param  obj1 - value

 * @param  j    - hash값에 해당하는 버킷 인덱스

 */

void createEntry(int i, Object obj, Object obj1, int j)

{

    Entry entry = table[j];                     // 버킷에 매핑된 첫번째 entry

    table[j] = new Entry(i, obj, obj1, entry);  // 새로운 엔트리에 기존 버킷의 첫번째 entry를 next로 저장후 버킷에 추가

    size++;                                     // size 변수 증가

}

 

 

- get 함수 -

/**

 * get

 *

 * @param  obj  - key

 * @return key에 해당하는 value, null인경우 null리턴

 */

public Object get(Object obj)

{

    if(obj == null)                 // key의 null여부 판별

    {

        return getForNullKey();     // null key에 해당하는 value 리턴

    } else

    {

        Entry entry = getEntry(obj);    // entry값 가져옴

        return null != entry ? entry.getValue() : null;     // entry값이 null인 경우 null 리턴 아닌경우 entry의 value 반환

    }

}

 

/**

 * getEntry

 *

 * @param  obj  - key

 * @return key에 해당하는 entry 객체, null인경우 null리턴

 */

final Entry getEntry(Object obj)

{

    int i = obj != null ? hash(obj) : 0;            // key가 null인경우 0 아닌경우 key의 해시값 i에 입력

   

    // 해시값에 해당하는 버킷에서 key에 해당하는 entry 찾음 있을경우 entry 반환,

    for(Entry entry = table[indexFor(i, table.length)]; entry != null; entry = entry.next)

    {

        Object obj1;

        if(entry.hash == i && ((obj1 = entry.key) == obj || obj != null && obj.equals(obj1))) {

            return entry;

        }

    }

   

    // 못찾을경우 null 반환

    return null;

}

 

- remove 함수 -

/**

 * remove

 *

 * @param  obj - key

 */

public Object remove(Object obj)

{

    Entry entry = removeEntryForKey(obj);       // key를통해 entry 삭제 및 해당 엔트리 입력

    return entry != null ? entry.value : null;  // entry가 null이 아닐경우 삭제되는 엔트리 value 값 반환, null일경우 null 반환

}

 

/**

 * removeEntryForKey

 *

 * @param  obj - key

 */

final Entry removeEntryForKey(Object obj)     

{

    int i = obj != null ? hash(obj) : 0;        // key의 해쉬값 구함

    int j = indexFor(i, table.length);          // 해쉬값에 해당하는 버킷인덱스 구함

    Entry entry = table[j];                     // 해당 버킷의 첫번째 엔트리 구함

    Entry entry1;

    Entry entry2;

   

    // 버킷의 시작 entry부터 마지막 엔트리까지 key에해당하는 entry를 찾는 루프

    for(entry1 = entry; entry1 != null; entry1 = entry2)

    {

        entry2 = entry1.next;       // 현재 반복문이 가리키는 entry의 다음 entry

        Object obj1;

       

        // key에 해당하는 엔트리를 찾았을경우

        if(entry1.hash == i && ((obj1 = entry1.key) == obj || obj != null && obj.equals(obj1)))

        {

            modCount++;             // ?

            size--;                 // size -1;

            if(entry == entry1) {   // 현재 조건의 entry가 버킷의 시작 entry인경우

                table[j] = entry2;

            } else {                // 아닐경우

                entry.next = entry2;

            }

            entry1.recordRemoval(this);

            return entry1;

        }

       

        entry = entry1;     // 엔트리에는 현재엔트리 입력

    }

 

    return entry1;      // 못찾을경우 null 반환

}

 

 - putAll 함수-

/**

 * putAll

 *

 * @param  map

 */

public void putAll(Map map)

{

    int i = map.size();     // 맵의 크기 가져옴

    if(i == 0) {

        return;

    }

    if(i > threshold)       // 맵의 크기가 hashmap의 임계값보다 크면 리사이즈

    {

        int j = (int)((float)i / loadFactor + 1.0F);

        if(j > 1073741824) {

            j = 1073741824;

        }

        int k;

        for(k = table.length; k < j; k <<= 1) {

            ;

        }

        if(k > table.length) {

            resize(k);

        }

    }

    Map.Entry entry;        // 맵의 처음 entry 값 가져옴

   

    // 맵의 모든 entry를 hashmap안에 넣어줌

    for(Iterator iterator = map.entrySet().iterator(); iterator.hasNext(); put(entry.getKey(), entry.getValue())) {

        entry = (Map.Entry)iterator.next();

    }

 

}