Map - HashMap 이론과 구현

 

📌 Map<K, V> 컬렉션

- key와 value 한 쌍(Entry)으로 데이터를 저장

- key는 중복저장 불가, Value는 중복 가능

- Collection과는 별개의 interface이다. (List, Set과 기본 메서드가 다르다, List와 Set은 Collection을 상속)

- Key는 중복 불가, Value는 중복 허용

 

 

 

 

---

 

📌 Map<K, V> 컬렉션의 주요 메서드

Map<K, V>의 구현 클래스는 아래의 모든 메서드를 포함한다.

구분	리턴타입	메서드 이름	기능
데이터 추가	V	put(K key, V value)	입력 매개변수(키,값)을 Map객체에 추가
	void	putAll(Map<? extends K, ? extends V> m)	입력매개변수의 Map객체를 통제로 추가
데이터 변경	V	replace(K key, V value)	Key 값에 해당하는 값을 value로 변경 (old값 리턴) (단, 해당 key가 없으면 null 리턴)
	boolean	replace(K key, V oldValue, V newValue)	(key, oldValue)의 쌍을 가지는 엔트리에서 값을 newValue로 변경 (단, 해당 엔트리가 없으면 false를 리턴)
데이터 정보추출	V	get(Object key)	매개변수의 key값에 해당하는 valuye 값을 리턴
	boolean	containsKey(Object key)	매개변수의 key값이 포함되어 있는지 여부
	boolean	containsValue(Object value)	매개변수의 value 값이 포함되어 있는지 여부
	Set<K>	keySet()	Map 데이터들 중 key들만 뽑아서 Set객체로 리턴
	Set<Entry<K,V>>	entrySet()	Map의 각 Entry들을 Set 객체로 담아 리턴
	int	size()	Map에 포함된 데이터(Entry) 개수
데이터 삭제	V	remove(Object key)	입력 매개변수의 Key를 갖는 엔트리 삭제 (단, 해당 key가 없으면 아무런 동작을 안함)
	boolean	remove(Object key, Object value)	입력 배개변수의 (key, value)를 갖는 엔트리 삭제 (단, 해당 엔트리가 없으면 아무런 동작 안함)
	void	clear()	Map 객체내의 모든 데이터 삭제

 

 

---

 

📌 HashMap<K, V>

- Map<K, V> 인터페이스를 구현한 대표적인 구현 클래스

- Key, Value의 쌍으로 데이터를 관리하며 저장공간(capacity) 동적 관리 (default capacity : 16)

- 입력의 순서와 출력의 순서는 동일하지 않을 수 있음 (Key 값이 Set으로 관리)

 

예시코드)

public class HashMapMethod {
    public static void main(String[] args) {
        Map<Integer, String> hMap1 = new HashMap<>();

        //#1. put (K key, V value)
        hMap1.put(2, "나다라");
        hMap1.put(1, "가나다");
        hMap1.put(3, "다라마");
        System.out.println(hMap1.toString()); //{1=가나다, 2=나다라, 3=다라마}

        //#2. puttAll(다른객체)
        Map<Integer, String> hMap2 = new HashMap<>();
        hMap2.putAll(hMap1);
        System.out.println(hMap2.toString()); //{1=가나다, 2=나다라, 3=다라마}

        //#3. replace(K key, V value)
        hMap2.replace(1, "가가가");
        hMap2.replace(4, "라라라"); //없는 데이터, 동작안함
        System.out.println(hMap2.toString()); //{1=가가가, 2=나다라, 3=다라마}

        //#4. replace(K key, V oldValue, V newValue)
        hMap2.replace(1, "가가가", "나나나");
        hMap2.replace(2, "다다다", "라라라"); //동작안함
        System.out.println(hMap2.toString()); //{1=나나나, 2=나다라, 3=다라마}

        //#5. V get(Object key)
        System.out.println(hMap2.get(1)); //나나나
        System.out.println(hMap2.get(2)); //나다라
        System.out.println(hMap2.get(3)); //다라마

        //#6. containsKey(Object key)
        System.out.println(hMap2.containsKey(1)); //true
        System.out.println(hMap2.containsKey(5)); //false

        //#7. containsValue(Object value)
        System.out.println(hMap2.containsValue("나나나")); //true
        System.out.println(hMap2.containsValue("다다다")); //false

        //#8. Set<K> keySet()
        Set<Integer> keySet = hMap2.keySet();
        System.out.println(keySet.toString()); //[1, 2, 3]

        //#9. Set<Map.Entry<K,V>> entrySet()
        Set<Map.Entry<Integer, String>> entryset = hMap2.entrySet();
        System.out.println(entryset.toString()); //[1=나나나, 2=나다라, 3=다라마]

        //#10. size()
        System.out.println(hMap2.size()); //3

        //#11. remove(Object key)
        hMap2.remove(1);
        hMap2.remove(4); //동작안함
        System.out.println(hMap2.toString()); //{2=나다라, 3=다라마}

        //#12. remove(Object key, Object value)
        hMap2.remove(2, "나다라");
        hMap2.remove(3, "다다다"); //동작안함
        System.out.println(hMap2.toString()); //{3=다라마}

        //#13. clear()
        hMap2.clear();
        System.out.println(hMap2.toString()); //{}

    }
}

 

 

