Map 자료구조의 특징

중복을 허용하지 않는 Key 값과 그에 대응하는 중복이 허용되는 Value 값이 쌍을 이루어 저장되는 자료구조.

중복: Key 값은 중복 불가능, Value값은 중복 가능
순서: 순서 보장X
정렬: 불가능

주요 메소드

• put(Object key, Object value): 데이터 추가
• get(Object Key): 전달된 키에 대응하는 값을 반환. 없다면 boolean이 아닌 null을 반환한다.
• remove(Object key): 데이터 삭제
• remove(Object key, Object value): 데이터 삭제(없다면 false 반환)
• replace(Object key, Object value): 키에 대응하는 값을 대체
• clear(): 데이터 모두 삭제
• size(): 크기
• containsKey(Object key): Key값이 있는지 여부(boolean)
• containsValue(Object value): Value값이 있는지 여부(boolean)
• isEmpty(): map 비어있는지 확인
• Set < Object key >keySet() : 모든 키로 만들어진 Set 객체를 반환

HashMap<K, V>

해시 알고리즘을 사용하여 검색 속도가 매우 빠르다. Thread-safe하지 않다. key에 null을 허용한다. 보조 해시를 사용하기 때문에 안전하다.Collections.synchronizedMap(hashMap) 등을 이용하여 동기화 처리 후 사용하자. 또한 MultiThread 환경에서는 ConcurrentHashMap을 고려하자.

• 검색 속도 빠름
• Thread-safe하지 않음
• null을 허용

시간 복잡도

add : O(1)
contains : O(1)
next : o(h/n) h는 테이블 용량

---

HashTable<K, V>

HashMap 클래스와 같은 동작을 한다. Thread-safe 하지만, null을 허용하지 않고, 보조 해시 함수를 사용하지 않아 충돌이 발생할 수도 있다.

• Thread-safe
• null을 허용X

시간 복잡도

add : O(1)
contains : O(1)
next : o(h/n) h는 테이블 용량

---

TreeMap

Key 값이 중복되지 않는다는 점은 다른 Map 클래스와 동일하지만, 데이터의 Key값을 기준으로 정렬된다는 점이 특징- 삽입과 동시에 정렬되는 상태를 유지함. 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현되어 있다.

시간 복잡도

add : O(log n)
contains : O(log n)
next : o(log n)

---

LinkedHashMap

저장순서를 유지하고 관리하는 HashMap이다. 하지만 인덱스로 접근할 수 없어 데이터에 하나하나 접근하기 위해서는 entrySet() 메소드를 활용해 객체를 생성해야 한다. null을 허용하지만, 동기화 처리가 되어있지 않기 때문에 multi-thread 환경에서 사용은 적절하지 않다.

• Thread-safe하지 않음
• null 허용
  예시코드

import java.util.Iterator;
import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
	public static void main(String[] args)  {
		LinkedHashSet<String> str = new LinkedHashSet<String>(); // LinkedHashSet 선언
		
		// 값 추가
		str.add("Hello1");
		str.add("World2");
		str.add("Hello3");
		str.add("World4");
		
		/* Iterator를 사용 HashSet 배열 출력 */
		Iterator iter = str.iterator();
		while(iter.hasNext())
			System.out.print(iter.next() + " ");
	}
}

시간 복잡도

add : O(1)
contains : O(1)
next : o(1)