맵 Map

 - 맵은 해시라고도 하며 배열이나 사전(dictionary)과 관련 잇는 키-값 형태의 저장소.

 - 맵을 구현할 때는 Map 인터페이스를 사용한다.

 - List 인터페이솨 달리 Collection 인터페이스를 구현하지 않는다는 차이가 있다,

 - 맵의 특징 중 하나는 키 값은 트리 상에서 한 번만 나타난다는 것.

 

맵에서 키를 덮어 쓰는 예

 

 - HashMap 클래스는 해시 테이블을 자바로 구현한 것으로, 클래스 구현에는 키-값 쌍을 나타내는 Entry라는 내부 클래스가 있다.

 - 원소들은 Entry 객체의 배열로 저장할 수도 있고 배열 대신 Entry 객체의 리스트로 저장할 수도 있다.

 - 이렇게 저장된 원소의 특정 키 인스턴스의 값은 테이블의 어디에 해당 값이 있는지 정의

 - Object 클래스에 정의된 HashCode 메서드는 int 타입 값을 반환하며 이 값은 테이블 어디에 키-값 쌍이 있는지 확인하는데 사용

 - hashCode 메서드는 두 개의 같은 인스턴스는 같은 hashCode메서드 값을 반환해야 한다.

 - 하지만 반대는 성립하지 않는다. 두 개의 hashCode 값이 같은 인스턴스를 가리키지 않는다.

 

 - HashMap 클래스용으로 테이블에 값을 삽입했을 때는 hashCode 메서드가 해당 값을 읽은 다음 int 범위 안에 유요한 값이라면 반환되는 값이 될수 있다.

 - 반환 값은 보통 테이블 크기보다 작은 0과 1 사이의 값으로 반영됨.

 

 - 동일하지 않은 객체들이 같은 hashCode 메서드 값을 반환할 수도 있는 상황도 고려해야 함.

 - 구조상 서로 다른 객체가 같은 해시 테이블에 들어가는 상황이 발생할 수 있기 때문이다. 따라서 충돌이 발생할 경우 처리 방법도 고려 해야 함.

 

해결 방법

(1) 두 번째 해시 함수를 갖는 것.

 - 두 번째 해시 함수는 값을 삽입하려고 할 때 테이블의 위치에 이미 다른 값이 있으면 오프셋 방식으로 해당 값이 삽입될 위치를 다시 계산 함.

 - 하지만 이는 단지 충돌을 미룰 뿐 객체의 충돌은 여전히 발생한다.

 

(2) 각 테이블 원소에 대한 값들의 리스트를 저장하고 같은 테이블 인덱스와 연결되는 모든 테이블 키를 리스트의 값으로 추가 하는것.

 - 테이블을 간단하게 순회함으로써 키 복구를 수행하며 맞는 값을 찾을 때 까지 각원소들이 같인지 확인하는 장점이 있다,

 

 - 많은 원소를 가진 작은 테이블이 적은 원소를 가진 큰 테이블보다 충돌이 발생할 가능성이 높다.

 - 새로운 HashMap 객체를 생성할 때 백분율을 나타내는 0 과 1 사이의 값으로 부하계수를 명시할 수 있다.

 - 테이블은 이 부하계수를 다 채우게 되면 테이블 크기를 2배로 늘린다.

 - 테이블 크기가 조정되면 테이블의 모든 원소를 재배치 한다.

 - hashCode 메서드 값이 테이블의 인덱스에 맞게 재할당 되기 때문.

 - 많은 원소가 있는 테이블의 재할당느 많은 자원과 시간을 소모하는 작업이다.

 - 맵에서 많은 원소를 사용할 것이라고 미리 파악했다면 처음 맵을 만들 때 테이블 크기를 재할당 하지 않도록 적당한 크기로 테이블을 초기화 하는것이 좋다.

 

TreeMap

 - TreeMap 클래스는 Map 인터페이스를 구현하느데 이진 트리 자료구조를 이용한다.

 - TreeMap 에서 Comparable과 Comparator 인터페이스를 사용한다.

 - TreeMap 클래스는 키를 정렬 가능한 순서에 따라 저장하기 때문에 hashCode 메서드는 전혀 사용되지 않는다.

 - TreeMap 클래스에 포함된 각종 원소는 균형을 맞춘 트리 구조로 구성되어 있으므로 검색, 삭제, 삽입 같은 모든 동작이 항상 O(log n) 처리 성능을 발휘한다.

 - TreeMap과 HashMap의 주된 차이는 순서가 보존되고 보존되지 않는 차이이다.

 

LinkedHashMap

 - 기본적으로 HashMap 클래스와 같은 방식으로 작동한다.

 - 그래서 원소를 찾는데 O(1) 성능을 발휘

 - 키를 반속 순회할 때 삽입하는 경우와 순서가 같아야 한다.

 

ConrurentHahMap

 - 맵 인스턴스를 많은 스레드에서 공유하고자 한다면 이 방법이 유용

 - 스레드 세이프 하고, 맵에 값을 쓰는 도중이라도 값을 읽어서 반환할 수 있다.