HashMap의 동작을.. 얄팍하게 파악하자
어디에 어떻게 저장되어질까?
Node배열 — 해시버킷
/**
* 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;
HashMap의 객체들을 담는 테이블은 Node<Key,Value>[] 배열로 정의되어있다.
Node 가 있다.
/*** Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
} public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
} // getter setter
// equals}
TreeNode 도 있다.
LinkedHashMap.Entry<K,V> 는 HashMap.Node를 상속받는다.
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// 생략
}- Node<K,V>[] 배열 객체로 Node 또는 TreeNode를 담아 사용한다.
HashMap 에서 HashTable index로 사용될 Object의 Hash 값을 구하는 방법
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);hash.h의 상위 비트를 낮추기 위해 key.hashCode () 및 스프레드 (XOR)를 계산합니다. 이 테이블은 power-of-two Masking을 사용하기 때문에 현재 마스크 위에있는 비트 단위로만 변경되는 해시 세트가 항상 충돌합니다. (알려진 예로 작은 테이블에 연속적인 정수를 저장하는 Float 키 집합이 있습니다.) 그래서 우리는 더 높은 비트의 영향을 아래쪽으로 분산시키는 변환을 적용합니다. 속도, 유틸리티 및 비트 확산의 품질 간에는 균형이 있습니다. 많은 공통적 인 해시 세트가 이미 합리적으로 배포되어 있으므로 (확산에서 이점을 얻지 못함) 우리는 나무를 사용하여 큰 범위의 충돌을 처리하기 때문에 시스템 손실을 줄이기 위해 가능한 가장 저렴한 방법으로 비트를 이동 시켰습니다. 테이블 경계로 인해 인덱스 계산에 사용되지 않는 최상위 비트의 영향을 통합 할 수 있습니다.
HashMap에서 Put할때 동작
Parameters:
hash hash for key
key the key
value the value to put
onlyIfAbsent if true, don't change existing value
evict if false, the table is in creation mode.V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict)
- TREEIFY_THRESHOLD 에 의해 TreeNode 와 일반 Node로 변경된다.
- TREEIFY_THRESHOLD 이상의 연결Node일때 검색 속도를 위해 TreeNode로 변경
- 이렇게 해시버킷내의 동일 해시영역내에 LinkedList 또는 TreeNode로 구성되는 것이, 해시 충돌에 대한 방법인 Separate Chaining 방식이다.
참고 : https://d2.naver.com/helloworld/831311
해시버킷의 resize
HashMap의 해시버킷 최초 DEFAULT_INITIAL_CAPACITY [ 1<<4] 로 생성된다,
