[Java] - Map / TreeMap / LinkedHashMap

janjanee·2021년 7월 29일

java linkedhashmap java map java treemap map vs treemap vs linkedhashmap

Java

목록 보기

16/19

HashMap

Map의 특징인 키(Key)와 값(Value) 를 이용하여 하나의 데이터(entry) 로 저장한다.
해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색할 때 성능이 좋다. -> O(1)

키(key) 컬렉션 내의 키(key)중에서 유일
값(value) 키(key)와 달리 데이터 중복을 허용

아래는 Map을 사용한 예제이다.

코드

Map<String, Integer> map = new HashMap<>();

map.put("춘식이", 100);
map.put("라이언", 80);
map.put("짱구", 60);
map.put("호빵맨", 77);

Set<Map.Entry<String, Integer>> set = map.entrySet();

for (Map.Entry<String, Integer> entry : set) {
    System.out.println("이름: " + entry.getKey() + ", 점수: " + entry.getValue());
}

Set<String> keySet = map.keySet();
System.out.println("이름 목록: " + keySet);

Collection<Integer> values = map.values();

System.out.println("최댓값: " + Collections.max(values));
System.out.println("최솟값 : " + Collections.min(values));

결과

이름: 호빵맨, 점수: 77
이름: 짱구, 점수: 60
이름: 춘식이, 점수: 100
이름: 라이언, 점수: 80
이름 목록: [호빵맨, 짱구, 춘식이, 라이언]
최댓값: 100
최솟값 : 60

entrySet() : HashMap에 저장된 키와 값을 엔트리의 형태로 Set에 저장해서 반환
keySet() : HashMap에 저장된 모든 키가 저장된 Set을 반환
values() : HashMap에 저장된 모든 값을 컬렉션의 형태로 반환

해싱과 해시함수

해싱?
해시함수(hash function)을 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.

자바에서 해싱을 구현한 컬렉션 클래스는 HashSet, HashMap 등이 있다.
해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘 이다.

해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다.
Object 클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들기 때문에
모든 객체에 대해 hashCode()를 호출한 결과가 유일하다.

String 클래스는 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 생성한다.
그래서 서로 다른 String 인스턴스일지라도 같은 내용의 문자열이라면 hashCode() 호출 시 같은 해시코드를 얻는다.

서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다.
따라서 새로운 클래스를 정의할 때 equals()를 오버라이딩 해야 한다면, hashCode()도 같이 오버라이딩해서
equals() 결과가 true인 두 객체의 hashCode() 결과도 같에 만들어야 한다.

그렇지 않으면, HashMap과 같이 해싱을 구현한 컬렉션 클래스에서 equals() 를 호출한 결과가 같은 객체일지라도
서로 다른 해시코드를 가지고 있으면 서로 다른 것으로 인식하고 다른 위치에 저장이된다.

HashMap vs TreeMap vs LinkedHashMap

TreeMap

이진 검색 트리(binary search tree) 라는 자료구조의 형태로 데이터를 저장
이진 검색 트리의 성능을 향상시킨 'Red Black tree' 로 구현
compareTo() 메서드 또는 외부에서 제공되는 Comparator에 따라 키의 순서에 따라 정렬.
add(), remove(), contains() 호출 시 O(log n) 성능을 제공

LinkedHashMap

삽입 순서를 유지한다.
Map 인터페이스를 구현한 클래스이며 double-linked buckets(이중 연결 버킷) 으로 구현
HashMap과 마찬가지로 get(), put(), contains() 호출 시 O(1) 성능

HashMap

자바 8 이전에 Separate Chaining 방식으로 해시 충돌을 해결
- HashMap에서 요소를 검색할 때 최악의 경우 연결 리스트에서 요소를 검색하는 것만큼 시간이 소요
- 즉, O(n) 시간복잡도를 가짐
자바 8 이후부터 데이터 개수가 많아지면 Separate Chaining 에서 LinkedList 대신 TreeNode를 사용
- 해시 충돌이 높은 경우 최악의 경우 성능이 O(n) -> O(log n) 으로 향상
- 해시 버킷에 8개의 데이터가 모이면 트리로 변경
  - 버킷에 데이터가 6개가 되면 다시 링크드 리스트로 변경
  - 7이 아니라 6인 이유는?
    - 차이가 1일 경우 키-값 쌍이 반복되어 삽입/삭제 되는 경우 불필요한 데이터 변경이 발생하여 성능저하
즉 대부분의 일정한 시간복잡도는 O(1) 이지만, 해시 충돌이 높은 경우 최악의 성능은 O(log n) 이다.