본문 바로가기
카테고리 없음

240620 Map

kinggora 2024. 6. 20. 17:56

Hashtable

package java.util

 

해시 테이블의 구현체
HashMap과 유사하지만 동기화 지원

 

Hashing
키를 해시 함수를 사용해 변환한 해시 값 -> 배열의 인덱스로 사용하여 값을 저장
Key -> [ Hash Function ] -> Hash Value

Hash Table
(Key, Value) 형태의 데이터를 저장하는 자료구조

1. null을 제외한 모든 object를 key, value로 사용할 수 있다.

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode(); // key 객체의 해시코드 참조
        ...
 }

 

2. Key로 사용되는 객체는 hashCode()와 equals() 메서드를 구현해야 한다.

  • hashCode(): 객체의 주소 값에 해시 함수를 적용한 고유 값을 반환
  • Hashtable의 인스턴스는 해시 테이블 성능에 영향을 미치는 두 가지 파라미터를 가진다.
    => initialCapacity, loadFactor

생성자

public Hashtable(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal Load: "+loadFactor);
        }
        if (initialCapacity==0) {
            initialCapacity = 1;
        }
        this.loadFactor = loadFactor;
        table = new Hashtable.Entry<?,?>[initialCapacity];
        threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

 

- Capacity(용량): 해시 테이블의 버킷 수
- loadFactor(적재율): 해시 테이블의 용량이 자동으로 증가하기 전에 어느 정도의 용량을 허용하는지에 대한 기준

                                  테이블 크기(N)에 대한 키의 개수(K) => K/N

Hashtable vs HashMap

  • Hashtable은 key, value로 null을 사용할 수 없지만, HashMap은 null 사용 가능하다.
  • Hashtable은 Dictionary 클래스를 상속하고 HashMap은 AbstractMap 클래스를 상속한다.
  • Hashtable은 동기화를 지원하므로 HashMap보다 느리다
    • 대부분의 메서드가 synchronized 키워드로 정의되어 있다. (thread-safe)

WeakHashMap

package java.util

 

Weak 키를 가진 해시 테이블

  • WeakHashMap에 저장된 (Key, Value) 엔트리가 있을 때, Key가 사용되지 않으면 자동적으로 삭제된다.
  • 정확하게는, Key 객체가 가비지 컬렉터에 의해 제거 -> Map에서 해당 Key에 매핑되는 Entry 자동 삭제

가비지 컬렉터: 힙(Heap) 내 객체 중 가비지를 찾아내 메모리 회수
가비지인지 판별하는 기준: 참조 여부(Reachability)

 

참조 유형과 가비지 컬렉션

참조 유형에 따라 GC 때의 동작을 다르게 지정
https://d2.naver.com/helloworld/329631

 

1. 강한 참조 (Strong Reference)
Object obj = new Object();
변수가 객체를 직접 참조할 때, 가비지 컬렉션의 대상이 되지 않는다.
  
2. 소프트 참조 (Soft Reference)
SoftReference<Object> softReference = new SoftReference<>(new Object());
SoftReference 클래스를 사용해 만들어진다.
메모리가 부족할 때 가비지 컬렉터에 의해 회수된다.
  
3. 약한 참조 (Weak Reference)
WeakReference<Object> weakReference = new WeakReference<>(new Object());
WeakReference 클래스를 사용해 만들어진다.
가비지 컬렉션 시점에 항상 회수된다.

 

내부적으로 WeakReference<Object>를 상속받은 Entry를 static class로 정의하여 key-value 저장

import java.util.WeakHashMap;

public class Main {
    public static void main(String[] args) {
        WeakHashMap<String, String> map = new WeakHashMap<>();
        String key1 = new String("1000");
        String key2 = new String("2000");
        map.put(key1, "A");
        map.put(key2, "B");
        key1 = null; // 강한 참조 삭제
        System.gc(); // 강제 가비지 콜렉션. key1이 참조하던 인스턴스 제거
        map.entrySet().forEach(System.out::println); // map에 저장된 Entry 출력

        // 출력 결과
        // 2000=B
    }
}

 

  • key, value로 null 사용 가능
  • HashMap 클래스와 유사한 특성을 가지며, initialCapacity, loadFactor으로 성능 제어
  • String 리터럴처럼 캐싱되어 있는 객체는 WeakHashMap 은 자동으로 삭제되지 않는다.

EnumMap

package java.util

 

Enum 타입 키를 사용하는데 특화된 Map 구현체

  • 내부적으로 배열(Array)을 사용하여 데이터를 저장한다. -> 성능 이점
  • 해시를 사용하지 않으므로 해시 충돌이 없다.
  • null 키를 허용하지 않는다.
  • enum 상수가 선언되는 순서인 natural order에 따라 Key 순서를 유지한다.
    -> keySet(), entrySet(), values() 등으로 element를 순차 탐색하면 순서 확인 가능
enum DayOfWeek {
    MON, TUE, WED, THU, FRI, SAT, SUN
}
  
public class Main {
    public static void main(String[] args) {
        EnumMap<DayOfWeek, String> enumMap = new EnumMap<>(DayOfWeek.class);
        enumMap.put(DayOfWeek.SUN, DayOfWeek.SUN.name());
        enumMap.put(DayOfWeek.FRI, DayOfWeek.FRI.name());
        enumMap.put(DayOfWeek.MON, DayOfWeek.MON.name());
        for(DayOfWeek key : enumMap.keySet()) {
            System.out.println(key);
        }
  
  		// 출력 결과
        // MON
        // FRI
        // SUN
    }
}

 

put()

enum 상수를 인덱스로 배열에 value 저장
중복 키로 입력 시 이전 값 삭제

public V put(K key, V value) {
    typeCheck(key);
  
    // enum 상수를 인덱스로 배열에 value 저장
    int index = key.ordinal(); 
    Object oldValue = vals[index];
    vals[index] = maskNull(value);
    if (oldValue == null)
        size++;
    return unmaskNull(oldValue);
}

 

생성자

1. Key 의 Enum 타입을 지정하여 빈 EnumMap 생성
  - keyUniverse: 캐싱을 위한 키 배열

public EnumMap(Class<K> keyType) {
    this.keyType = keyType;
    keyUniverse = getKeyUniverse(keyType);
    vals = new Object[keyUniverse.length];
}

 

2. EnumMap으로부터 같은 Key 타입을 가진 EnumMap 생성

public EnumMap(EnumMap<K, ? extends V> m) {
    keyType = m.keyType;
    keyUniverse = m.keyUniverse;
    vals = m.vals.clone();
    size = m.size;
}

 

3. Map 객체로부터 EnumMap 생성

public EnumMap(Map<K, ? extends V> m) {
        if (m instanceof EnumMap) {
            EnumMap<K, ? extends V> em = (EnumMap<K, ? extends V>) m;
            keyType = em.keyType;
            keyUniverse = em.keyUniverse;
            vals = em.vals.clone();
            size = em.size;
        } else {
            if (m.isEmpty())
                throw new IllegalArgumentException("Specified map is empty");
            keyType = m.keySet().iterator().next().getDeclaringClass();
            keyUniverse = getKeyUniverse(keyType);
            vals = new Object[keyUniverse.length];
            putAll(m);
        }
}

티스토리툴바