[Java Collection Framework] HashMap, HashTable, Map

1. 해싱이란?

- (알고리즘) 해시 함수는 데이터를 고정된 크기의 해시값, 코드로 변환한다. 

- (자료구조) 해시 함수를 활용해 데이터를 저장하고 빠르게 검색한다. (상수시간)

- 해시충돌 : 다른 입력값이 동일한 해시값을 가지는 것을 의미한다. 

- 해시충돌 방지 (개방 주소법) : 충돌이 발생하는 경우 다른 버킷에 데이터를 저장한다.

- 해시충돌 방지 (체이닝) : 각 버킷이 연결리스트의 헤더를 가지고 충돌이 발생하면 다음 연결 리스트에 데이터를 저장한다.

 

2. Java HashMap 

- Key:Value 쌍을 구조로 데이터를 저장 및 조회하는 자료구조

- Key:Value 쌍의 개수에 따라 동적으로 크기가 증가하는 Associate Array 

- 해시 충돌 방지를 위해 체이닝 기법을 사용한다. 

- 기본 버킷 개수는 16이며 해시 충돌이 발생할 때마다 2배씩 증가하여 최대 2^30까지 버킷 갯수를 가질 수 있다. 

- 자바8에서는 버킷에 8개 이상의 데이터가 저장되면 트리로 변경되고, 6개 이하인 경우 다시 연결 리스트로 변경된다. 

 

3. HashMap vs HashTable

- JCF(Java Collection Framework)에는 HashMap과 거의 동일한 기능을 제공하는 HashTable이 있다. 

- HashTable은 Thread-safe 하여 안전한 대신 속도가 느리다.

- HashMap은 안전하지 않은 대신 속도가 빠르다. 

 

 

4. 사용법

메소드	내용
put(K key, V value)	key에 대한 value 값을 맵핑 합니다.
putIfAbsent(K key, V value)	해당 key가 없는 경우 value 값을 맵핑합니다.
putAll( @NotNull  Map<? extends K, ? extends V> m )	다른 맵으로부터 키-값 쌍을 전부 전달받아 합칩니다.
ketSet()	모든 키 값을 Set 자료형으로 반환 받아 순회 시 사용합니다.
forEach( java.util.function.BiConsumer<? super K, ? super V> action )	순차적으로 action을 수행합니다. 각 순회마다 맵의 Key, Value 쌍인 entry를 가져오며 entrySet()과 유사한 기능을 수행합니다.
@Override  public int hashCode() { ,,, }	Object 클래스의 hashCode 메소드를 재정의합니다. 해시맵에서 객체를 키 값으로 사용하는 경우 해당 객체의 동일성을 재정의한 equals()로 판별하기에 앞서 hashCode()를 확인합니다. 따라서 해시맵에 객체키를 사용하는 경우 hashCode()와 equals() 메소드 모두 재정의가 필요합니다.

 

import java.util.Map;
import java.util.HashMap;

public class ch14_HashMap {
    public static void main(String[] args) {
        Map<String, Integer> hm = new HashMap<>();
        hm.put("A", 100);
        hm.put("B", 101);
        hm.put("C", 102);
        hm.put("C", 103); // 1. 이미 값이 있는 경우 값을 덮습니다.
        if(!hm.containsKey("D")){
            hm.put("D", 104); // 2. 값의 여부를 확인해 덮어쓰기를 방지합니다.
        }
        hm.putIfAbsent("D", 105);

        System.out.println(hm);
        System.out.println(hm.get("A"));
        System.out.println(hm.get("B"));
        System.out.println(hm.get("C"));
        System.out.println(hm.get("D"));


        System.out.println("========================================");


        Map<String, Integer> hm2 = new HashMap<>();
        hm2.put("key1", 1);
        hm2.put("key2", 2);
        hm2.putAll(hm); // 3. hm2 에 hm 의 모든 쌍을 추가해 합침.
        System.out.println(hm2);

        for(String key : hm2.keySet()){ // 4. keySet() 메소드를 이용해 Map에 있는 모든 키를 순회할 수 있다.
            System.out.println("(keySet) " + key + ":" + hm2.get(key));
        }
        hm2.forEach((key, value) -> { // 5. forEach() 메소드와 람다식을 활용해 모든 키, 값을 순회할 수 있습니다.
            System.out.println("(forEach) " + key + " : " + value);
        });


        System.out.println("========================================");


        // 객체키 : equals() 메소드 오버라이딩
        Person p1 = new Person("1", "111111-1111111");
        Person p2 = new Person("2", "222222-2222222");
        Person who = new Person("1", "111111-1111111");

        Map<Person, Integer> hm3 = new HashMap<>();
        hm3.put(p1, 0);
        hm3.put(p2, 1);

        System.out.println("Does map include " + who.getName() + "? => " + hm3.containsKey(who));

        hm3.put(who, 3);
        System.out.println(hm3);

    }
}

class Person{
    private String name;
    private String id;
    public Person(String name, String id){
        this.name = name;
        this.id = id;
    }
    public String getName() {
        return this.name;
    }

    @Override
    public String toString(){
        return this.name;
    }

    @Override
    public boolean equals(Object o){ // Object 클래스는 최상위 객체이다.
        if(o instanceof Person){ // 동일한 Person 객체이며
            Person p = (Person) o; // Person 으로 형변환
            return this.id.equals(p.id) && this.name.equals(p.name); // 필드값이 같은 경우 동일한 객체로 간주한다.
        }
        return false; // 다른 클래스인 경우 false를 반환.
    } // => equals 오버라이딩으로 같은 객체임을 명시함에도 불구하고 해시맵에서 인식하지 못한다. => 어떻게 해야할까?

    // HashMap은 hashCode()를 비교하고 같은 경우 equals()를 수행한다.
    @Override
    public int hashCode(){
        return name.hashCode() + id.hashCode(); // id와 name으로 해시코드를 만들어 주어 id와 name이 동일한 경우 같은 해시 값을 반환하도록 한다.
    } // 따라서 반드시 같은 객체를 판단하는 equals를 재정의할 때 함께 hashCode도 재정의 해주어야 합니다.
}

 

 

5. 추가 

- 왜 Map 인터페이스를 선언하고 HashMap을 생성하는가?

=> 객체지향 설계 원칙에 따라 Map 인터페이스로 생성할 때에 다음과 같은 이점이 있습니다. 

다형성 : Map 인터페이스 변수를 사용함으로서 필요에 따라 다른 구현체들을 쉽게 사용할 수 있습니다. 예를 들어, 코드를 나중에 수정할 때, LinkedHashMap, TreeMap, HashMap, HashTable 등으로 기존 코드를 수정하지 않고도 교체할 수 있습니다.

유연성 : 인터페이스를 사용하는 것은 구현체와의 결합도를 낮추어 유지보수와 확장성을 높입니다.

테스트 용이성 : Map 인터페이스를 사용하면 단위 테스트 시 Mock 개겣를 사용하는 것이 더 쉬워집니다. 예를들어, Map 인터페이스를 사용하면 HashMap 대신 테스트를 위한 MockMap을 사용할 수 있습니다. 

 

따라서 인터페이스 Map을 활용해 HashMap을 생성하는 것이 다형성, 유연성을 활용하는 좋은 프로그래밍 습관입니다.