Map 인터페이스
Key, Value 형식으로 데이터를 저장하는 자료형이다.
Map 인터페이스는 기본적으로 Key값의 Hashcode를 이용하여 데이터의 존재 여부 혹은 삽입 삭제 등의 연산의 위치(=bucket)를 판단하며, 동일한 Hashcode를 갖는다면 Key의 eqauls 메소드를 통하여 연산을 진행한다.
HashMap
HashMap은 다음과 같이 Node단위로 데이터를 저장한다. 해당 노드는 hashcode, key, value, next 변수를 가지고 있다.
HashMap의 연산들은 삽입할때는 다음과 같이 put 과정 및 조건에 따라 resize하는 과정이 추가된다.
추가로, 내부의 Node배열을 유지해 해당 값에 인덱스 & Hashcode연산을 통해 직접접근 하므로, O(1)시간 내에 해당 객체를 조회할 수 있다.
HashMap 삽입과정은 다음과 같다.
- 노드 혹은 HashMap의 사이즈가 0라면, 노드를 Resizng한다.
- 이 후, Hashcode연산을 통해 넣고자하는 Hashcode키에 저장된 데이터가 없다면, 새로운 노드를 생성하고, 해당 노드에 저장한다.
3 만일, 같은 키에 Hashcode연산 값이 동일한 데이터가 저장되어 있었다면, 새로운 노드를 만들어 기존 값을 대체하고 기존에 있던 값을 반환한다.
HashMap은 삽입, 삭제, 조회 등의 연산 시 Hashcode연산을 통해 해당 값에 접근하고, 연산을 한다. 이때, Key를 통해 데이터를 접근하는데, 해당 Key의 == 연산을 통해 우선적으로 접근하고, == 연산이 실패하면, equals 연산의 결과를 통해 데이터에 접근한다.
HashMap은 null 키 값을 허용한다. null은 Hashcode를 제공할 수 없으므로, HashMap의 키 값으로 null이 들어오면 0번 인덱스의 버킷에 삽입한다.
TreeMap
TreeMap은 Balanced Binaray Tree인 Red-Black Tree를 이용하여, 데이터를 저장할 때, 키 값을 기준으로 정렬하여 저장한다. 이 때, Comparable 인터페이스를 구현하여 전달해, 정렬 순서를 커스텀할 수 있다.
TreeMap은 데이터에 접근할 때, 트리를 순회하며 접근하므로 O(log N)의 시간 복잡도를 갖는다.
TreeMap은 Comparable 인터페이스에서 null 키 여부를 적절히 처리 할 수 있다면, null 키 값을 저장할 수 있다.
LinkedHashMap
LinkedHashMap은 삽입된 순서를 유지하여 저장되며 HashMap과의 다른 점으로는 노드가 순서상 이전의 객체와 다음의 객체에 대한 참조를 추가적으로 저장하여 HashMap보다 추가의 메모리를 사용한다.
LinkedHashMap도 HashMap과 같이 내부의 Node배열을 유지해 O(1)시간 내에 해당 객체를 조회할 수 있다.
LinkedHashMap은 HashMap과 마찬가지로 null 키 값을 가질 수 있습니다.
참고.
https://stackoverflow.com/questions/24522051/why-is-equals-method-not-called-in-the-hashmap
https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC#%EC%B2%AB_%EB%B2%88%EC%A7%B8_%EA%B2%BD%EC%9A%B0
https://stackoverflow.com/questions/25932730/hashmap-with-null-key-and-null-value
