[Java] 컬렉션 개념(HashMap)

개념

맵이란 것은 키(Key) 와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조. (키는 맵에 오직 유일하게 있어야함 ,값은 중복 상관 X). 키와 값을 매핑하기 위해 해시라는 것을 사용한다.  한편,HashMap은 HashTable과 달리 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다. (해시 테이블과의 비교는 사실 의미 없음)

 

특징

java 8 HashMap에서는 Entry클래스 대신 Node 클래스를 사용한다. 링크드 리스트 대신 트리를 사용할 수 있도록 하위 클래스인 TreeNode가 있다는 점에서 java 7 HashMap과 다르다. 이 때 사용되는 트리는 Red-Black Tree이다. 

 

 

해시와 해시 함수

해시는 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값이다. 이를 매핑하기 위해 있는 것이 해시 함수이다. 

예를들어 {"ABC","1"}, {"DEF","2"}, {"GHI","3"}, {"123","4"} 라는 값이 해시 맵에 들어간다고 하면 아래와 같이 저장된다.

각각 hash에 매핑되어 value가 들어가게 되고, 만약 같은 hash값을 가진다면 링크드 리스트 형태로 저장되게 된다. 

 

Q) 1대1 대응으로 O(1)의 시간복잡도를 하면되지 왜 링크드 리스트 형태로 저장되나요?

해시는 O(1)을 보장하기 위함이지만, 이는 완전한 자료 해시 함수일 때만 가능하다.(각각 모두 달라야함) 자바의 HashMap에서는 hashCode() 결과 자료형이 int 32비트 정수 자료형이다. 32비트 정수 자료형으로는 완전한 자료형을 만들 수 없다.( 객체가 2^32보다 많다면 1대1 매핑 할 수 없음). 또한 32비트만이라고 하더라도, O(1)을 보장하려면 모든 해시맵이 2^32인 배열을 가지고 있어야하는데, 이렇게 되면 메모리를 많이 사용하게 된다. 따라서 객체에 대한 해시코드의 나머지 값을 버킷의 인덱스로 사용한다.

 

 이렇게 되면 서로 다른 해시 코드를 가지는 서로 다른 객체가 같은 해시 버킷을 사용하게 될 확률은 1/M가 된다. 이렇게 겹치게 되는 상황을 링크드 리스트를 통해 해결하게 되는 것이다. 이를 Separate Chaining이라고 한다. (위의 1 -> 4)

 

Q) 객체의 해시 함수 값이 균등 분포상태라고 할 때, get으로 값을 꺼낼 때 기대되는 시간 복잡도는?

N = 12, M = 3인경우 링크드리스트를 4번 탐색해야한다.

해시맵(HashMap) 클래스의 대표적인 메소드는 다음과 같습니다.

put(Object key, Object value): 지정된 키와 값을 해시맵에 추가합니다.
get(Object key): 지정된 키에 해당하는 값을 반환합니다. 해당 키가 없으면 null을 반환합니다.
remove(Object key): 지정된 키에 해당하는 값을 제거합니다. 해당 키가 없으면 아무 일도 하지 않습니다.
containsKey(Object key): 지정된 키가 해시맵에 존재하는지 여부를 반환합니다.
containsValue(Object value): 지정된 값이 해시맵에 존재하는지 여부를 반환합니다.
size(): 해시맵에 저장된 데이터의 개수를 반환합니다.
isEmpty(): 해시맵이 비어 있는지 여부를 반환합니다.
clear(): 해시맵에 저장된 모든 데이터를 제거합니다.
keySet(): 해시맵의 모든 키를 포함하는 Set 객체를 반환합니다.
values(): 해시맵의 모든 값들을 포함하는 Collection 객체를 반환합니다.
entrySet(): 해시맵의 모든 엔트리(키-값 쌍)를 포함하는 Set 객체를 반환합니다.

public class Main {
    public static void main(String[] args) {
				Map<Integer, String> map = new HashMap<>();
        map.put(1, "apple");
        map.put(2, "berry");
        map.put(3, "cherry");

        System.out.println(map);

        System.out.println("1st in map: " + map.get(1));

        map.remove(2);
        System.out.println(map);
        System.out.println(map.containsKey(2));
        System.out.println(map.containsValue("cherry"));
        
        map.clear();
        System.out.println(map);
    }
}