Java Collection - Map

아마 가장 많이 사용하는 Map은 HashMap일 것이다.

HashMap의 구조에 대해서 살펴보자

 

HashMap key값에서 value를 찾을 수 있는 O(1) 형태의 데이터 구조이다.

Java의 모든 객체는 hashCode()와 equals() 메소드를 가지고 있다.

Node<K,List<V>>[] table;

public V get(Object key) {
	int index = object.hashCode() % 16;
	List<V> list = table[index];
    for(int i = 0; i < list.size(); i++) {
      if(list.get(i).equals(key))
      	return list.get(i);
    }
    return null;
}
// 설명을 위해 단순화된 예시, 실제로는 훨씬 복잡하다.

 

객체의 hashCode()를 통해 index의 위치를 탐색하기 때문에 O(1) 형태의 구조를 가지지만 hash충돌이 많을 경우 O(n)의 구조를 가져갈 수 있으니 hashCode(), equals()를 재구현해야할 경우 주의가 필요하다.

 

또한 위에서는 List로 설명하였는데, jdk 1.8부터는 Tree구조를 가져가고 있으니 hash 충돌에도 더 빠른 탐색(O(log n))이 가능하다.(초기에는 List로 저장하다가 충돌이 많아지면 Tree로 변환해서 저장한다.)

 

그 외에도

키 순서가 정렬되어있는 TreeMap

입력 순서(or 접근 순서)가 보장되는 LinkedHashMap

동시성이 보장되는 ConcurrentHashMap

키 값이 enum인 경우 최적화 되어있는 EnumMap

와 같이 다양한 Map 종류를 jdk에서 제공하고 있다.