컬렉션 프레임워크(Collection Framework) (4) - 해시테이블(Hashtable...

컬렉션 프레임워크(Collection Framework) (4) - 해시테이블(Hashtable...

1. Hashtable vs HashMap

앞서 HashMap 클래스에 있는 메소드의 사용법에 대해 알아보았다.

2021.12.28 - [자바] - 컬렉션 프레임워크(Collection Framework) (3) - Map

컬렉션프레임워크가 등장하기전 자바에서 제공하는 데이터 구조체로 Hashtable 이 있다.

HashMap과 마찬가지로 Map 인터페이스를 구현하여 제공하는 기능은 같지만 차이점이 존재한다.

기능 HashMap Hashtable 키값에 null 허용 가능 불가능 멀티 쓰레드 환경 불안전 안전 중복키 처리방법 나중에 입력한 값으로 변경 초기값 유지

HashMap은 키값에 null을 허용하며, 중복된 키를 입력했을 경우 나중에 입력한 값으로 변경되고,

Hashtable은 키값에 null을 허용하지 않으며, 메소드가 synchronized가 걸려있어 멀티쓰레드 환경에서 안전하다.

2021.12.24 - [자바] - 쓰레드(3) - Synchronized

2. HashMap, Hashtable의 원리

키를 해시 처리한뒤 인덱싱을 관리하여 버킷에 저장하는 구조

위 그림은 hash function을 사용하여 키(key)를 해시값으로 매핑하고, 이 해시값을 인덱싱하여 데이터(value)를 키(key)와 함께 저장한다.

즉, key-value 가 1:1로 매핑되어있어 삽입, 삭제, 검색의과정에서 평균적으로 O(1)의 시간복잡도를 가진다는 장점이있다.

int index = A.hashCode() % M // M 은 전체 데이터의 양

인덱싱을 하는 계산법은 hashCode()를 전체 데이터의 양으로 나눈 나머지로 계산된다.

이렇게 인덱싱을 하게 되면 1/M 의 확률로 같은 공간을 사용하게 되는데 그것을 해시 충돌 이라고 부른다.

해시충돌이 일어나는 경우 별도의 관리를 안해주면 탐색의 시간복잡도가 O(1) 에서 O(n) 으로 가까워지기 때문에

Open Addressing 방식과 Seperate Chaining 방식으로 자료구조를 관리한다.

Open Addressing 방식

Open Addressing 방식은 해시 충돌발생시 뒤에있는 버킷중 빈 버킷을 찾아 자료를 저장하는 방식이다.

그림에서 Sandra의 인덱스는 152이다 하지만 John의 인덱스에 충돌이 발생하기 때문에 153 인덱스에 값을 저장한다.

이러한 방식으로 Sandra의 Key 검색이나 삭제를 할때에도 index가 152이고 Key가 일치하지 않으므로 뒤의 index를 검색해서 같은 Key가 나오거나 혹은 Key가 없을 때 까지 조회한다.

Seperate Chaining

Seperate Chaining 방식은 JDK 내부에서도 사용하고있는 방식으로 LinkedList와 Tree를 사용한다.

(데이터가 6개 이하이면 LinkedList를 8개 이상이면 tree를 사용)

해시 충돌이 발생하면 인덱스가 가리키고 있는 LinkedList에 노드를 추가하여 값을 삽입한다.

데이터를 조회하거나 삭제할 때 키에 대한 인덱스가 가리키고 있는 LinkedList를 선형검색하여 작업을 수행한다.

Seperate Chaning & Open Addressing 효율 비교

데이터의 갯수가 적을때는 Open Addressing의 효율이 더 좋고, 반대의 경우 Seperate Chaning의 효율이 더 좋다.

3. HashMap, Hashtable의 리사이징(Resizing)

HashMap 클래스를 열어보면

/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f;

선언된 상수들을 보면 해시맵의 초기 용량은 16이고, 기본 load factor는 0.75로 HashMap의 용량이 75%가 채워지면 용량을 2배로 늘리는 작업을 수행한다.

이러한 작업은 더큰 버킷을 가지는 배열을 새로만든후, 새로만든 배열에 hash를 다시 계산해서 복사를 한다.

따라서 많은 용량을 처리하는 경우 초기 용량과 load factor HashMap 생성시 늘려준다면 불필요한 Resizing 작업을 수행하지 않을 것이다.

HashMap map = new HashMap<>(16,1.5f);

from http://dev-cool.tistory.com/9 by ccl(A) rewrite - 2021-12-28 15:27:09