[DataStructure] HashMap (Java)

1. HashMap

Java 11

Module java.base
Package java.util
Class HashMap<K,​V>
java.lang.Object
    java.util.AbstractMap<K,​V>
        java.util.HashMap<K,​V>

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values

All Implemented Interfaces:
Serializable, Cloneable, Map<K,​V>

Direct Known Subclasses:
LinkedHashMap, PrinterStateReasons

public class HashMap<K,​V>
extends AbstractMap<K,​V>
implements Map<K,​V>, Cloneable, Serializable

2. 설명

Map 인터페이스의 해시 테이블 기반 구현. 이 구현은 모든 선택적 맵 작업을 제공하고 null 값과 null 키를 허용합니다. (HashMap 클래스는 동기화되지 않고 null을 허용한다는 점을 제외하면 Hashtable과 거의 동일합니다.) 이 클래스는 맵의 순서를 보장하지 않습니다. 특히 order가 시간이 지나도 일정하게 유지된다는 보장은 없습니다.

이 구현은 해시 함수가 버킷 간에 요소를 적절하게 분산한다고 가정할 때 기본 작업(get 및 put)에 대해 일정한 시간 성능을 제공합니다. 컬렉션 보기를 반복하려면 HashMap 인스턴스의 "capacity"(버킷 수)과 크기(키-값 매핑 수)에 비례하는 시간이 필요합니다. 따라서 반복 성능이 중요한 경우 초기 용량을 너무 높게(또는 너무 낮게 로드 팩터) 설정하지 않는 것이 매우 중요합니다.

HashMap의 인스턴스에는 성능에 영향을 미치는 두 가지 매개변수가 있습니다. capacity(초기 용량)과 load factor(부하율)입니다. 용량은 해시 테이블에 있는 버킷의 수이며 초기 용량은 단순히 해시 테이블이 생성된 시점의 용량입니다. 로드 팩터는 해시 테이블의 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 차도록 허용되는지를 측정한 것입니다. 해시 테이블의 항목 수가 로드 팩터와 현재 용량의 곱을 초과하면 해시 테이블을 다시 해시하여(즉, 내부 데이터 구조를 재구축) 해시 테이블의 버킷 수가 약 2배가 되도록 합니다.

일반적으로 기본 부하 계수(0.75)는 시간과 공간 비용 간에 적절한 균형을 제공합니다. 값이 높을수록 공간 오버헤드가 감소하지만 조회 비용이 증가합니다(가져오기 및 넣기를 포함하여 HashMap 클래스의 대부분의 작업에 반영됨). 맵의 예상 항목 수와 로드 계수는 초기 용량을 설정할 때 고려하여 rehash 작업 수를 최소화해야 합니다. 초기 용량이 최대 항목 수를 로드 팩터로 나눈 것보다 크면 rehash 작업이 발생하지 않습니다.

HashMap 인스턴스에 많은 매핑을 저장해야 하는 경우 충분히 큰 용량으로 매핑을 생성하면 테이블을 확장하는 데 필요한 자동 rehashsing을 수행하는 것보다 매핑을 더 효율적으로 저장할 수 있습니다. 동일한 hashCode()로 많은 키를 사용하는 것은 모든 해시 테이블의 성능을 저하시키는 확실한 방법입니다. 영향을 개선하기 위해 키가 Comparable일 때 이 클래스는 키 간의 비교 순서를 사용하여 연결을 끊을 수 있습니다.

이 구현은 동기화되지 않습니다. 여러 스레드가 해시 맵에 동시에 액세스하고 스레드 중 하나 이상이 구조적으로 맵을 수정하는 경우 외부에서 동기화해야 합니다. (구조적 수정은 하나 이상의 매핑을 추가하거나 삭제하는 모든 작업입니다. 인스턴스에 이미 포함된 키와 연결된 값을 변경하는 것만으로는 구조적 수정이 아닙니다.) 이는 일반적으로 맵을 자연스럽게 캡슐화하는 일부 객체를 동기화하여 수행됩니다. 그러한 객체가 없으면 Collections.synchronizedMap 메소드를 사용하여 맵을 "래핑"해야 합니다. Map에 대한 우발적인 동기화되지 않은 액세스를 방지하려면 생성 시 수행하는 것이 가장 좋습니다.

Map m = Collections.synchronizedMap(new HashMap(...));

이 클래스의 모든 "컬렉션 뷰 메소드"에 의해 반환된 iterator는 fail-fast입니다: 반복자가 생성된 후 언제든지 맵이 구조적으로 수정되면 반복자의 자체 제거 메소드를 통하지 않는 방식으로 반복자는 ConcurrentModificationException을 던질 것입니다. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

iterator의 fail-fast 동작은 일반적으로 동기화되지 않은 동시 수정이 있는 경우 확실한 보장을 하는 것이 불가능하기 때문에 보장할 수 없습니다. Fail-fast iterator는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 정확성을 위해 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다. 반복기의 빠른 실패 동작은 버그를 감지하는 데만 사용해야 합니다.

이 클래스는 Java Collections Framework의 멤버입니다.

Since:
1.2
See Also:
Object.hashCode(), Collection, Map, TreeMap, Hashtable, Serialized Form