key 와 value 를 맵핑하는 자료구조
key 는 중복될 수 없다.
key 는 최소한 하나의 value 를 가져야 한다.
3가지 collection view 를 제공한다. 데이터가 넣어진 순서를 보장하지 않는다. (TreeMap 제외)
equals()
Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This ensures that the equals method works properly across different implementations of the Map interface.
hashCode()
Returns the hash code value for this map. The hash code of a map is defined to be the sum of the hash codes of each entry in the map's entrySet() view. This ensures that m1.equals(m2) implies that m1.hashCode()==m2.hashCode() for any two maps m1 and m2, as required by the general contract of Object.hashCode.
Map 인터페이스의 구현 클래스
get(), put()
메서드는 constant time 의 시간복잡도를 제공해야한다.Node<K, V> table
필드다./**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
singly-linked-list
한 bucket 의 Node 수가 TREEIFY_THRESHOLD 에 도달하면 bucket 의 자료구조가 singly-linked-list 에서 Tree 로 변환된다.
Linked-List 의 검색 시간 복잡도는 O(n) 이기 때문에 검색 성능 개선을 위해 Java8 부터 변경 되었다고 한다.
잘못된 해싱 함수로 인해 하나의 버킷에 많은 데이터가 저장되어도 트리 구조에서는 검색 시간 복잡도가 O(logn) 이기 때문에 어느 정도 상쇄될 수 있다고 한다.
Binary-Search-Tree
putVal
, HashMap 이 데이터를 넣기 처리하는 메서드지역변수
Node<K, V>[] tab
: bucket 배열
Node<K, V> p
:
bucket 배열에 넣어야할 Node
int n
:
bucket 배열의 길이
tab==null
) 이거나 length == 0
이면n
에 초기화된 bucket 배열의 사이즈를 할당한다. p
에 할당한다.**p == null**
이면 Node 를 생성하고 bucket 배열에 할당한다. 지역변수 - Node<K,V> e
, K k
: Key 객체 참조값
bucket 배열에 이미 있는 Node p
와 새로 넣을 K-V 쌍에서 동등한 Key 객체인지 확인한다.
동등한 Key 객체일 경우 e
에 기존 Node p
를 할당한다.
동등한 Key 객체가 아닌 경우 bucket 에 Node 를 추가해야 하는데,
HashMap 은 bucket 의 사이즈가 임계치를 넘으면 Linked-list → Tree 로 변환하기 때문에
Node 가 TreeNode 인지 아닌지 검사한 뒤 분기 처리한다.
hash(Object key)
buckets 의 인덱스를 계산하는 메서드
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
resize()
, bucket 동적 확장을 처리하는 메서드table
필드에 할당한다.