---

📌 Map의 중복확인 매커니즘

- Map의 중복확인 매커니즘은 Set과 동일하다.

 

#case 1) hashcode, equals 메서드 오버라이딩 X

- Object의 equals()은 ==와 동일한 연산 (저장 번지 비교)

class A {
    int data;
    public A(int data){
        this.data = data;
    }
}

public class HashMapMachanism {
    public static void main(String[] args) {

        //#1. equals, hashCode 오버라이딩 X
        Map<A, String> hmap1 = new HashMap<>();
        A a1 = new A(2);
        A a2 = new A(2);
        hmap1.put(a1, "바나나");
        hmap1.put(a2, "딸기");
        System.out.println(a1 == a2); //false
        System.out.println(a1.equals(a2)); //false
        System.out.println(a1.hashCode() + " " + a2.hashCode());
        System.out.println(hmap1.size()); //2
        
    }
}

 

 

#case 2) equals() 오버라이딩

- equals를 오버라이딩하여 값이 같으면, true를 반환하도록 설정

- 하지만 hashcode값이 다르기 때문에, 여전히 다른 객체로 판단

class B {
    int data;
    public B(int data){
        this.data = data;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof B){
            this.data = ((B)obj).data;
                return true;

        }
        return false;
    }
}

public class HashMapMachanism {
    public static void main(String[] args) {
        
        //#2. equals 오버라이딩
        Map<B, String> hmap2 = new HashMap<>();
        B b1 = new B(2);
        B b2 = new B(2);
        System.out.println(b1 == b2); //false
        System.out.println(b1.equals(b2)); //true
        System.out.println(b1.hashCode() + " " + b2.hashCode());
        hmap2.put(b1, "바나나");
        hmap2.put(b2, "딸기");
        System.out.println(hmap2.size()); //2

    }
}

 

 

#case 3) equals(), hashcode 오버라이딩

- equals(), hashcode를 매개변수 값이 같으면 각각 true, 같은 hash값을 반환하도록 설정.

- 같은 객체로 인식하여 Set 에 값이 하나만 들어간 것을 알 수 있음.

class C {
    int data;
    public C(int data){
        this.data = data;
    }

    @Override
    public boolean equals(Object obj) {
       if(obj instanceof C){
           this.data = ((C)obj).data;
           return true;
       }
       return false;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(data);
    }
}

public class HashMapMachanism {
    public static void main(String[] args) {

        //#3. equals, hashCode 오버라이딩
        Map<C, String> hmap3 = new HashMap<>();
        C c1 = new C(2);
        C c2 = new C(2);
        hmap3.put(c1, "바나나");
        hmap3.put(c2, "딸기");
        System.out.println(c1 == c2); //false
        System.out.println(c1.equals(c2)); //true
        System.out.println(c1.hashCode() + " " + c2.hashCode()); //2 2
        System.out.println(hmap3.size()); //1

    }
}

 

 

---

💡HashMap 구현

- HashMap을 다음과같이 구현하였다.

public class MyHashMap<K, V> {
    private class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
    }

    private static final int INITIAL_CAPACITY = 16;
    private static final double LOAD_FACTOR = 0.75;
    private LinkedList<Entry<K, V>>[] buckets;
    private int size = 0;

    public MyHashMap(){
        buckets = new LinkedList[INITIAL_CAPACITY];
    }

    private int hash(K key) {
        return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length);
    }

    public void put(K key, V value){
        int index = hash(key);

        if(size > buckets.length * LOAD_FACTOR) {
            resize();
        }

        if(buckets[index] == null){
            buckets[index] = new LinkedList<>();
        }
        for(Entry<K, V> entry : buckets[index]) {
            if(entry.key.equals(key)){
                entry.value = value;
                return;
            }
        }

        buckets[index].add(new Entry<>(key, value));
        size++;

    }

    public V get(K key) {
        int index = hash(key);
        if(buckets[index] == null) return null;
        for(Entry<K, V> entry : buckets[index]){
            if(entry.key.equals(key)){
                return entry.value;
            }
        }
        return null;
    }

    public boolean containsKey(K key) {
        int index = hash(key);
        if(buckets[index] == null) return false;
        for(Entry<K, V> entry : buckets[index]){
            if(entry.key.equals(key)){
                return true
            }
        }
        return false;
    }

    public void remove(K key) {
        int index = hash(key);
        if(buckets[index] == null) return;
        boolean removed = buckets[index].removeIf(entry -> entry.key.equals(key));
        if(removed) size--;
    }

    private void resize(){
        LinkedList<Entry<K, V>>[] oldBuckets = buckets;
        buckets = new LinkedList[oldBuckets.length * 2];
        size = 0;
        for(LinkedList<Entry<K, V>> bucket : oldBuckets){
            if(bucket != null){
                for(Entry<K, V> entry : bucket){
                    put(entry.key, entry.value);
                }
            }
        }
    }
}

 

 

