Collections Framework (6) HashMap, TreeMap

HashMap

- Map을 구현한 클래스로, 키와 값을 묶어 하나의 데이터(entry)로 저장한다.
- 해싱을 이용해 많은 양의 데이터를 검색하는 데 있어 뛰어나다.

 

Hashing & Hash Function

[해싱] : 해시 함수를 이용해 데이터를 해시테이블에 저장하고 검색하는 기법이다.
[해시 함수] : 데이터가 저장되어 있는 위치를 알려준다.

해싱을 사용하는 자료구조는 배열과 LinkedList의 조합으로 이루어져 있다. 데이터를 저장하는 과정은 다음과 같다.
1. 저장할 데이터의 키를 해시 함수에 넣으면 배열의 한 요소를 얻게 된다.
2. 해당 요소에 연결되어 있는 LinkedList에 데이터를 저장한다.

데이터를 검색하는 과정은 다음과 같다.
1. 검색하고자 하는 value의 key로 해시 함수를 호출한다.
2. 해시 함수의 결과인 해시코드를 통해 해당 값이 저장되어 있는 LinkedList를 찾는다.
3. LinkedList에서 검색한 키와 일치하는 데이터를 찾는다.

LinkedList는 데이터 접근성이 상대적으로 떨어지기 때문에 데이터의 양이 많아지면 검색 속도가 떨어지게 된다. 반면, 배열은 크기가 커지더라도 위치만 알면 빠르게 접근할 수 있다. 그렇기 때문에, 해시테이블의 인덱스마다 하나의 데이터만 저장되어 있으면 더 빠른 검색을 진행할 수 있다. 이렇게 하기 위해서는 하나의 LinkedList에 최소한의 데이터만 저장해야 하며, 저장될 데이터의 크기에 맞게 HashMap의 크기를 적절하게 지정해야 한다. 즉, 해시 함수를 통해 반환되는 해시코드의 중복을 최소화해야 한다!

HashMap은 HashSet과 동일하게 다른 두 객체에 대해 equals()의 결과 값이 true인 동시에 hashCode()의 반환값이 동일해야 같은 객체로 인식한다. 그렇기 때문에, 사용자 정의 클래스를 정의하는 경우 equals()의 결과 값이 true인 두 객체의 hashCode()의 결과 값이 동일하도록 해줘야 하는 것이다.

 

TreeMap

- 이진 탐색 트리의 형태로 (key, value)의 형태로 데이터를 저장한다.
- 검색과 정렬에 적합한 컬렉션이다.
- 검색에 있어서는 HashMap이 더 뛰어난 성능을 보여주지만, 범위검색이나 정렬에 있어서는 TreeMap이 더 뛰어나다.

 

참고: Java의 정석 (남궁 성 지음)