HashMap과 TreeMap에 대해

 Map

- 순서가 없고 키는 중복을 허용하지 않으나, 값은 중복을 허용한다.

- 데이터를 키와 값의 쌍으로 저장한다.

- Map을 구현한 컬렉션 클래스 : Hashtable, HashMap, LinkedHashMap, TreeMap

HashMap

- Map인터페이스를 구현한 대표적인 컬렉션 클래스

- HashMap(동기화되어있지 않음)은 Hashtable(동기화되어있음)의 신버전이다.

- 저장 순서를 유지하고 싶으면 LinkedHashMap 클래스를 사용하면 된다.

- 해싱(hashing)기법을 이용해 데이터를 저장하여 데이터가 많아도 검색이 빠르다는 장점이 있다.

- 같은 키로 값을 저장하게 되면 나중에 저장된 값이 이전 값을 덮어씌운다.

- HashMap은 HashMap클래스의 내부 클래스인 Entry의 배열에 저장을 하며 Object타입의 키와 값을 가지고 있다.

HashMap의 주요 메소드

- HashMap()

HashMap객체를 생성한다.

- HashMap(int initialCapacity)

지정된 값을 초기용량으로 하는 HashMap객체를 생성한다.

- HashMap(int initialCapacity, float loadFactor)

지정된 초기 용량과 load factor의 HashMap객체를 생성한다.

- HashMap(Map m)

지정된 Map의 모든 요소를 포함하는 HashMap 객체를 생성한다.

- Object put(Object key, Object value) = 추가

지정된 키와 값을 HashMap에 저장한다.

- void putAll(Map m) = 추가

Map에 저장된 모든 요소를 HashMap에 저장

- Object remove(Object key) = 삭제

HashMap에서 지정된 키로 저장된 값(객체)를 제거

- Object replace(Object key, Object value) = 변경

지정된 키와 값을 지정된 객체(value)로 대체

- boolean replace(Object key, Object oldVal, Object newVal) = 변경

지정된 키와 객체(oldVal)가 모두 일치하는 경우에만 새로운 객체로 대체

- boolean containsKey(object key) = 검색

HashMap에 지정된 키가 포함되어 있는지 여부를 반환한다

- boolean containsValue(Object value) = 검색

지정된 값이 포함되어있는지 여부를 반환한다

- Object get(Object key) = 검색

지정된 키의 값(객체)를 반환하며 찾지 못한다면 null을 반환한다

- Object getOrDefault(Object key, Object defaultValue) = 검색

지정된 키의 값을 반환하며 찾지 못하면 기본값(defaultValue)로 지정된 객체를 반환한다.

- Set entrySet() = 조회

HashMap에 저장된 키와 값을 엔트리의 형태로 Set에 저장한 후 반환한다.

엔트리는 키와 값을 전부 다 포함하였다는 것을 의미한다.

- Set keySet() = 조회

HashMap에 저장된 모든 키가 저장된 Set을 반환한다.

- Collection values()     

모든 값을 컬렉션의 형태로 반환한다.

컬렉션의 형태인 이유는 값이 중복을 허용하기 때문이다.(List, Set 둘 다 가능). List는 중복을 허용하나 Set은 중복이 허용되지 않는다.

- void clear()

저장된 모든 객체를 제거한다.

- boolean isEmpty()

HashMap이 비어있는지의 여부를 반환한다.

- int size()

HashMap에 저장된 요소의 개수를 반환해준다.

TreeMap

- TreeSet과 같이 객체를 정렬하여 저장한다는 특징을 가지고 있다.

- TreeSet은 TreeMap을 이용하여 구현한 클래스이다.

- 정렬과 범위 검색에 유리한 클래스이다.

- 정렬 후 저장하기 때문에 HashMap보다 데이터 추가, 삭제에 시간이 더 걸린다.

해싱(Hashing)

- 해시함수로 해시테이블(hash table)에 데이터를 저장하거나 저장된 데이터를 검색하는 과정을 의미한다. 

- 해시테이블은 데이터가 저장되는 공간이다. 이 테이블은 배열과 연결 리스트가 조합된 형태를 띄고 있다. 각 배열의 요소들에 연결리스트가 저장되어 있는 모양이다.

- 사용자가 개인정보를 저장한다고 할 때 키를 주민번호로 설정하게 되는데, 이 값을 해시함수에 넣으면 이 해시함수가 한 정수값을 반환하게 된다. 이 값을 해시코드(Hash Code)라고 부른다. 또한 해시코드는 배열들의 인덱스 값을 의미하기도 한다.

- 해시테이블에 저장된 데이터를 가져오는 과정

1) 키를 통해 해시함수를 호출 후 해시코드를 얻는다.

2) 해시코드(해시함수의 결과 반환값)에 대응하는 연결 리스트를 배열에서 찾는다.

3) 연결리스트에서 키와 일치하는 데이터를 찾는다.

* 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다. 또한 서로 다른 키라도 같은 해시코드값을 얻을 수수도 있다.

- 좋은 해시함수의 조건

1) 충돌이 적어야 한다.

2) 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포해야 한다.

3) 계산이 빨라야 한다.

TreeMap

- 이진 검색 트리의 구조로 되어 있으며 키와 값의 쌍으로 이루어진 데이터를 저장하게 된다.

- TreeSet과 다른 점은 Map 컬렉션이기 때문에 키와 값의 쌍으로 저장한다는 점이다.

- TreeSet처럼 데이터를 정렬(키 기준)해 저장하기 때문에 저장에 소요되는 시간이 길다.(TreeSet은 TreeMap을 이용해 구현되어 있다.)

- 다수 데이터에서의 개별적인 검색은 TreeMap보다 HashMap이 더 빠르다. 기타 Map 클래스가 필요할 때는 주로 HashMap을 사용하게 된다.

- 정렬 또는 범위검색이 필요할 때 TreeMap을 사용하게 된다.

- Map검색 자체는 키와 값의 쌍으로 되어 있어 iterator을 통해 추출할 수 없다. 이를 해결하기 위해서는 keySet메소드나 entrySet메소드를 이용해 Set형으로 변환한 후 iterator를 불러오는 방식을 이용하면 된다.

- TreeMap은 정렬할 때 기본적으로 오름차순을 통해 정렬되도록 설정되어 있다.