내가 이해한 HashMap 과 HashTable

성종호·2023년 7월 8일

Java

HashMap과 HashTable

Java에서 Collection을 상속받고 있진 않지만 Collection으로 분류되는 Map 인터페이스를 상속받아 사용하는 HashMap, HashTable에 대해서 알아보겠다.

특징

키(key) 와 값(Value) 쌍으로 이루어진 데이터
이터레이션 프로토콜을 사용하는 자료구조
키에 대한 중복값 불가 값은 중복값 가능
데이터를 찾을때 O(1)의 시간복잡도를 갖는다.

HashMap과 HashTable 차이

HashMap은 Thread-Safety 하지 않으며 HashTable은 Thread-Safety하다.
HashMap은 키와 값에 Null을 허용하지만 HashTable은 Null을 허용하지 않는다.

내부 구조

저장 형태

/* 선언 및 초기화 방식 */
HashMap<String, String> map = new HashMap<String, String>()
map.put("키1", "값1");

이렇게 HashMap 객체를 생성하면 기본 크기(initial capcity)가 16인 객체가 생성되고 메모리에 할당을 받는다.

그리고 데이터를 할당할때 아래와 같은 흐름으로 데이터가 저장되게 된다.

1. 키1 이라는 문자열 객체의 hashcode()를 호출 예) 10016
2. 10016을 map의 기본크기인 16으로 모듈러연산(10016 % 16 = 0)
3. map객체를 생성할때 생성된 버킷배열의 0(모듈러 연산 값)번째 인덱스에 데이터가 안착

데이터를 계속 넣다보면 해시값의 모듈러 연산된 값이 중복될때가 있는데 이렇게 해시값이 중복이 되었을때를 해시충돌 이라고 한다.

해시충돌이 되었을때의 전략으로 중복이 되었을때 키1(10016), 키13(10032)의 인덱스인 0번째 인덱스에 LinkeList의 형태로 저장되게 된다.

Bucket 0:
    - Key: 키1, Value: 값1
    - Key: 키13, Value: 값13

Bucket 1:
    - Key: 키2, Value: 값2
    - Key: 키14, Value: 값14

.
.
.

Bucket 11:
    - Key: 키12, Value: 값12

그리고 HashMap과 HashTable의 특징으로 시간복잡도가 O(1)이라는 복잡도를 가졌다고 했는데

1. map.get("키1") -> 0번째 인덱스 가져옴
2. 0번째의 인덱스에 저장된 데이터를 반복하여서 가져옴
3. equals("키1") 메소드로 문자열 비교

위의 과정을 거치기 때문에 사실상 O(1)보다 시간복잡도가 올라가게 된다.

크기 변환

그리고 HashMap과 HashTable은 크기(capcity)가 정해져 있는데 임계값(load factor) 기본값= 0.75 만큼 데이터가 들어갔을때 현재 크기에 2배에 해당되는 메모리를 할당받는다.

크기가 커진만큼 예를들어 기본값이 16이고 2배인 36을 할당 받았을때 내부에 저장 되어있던 값을 다시 모듈러 연산을 통해 데이터를 재배치 한다.

Java 8버전 이후에는 특정 버킷 하나에 LinkedList의 요소가 기본 임계값(load factor) 8 을 넘어서게 되면 트리형태로 변환하게 되고 최소 임계값 6이하로 떨어지게 되면 다시 LinkedList의 형태로 변환하게 된다.