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] 로 생성된다,

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store