찰떡개발자 코딩

너무 기본적인 것들에 대해 정리가 되어있지 않아 초심으로 돌아가보려고 한다.

왜 사용하는지 다시한번 머리 속에 담아두자..!

Map은 Collection Interface를 상속받고 있지않지만 편의상 Collection으로 분류한다고 한다.

Map

• 정의 : 키(Key) , 값(Value) 을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스들을 구현하는 데 사용 되는 인터페이스
• 특징 :
  1. 요소의 저장 순서가 별도로 존재하지 않는다.
  2. Key : 중복 허용하지 않음
  3. Value : 중복 허용

1). HashMap

특징 :

• 내부적으로  Entry<K,V>[] Entry의 배열로 이루어 져있다. 해당 Array에 Index는 내부 해쉬 함수를 통해 계산된다.
• 내부 Hash값에 따라서 키 순서가 정해지므로 순서의 규칙이 없다.
• 그래서 .get() 메서드는 Hash 값으로 직접 해당 Array에 바로 접근이 가능하기 때문에 성능은O(1)으로 빠르다.

2). TreeMap

특징 :

• 키값이 알파벳 순서대로 정렬된다
• 키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree)의 형태로 저장한다.
• 이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠르다.
• 하지만 위와같은 Tree 구조를 갖기 때문에 특정 Entry에 접근하려면 O(logn)의 성능을 가진다.
• 기본적으로 Key기준으로 정렬이 되어있는데, Comparator를 사용하여 정렬 순서를 변경할 수 있다.

3). LinkedHashMap

특징 :

• 흐름은 HashMap과 동일하지만, LinkedList와 같이 필요 노드에 대한 정보를 보유하고있다.
• Entry내에는 이전, 다음 Entry에 대한 정보를 가지고있기 때문에 순서를 보장할 수 있게 된다.
• 입력된 순서를 보장하고 싶을때 사용할 수는 있지만, 링크드리스트와 같이 랜덤 접근에 대해서는 O(n) 성능을 지니므로, 대량의 데이터에는 사용하지 않는것이 좋다.

<결론>

결국 필요시에는 골라서 사용하긴 하지만 성능적으로 보면 HashMap을 가장 많이 쓰는 이유를 알수있었다.

• 특별한 이유가 없다면 검색 성능이 좋은(O(1)) HashMap 을 사용
• 키값이 일정한 수준대로 iterate 하려고 한다면 TreeMap 을 사용. 하지만 랜덤 접근에 대해서는 O(logn) 성능을 지니므로 많은 데이터를 넣을경우 좋지 않은 성능이 나올수 있다.
• 입력 순서가 의미있다면 LinkedHashMap 을 사용. 랜덤 접근에 대해 O(n) 성능을 지니므로 많은 데이터를 입력할 경우 지양한다.

Map을 생성하는데에는 LinkedList가 HashMap보다 더 느리다는 말이 있었는데, 한 블로그를 보니 오히려 LinkedList가 더 빠른 결과를 보여줬다. 결국 생성시에는 두개의 속도 차이는 거의 없다!

정리 : 

HashMap은 HashCode를 기준으로 입력이 되기 때문에, 정렬의 순서가 보장되지 않는다. 하지만 hash함수를 사용하기 때문에 탐색시간은 O(1)의 속도로 가장 빠르다.

TreeMap은 Key값이 알파벳 순서대로 정렬된다. 이진 검색 트리의 형태로 저장되어, 탐색 시간은 O(logN)의 성능을 가지게 되지만 추가 삭제의 속도가 빠르다. Key기준으로 정렬되기 때문에 Comparator를 사용하여 정렬 기준을 바꿀수 있다.

LinkedHashMap의 가장 큰 특징은 LinkedList와 같이 이전, 다음 노드의 필요정보를 Entry에 저장하여, 입력된 순서를 보장받는다. 랜덤 접근에서는 O(n)의 성능을 가지므로 대량의 데이터에는 적합하지 않다.