# Map

검색의 개념이 가미된 인터페이스로 데이터를 삽입할 때 Key 와 Value 의 형태로 관리한다.

때문에 해당 Key 를 이용해서 Value 값을 얻을수 있다.

# Hashtable 1.0

가장 처음에 나온 해시테이블을 가진 맵 클래스

• Key & Value 에 null 이 허용된다.
• 확장성이 떨어진다.
• 동시성 보장이 된다.
  • synchronized 키워드를 Method 전체에 Lock 을 적용한다.
  • Hashtable 을 참조하는 Thread 의 갯수가 많아질수록 Lock 을 획득하기 위한 시간비용이 많이 들어 성능이 급격히 낮아진다.
• HashMap 보다 성능이 떨어진다.
  • 2차 해시함수 사용불가
  • 단일스레드에서 사용시 Locking 이 느림

# HashMap 1.2

• 멀티스레드 기반에서 동시성 보장할 수 없다. (Thread-not-safe)
  • 단일 스레드 기반에서는 우선으로 사용
• Key & Value 에 null 허용
  • 정렬 기능을 지원함

탐색을 위한 시간복잡도는 O(1) 로 보장된다.

동시성 보장을 원하면 아래와 같이 변형해서 사용가능하다.

Map<K, V> m = Collections.synchronizedMap(new HashMap<>());

하지만 동시성 이슈가 있다면 ConcurrentHashMap 을 추천함

# ConcurrentHashMap 1.5

HashMap 을 thread-safe 하도록 만든 클래스가 ConcurrentHashMap 이며, key & value 에 null 을 허용하지 않는다.
둘 다 동기화 보장을 하는 특징이 있지만 구조적으로 작은 차이가 있다.

• 동시성 보장을 한다.
  • 내부적으로 여러개의 세그먼트를 두고 각 세그먼트마다 별도의 락을 가지고 있다.
  • 동시에 데이터를 삽입, 참조 하더라도 그 데이터가 다른 세그먼트에 위치하면 서로 Lock 을 얻기 위해 경쟁하지 않는다.
  • 이러한 방식을 Lock Striping 이라고 한다.
• Key & Value 에 null 허용 불가

# TreeMap 1.2

• 정렬기능을 지원함

# Hash 를 이용한 Map 관리

데이터를 저장 혹은 조회해오는 키 값을 Hash 값을 이용하며
저장되는 데이터의 Key & Value 의 개수에 따라 동적으로 크기가 증가하기도 한다.

# 해시함수

해시값을 이용한 자료형은 해시 함수를 통해서 나오는 인덱스 값으로 관리되는데 이 해시 함수는 해시 키값을 입력을 받아 해시 테이블상의 주소를 리턴해줘야 한다.

이는 해시함수를 작성시에는 다음 두가지의 조건을 만족하는것이 제일 좋다.

1. 입력되는 원소가 해시 테이블 전체에 고루 저장되어야 한다. (해시 분포)
2. 계산이 간단해야 한다 (성능)

첫번째 조건을 잘 만족해야만 서로 다른 두 원소가 하나의 해시 주소를 가지고 충돌날 확률이 적어지기 때문이다. (해시충돌)

대부분 아래와 같은 해시 함수를 사용한다.

int hashIndex = X.hashCode() % M;

이 코드와 같은 방식을 사용하면 서로 다른 객체가 1/M 의 확률로 같은 버킷을 가지게 된다.

해시를 이용한 인덱싱 사용으로 관리되는 이 Key 는 기본적으로 각 객체의 hashCode() 가 반환하는 값을 사용하는데 이 자료형은 int 다

32 bit 자료형으로는 완전한 자료의 해시 함수를 만들 수 없다.
논리적으로 2^32 보다 많을수도 있기 때문이며 해시를 이용한 Map 객체에서 랜덤 접근이 가능하게 하려면 원소가 2^32 인 배열을 모든 Map 이 가지고 있어야 하기 때문이다.

# 해시 충돌 (Hash Colision)

해시 충돌 (Hash Colision) 을 잘 회피하도록 구현해 놓았더라도 해시 충돌이 발행할 경우 회피할 수 있는 방법이 다음 대표적으로 두가지 방법이 사용된다.

다른 해시 회피방법이 있지만 이 두가지를 응용한 방법이다.

개방 주소법 (Open Address)

해시충돌이 발생하면 다른 버킷 (데이터 주소 공간) 을 찾아 자료를 삽입하는 방식이다.

비어있는 버킷을 탐색하거나 혹은 2차 해시함수를 이용하여 새로운 주소를 할당하는데
이 과정에서 새로운 해시 버킷을 찾는 방법을 Linear Probing, Quadratic Probing 등의 방법이 사용된다.

• 장점
  • 데이터 크기가 적다면 성능이 뛰어나다.
• 단점
  • 연속된 공간에 데이터를 저장하기 때문에 캐시 효율이 높다.
  • 크키가 커질수록 적중률 (hit ratio) 이 낮아지기 때문에 캐시 효율이 현저히 낮아진다.

분리 연결법 (Seperate Chaining)

Java HashMap 에서 사용중인 대표적인 방식으로 일반적으로 개방주소법보다는 성능상에 이점이 있다.

# 보조 해시 함수

저장하려는 두 개가 같은 인덱스로 해싱 (hashing : hash 함수를 통해 계산됨을 의미) 하게 되면 같은곳에 저장할 수 없게 된다.
때문에 해싱된 인덱스에 이미 다른 값들이 들어있다면 데이터를 저장할 다른 위치를 찾은뒤에야 저장할 수 있다.

이 외에도 해시 버킷의 동적 확장 등과 같은 방법도 있다.

# 해시 버킷의 동적 확장

해시 버킷의 개수가 작다면 메모리 사용을 아낄수 있지만 해시 충돌로 인한 성능상의 비용이 더 발생할 수 있다.

때문에 HashMap 은 Key & Value 의 쌍 데이터가 일정 개수 이상 되면 해시 버킷의 개수를 두배로 늘린다.

이 일정 개수는 기본 약 75% 정도로 load factor 로 HashMap 의 생성자에서 지정가능하다.

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

# 해시의 단점

데이터를 정렬된 순서로 접근하는것에 엄청난 비용이 발생한다.