필드, 메서드, 생성자

 

- Entry 클래스: HashMap의 각 요소를 나타내는 내부 클래스 (key, value 쌍)

- 해시 충돌을 방지하기 위해 LinkedList 사용

 private class Entry<K, V> {
    K key;   // 키
    V value; // 값

    // Entry 생성자
    Entry(K key, V value){
        this.key = key;
        this.value = value;
    }
}

private static final int INITIAL_CAPACITY = 16;   // 초기 버킷 크기 (16)
private static final double LOAD_FACTOR = 0.75;   // 로드 팩터 (버킷 크기가 75%를 초과하면 리사이즈)
private LinkedList<Entry<K, V>>[] buckets;  // 배열로 구현된 버킷(LinkedList 배열)
private int size = 0;  // 현재 저장된 요소의 개수

// MyHashMap 생성자, 초기 버킷 크기로 배열 생성
public MyHashMap(){
    buckets = new LinkedList[INITIAL_CAPACITY];
}

 

 

---

 

해시값 계산

 

- key의 해시 값을 계산하여 해당 인덱스를 반환

private int hash(K key) {
    return (key == null) ? 0 : Math.abs(key.hashCode() % buckets.length); 
    // null일 경우 0 반환, 그렇지 않으면 해시 코드의 절댓값을 버킷 크기로 나눈 나머지
}

 

 

---

 

key - value 쌍 저장 (put)

 

 public void put(K key, V value){
    int index = hash(key); // 해시 값을 통해 버킷 인덱스 계산

    // 요소가 로드 팩터를 초과하면 리사이즈
    if(size > buckets.length * LOAD_FACTOR) {
        resize();
    }

    // 해당 인덱스에 버킷이 없다면 새로 생성
    if(buckets[index] == null){
        buckets[index] = new LinkedList<>();
    }

    // 기존에 동일한 키가 있으면 값을 업데이트
    for(Entry<K, V> entry : buckets[index]) {
        if(entry.key.equals(key)){
            entry.value = value;
            return;
        }
    }

    // 새로운 키-값 쌍을 버킷에 추가
    buckets[index].add(new Entry<>(key, value));
    size++; // 크기 증가
}


// 해시 맵의 크기를 두 배로 늘리는 리사이즈 메서드
private void resize(){
LinkedList<Entry<K, V>>[] oldBuckets = buckets;  // 기존 버킷을 임시 저장
buckets = new LinkedList[oldBuckets.length * 2];  // 버킷 크기 두 배로 확장
size = 0; // 크기는 0으로 초기화 (put 메서드에서 다시 크기를 계산함)

// 기존 버킷에 저장된 모든 요소를 새 버킷에 다시 추가
for(LinkedList<Entry<K, V>> bucket : oldBuckets){
    if(bucket != null){
        for(Entry<K, V> entry : bucket){
            put(entry.key, entry.value); // 각 항목을 새 버킷에 저장
        }
    }
}

 

 

---

 

키에 해당하는 값 반환 (get)

 

public V get(K key) {
    int index = hash(key); // 해시 값을 통해 버킷 인덱스 계산
    if(buckets[index] == null) return null; // 해당 인덱스에 값이 없으면 null 반환
    for(Entry<K, V> entry : buckets[index]){
        if(entry.key.equals(key)){ // 해당 키를 찾으면 값 반환
            return entry.value;
        }
    }
    return null; // 키가 존재하지 않으면 null 반환
}

 

 

---

 

특정 키가 존재하는지 확인하는 메서드 (contains)

 

public boolean containsKey(K key) {
    int index = hash(key);
    if(buckets[index] == null) return false;
    for(Entry<K, V> entry : buckets[index]){
        if(entry.key.equals(key)){
            return true;
        }
    }
    return false;
}

 

 

---

 

특정 키를 가진 요소 제거 (remove)

 

 public void remove(K key) {
    int index = hash(key); 
    if(buckets[index] == null) return; 
    // removeIf로 해당 키를 가진 요소를 찾아 삭제
    boolean removed = buckets[index].removeIf(entry -> entry.key.equals(key));
    if(removed) size--;
}