[java] HashMap 과 TreeMap

맵(Map) 은 키(key) 와 값(value)을 함께 저장한다.

독특한 저장구조 때문에  리스트와 셋과 달리 Colection 인터페이스를 상속받지 않는다. 

 그래서 iterator를 사용하려면 entrySet( ) 메서드를 통해 set으로 변환하여야 한다.

 

 

<HashMap>

 

키(key)값의 '해싱'을 통해 값(value)의 저장주소를 생성한다.

'해싱'이란 해시함수를 통해  데이터를 해시테이블에 저장하는 기법을 말한다.

해시함수를 통해 값의 저장위치를 알 수 있으므로 검색속도가 빠르다.

 

키 값은 값의 저장위치를 구하는데 쓰이므로, 중복값을 허용하지 않는다.

 

반면 값은 키가 다르다면 저장위치가 달라지므로, 중복된 값이라도 상관없다.

 

해시맵은 배열과 링크드리스트를 합쳐서 구현한다. 해싱함수를 통해 배열의 주소값을 찾고,

배열의 주소로부터 연결된 링크드리스트에 키(key)와 값(value)를 저장하는 방식으로 구현한다.

 

해싱을 사용하는 클래스들은 equals( )와 hashCode( )를 통해 객체의 동일성을 판단한다.

1. equals( ) 가 true 라면 , hashCode( ) 역시  반드시 true가 나와야 한다.

2. hashCode( ) 가 같다면 , 프로그램 실행중에는 언제든 같은 값이 나와야 한다.

3. hash 값은 반드시 달라야 하는건 아니지만 검색속도를 위해서 다른것이 권장된다.

배열과 링크드 리스트를 결합하여 값을 저장한다.

 

<TreeMap>

앞에서 살펴본 TreeSet 처럼 이진 검색 트리를 사용하여 Map 방식으로 키와 값을 저장한다.

일반적으로 HashMap보다 검색속도는 느리지만, 범위검색과 정렬이 빠르다.