레드블랙트리 vs 해쉬테이블 (TreeMap vs HashMap)

C++ 의 map 은 레드블랙트리로 구현되있으며, java 의 treeMap 또한 레드블랙트리로 구현되어있습니다.

C++ 진영에서 해쉬테이블이 표준으로 구현되지 않았었기때문에,  많은 경우 해쉬를 굳이 외부라이브러리등

을 통하거나,만들어서 사용하지 않았는데, 그 의미는 많은 경우에 있어서 레드블랙트리로 맵을 사용하는게 충

분하다는 방증(circumstantial evidence) 이겠지요. Java 진영에서는 많은 경우 HashMap 을 사용하더군요.  

이런걸 보면 , 두개 알고리즘의 각각의 특징에 따라서 맵을 사용한다기보다는 , 대개의 프로그래머들은 그냥 

아무 생각없이 많이 쓰여 지는것을 쓴다고 볼수있습니다. 이 얘기는 프로그래머들이 게을러서라고 생각치 않

습니다. 많은 경우 두개의 알고리즘의 성능차이는 80대20법칙에서 중요치 않은 쪽에 속한다고 볼수있겠지

요. 어플리케이션 성능 체크를 해볼때, 병목이 일어나는 곳은 다른곳에 있었을 테니깐요.

그래도 우리는 소프트웨어 개발자이기때문에, 가끔 먼가 꺼림칙하기도 합니다. 따라서 여기에 

레드블랙트리의 장점을 간략히 기술해보면 

레드블랙트리의 장점 (해쉬에 비해)

- 순서가 있는 자료일 경우.  (해쉬는 순서가 없습니다) 

- 일관성있는 퍼먼스를 보여줍니다. (해쉬는 rehashing 될때 비정상적인 시간이걸릴수있음)

- 해쉬는 페이지폴트를 일으킬수있다. (페이지간 전환이 많아지면 느려지겠지요) 

- 연속된 삽입간에 지역성을 유지하기 쉽다. 더 적은 I/O 가 발생한다.( 해쉬테이블은 효율적인        lookup 을 위해 버켓안의 모든 요소를 스왑할수있다)

- 해쉬는 테이블 리사이징 이슈 : 갑자기 성능이 다운됨.

- 해쉬는 메모리 낭비가 있을수있다.( 이건 해쉬의 구현이 어떻게 되있냐에 따라 다름)

- 트리는 부정확한 검색에 사용될수있다.( "a" 로시작되는 모든것, 범위검색) 

자바를 사용해 개발한다면, 대부분의 경우 순서가 필요하면 TreeMap , 아니면 HashMap 을 쓰는게 좋다고 

생각합니다. Hash 가 java 7 에서 또 한번 큰 발전이 있었으며,(http://d2.naver.com/helloworld/831311) 

큰 차이가 없다면 가독성이라도 도움이 되니깐요. 아 이건 순서를 중요시했구나, 순서가 필요없구나~ 

물론 많은 데이터를 관리해야할 필요가 있을때는, 벤치마크가 필요하겠지요. 

---

I'll talk about the HashMap and TreeMap implementation in Java:

• HashMap -- implement basic map interface

  1. implemented by an array of buckets, each bucket is a LinkedList of entries
  2. running time of basic operations: put(), average O(1), worst case O(n), happens when the table is resized; get(), remove(), average O(1)
  3. not synchronized, to synchronize it: Map m = Collections.synchronizedMap(new HashMap(...));
  4. Iteration order of the map is unpredictable.

• TreeMap -- implement navigable map interface

  1. implemented by a red-black tree
  2. running time of basic operations: put(), get(), remove(), worst case O(lgn)
  3. not synchronized, to synchronize it: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  4. provide ordered iteration. higherKey(), lowerKey() can be used to get the successor and predecessor of a given key.

To sum, the biggest difference between HashMap and TreeMap is that TreeMap implements NavigableMap<K,V>, which provide the feature of ordered iteration. Besides, both HashMap and TreeMap are members of Java Collection framework. You can investigate the source code of Javato know more about their implementations.