HashMap은 배열과 연결 리스트로 구성된 복잡한 구조입니다. 해시 값이 배열에서 키 값의 위치를 결정합니다. 연결된 목록의 길이가 설정된 임계값에 도달하면 데이터 보안과 데이터 관련 작업의 효율성을 보장하기 위해 트리 형태로 구성됩니다.
HashMap 성능은 해시 코드의 효율성에 따라 달라지므로 기본입니다. hashCode 및 같음의 규칙은 특히 중요합니다. 예를 들어, 같음은 같음, hashCode는 반드시 같아야 합니다. hashCode를 다시 작성하려면 hashCode도 일관성을 유지해야 하며, 상태 변경으로 반환된 해시 값은 여전히 일관되어야 합니다. 대칭, 반사, 전송 및 등호의 기타 특성
HashMap 및 Hashtable, TreeMap 차이점
HashMap: 배열 기반 비동기 해시 테이블, null 키 또는 값을 지원하며 키에 대한 첫 번째 선택입니다. 값 쌍 액세스 데이터 시나리오
Hashtable: 배열 기반 동기 해시 테이블, null 키나 값을 지원하지 않습니다. 동기화로 인해 성능에 영향을 미치기 때문에 거의 사용되지 않습니다.
TreeMap: 레드 기반의 순차 액세스를 제공하는 맵입니다. 블랙 트리는 HashMap보다 공간을 절약하지만 데이터 작업(쿼리, 추가, 삭제) 시간 복잡도는 O(log(n))로 HashMap과 다릅니다. null 값을 지원합니다. 키가 비어 있고 Comparator 인터페이스가 구현되지 않은 경우 NullPointerException이 발생합니다. Comparator 인터페이스를 구현하고 null 개체를 판단하면
HashMap, Hashtable 및 TreeMap이 모두 저장되거나 작동됩니다. 키-값 쌍의 형태. HashMap과 TreeMap은 AbstractMap 클래스에서 상속되고, Hashtable은 Dictionary 클래스에서 상속됩니다. 세 가지 모두 Map 인터페이스를 구현합니다
HashMap 소스 코드 분석
HashMap()
public HashMap(int initialCapacity, float loadFactor){
// ...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}초기화 시 일부 초기 값만 설정됩니다. HashMap이지만 Data 처리를 시작하면 .put() 메소드 등이 점차 복잡해지기 시작합니다
HashMap.put()
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 定义新tab数组及node对象
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果原table是空的或者未存储任何元素则需要先初始化进行tab的初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 当数组中对应位置为null时，将新元素放入数组中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 若对应位置不为空时处理哈希冲突
else {
Node<K,V> e; K k;
// 1 - 普通元素判断： 更新数组中对应位置数据
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 2 - 红黑树判断：当p为树的节点时，向树内插入节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 3 - 链表判断：插入节点
else {
for (int binCount = 0; ; ++binCount) {
// 找到尾结点并插入
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 判断链表长度是否达到树化阈值，达到就对链表进行树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 更新链表中对应位置数据
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 回调以允许LinkedHashMap后置操作
afterNodeAccess(e);
return oldValue;
}
}
// 更新修改次数
++modCount;
// 检查数组是否需要进行扩容
if (++size > threshold)
resize();
// 回调以允许LinkedHashMap后置操作
afterNodeInsertion(evict);
return null;
}테이블이 null일 경우 resize(), resize()를 통해 초기화됩니다. 두 가지 기능이 있는데, 하나는 테이블을 생성하고 초기화하는 것이고, 두 번째는 테이블 용량이 수요를 충족하지 못할 때 용량을 확장하는 것입니다:
if (++size > threshold)
resize();구체적인 키-값 쌍 저장 위치 계산 방법은:
if ((p = tab[i = (n - 1) & hash]) == null)
// 向数组赋值新元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果新插入的结点和table中p结点的hash值，key值相同的话
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是红黑树结点的话，进行红黑树插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 代表这个单链表只有一个头部结点，则直接新建一个结点即可
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 链表长度大于8时，将链表转红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 及时更新p
p = e;
}
}
// 如果存在这个映射就覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 判断是否允许覆盖，并且value是否为空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 回调以允许LinkedHashMap后置操作
return oldValue;
}
}주의하세요 .put() 메소드에서 해시 계산을 할 때, 키의 hashCode가 아니라, XOR 연산을 위해 키의 hashCode 중 상위 비트 데이터를 하위 비트로 이동시켜 계산된 해시 값이 다음과 같이 되도록 하는 것입니다. 주로 높은 비트 데이터에서 다르며 HashMap에서 해시 주소를 지정할 때 용량 이상의 높은 비트는 무시되지 않습니다. 그러면 이러한 상황에서 해시 충돌을 효과적으로 피할 수 있습니다
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}HashMap.resize()
final Node<K,V>[] resize() {
// 把当前底层数组赋值给oldTab，为数据迁移工作做准备
Node<K,V>[] oldTab = table;
// 获取当前数组的大小，等于或小于0表示需要初始化数组，大于0表示需要扩容数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 获取扩容的阈值（容量*负载系数）
int oldThr = threshold;
// 定义并初始化新数组长度和目标阈值
int newCap, newThr = 0;
// 判断是初始化数组还是扩容，等于或小于0表示需要初始化数组，大于0表示需要扩容数组。若 if(oldCap > 0)=true 表示需扩容而非初始化
if (oldCap > 0) {
// 判断数组长度是否已经是最大，MAXIMUM_CAPACITY =（2^30）
if (oldCap >= MAXIMUM_CAPACITY) {
// 阈值设置为最大
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 目标阈值扩展2倍，数组长度扩展2倍
newThr = oldThr << 1; // double threshold
}
// 表示需要初始化数组而不是扩容
else if (oldThr > 0)
// 说明调用的是HashMap的有参构造函数，因为无参构造函数并没有对threshold进行初始化
newCap = oldThr;
// 表示需要初始化数组而不是扩容，零初始阈值表示使用默认值
else {
// 说明调用的是HashMap的无参构造函数
newCap = DEFAULT_INITIAL_CAPACITY;
// 计算目标阈值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 当目标阈值为0时需重新计算，公式：容量（newCap）*负载系数（loadFactor）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 根据以上计算结果将阈值更新
threshold = newThr;
// 将新数组赋值给底层数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// -------------------------------------------------------------------------------------
// 此时已完成初始化数组或扩容数组，但原数组内的数据并未迁移至新数组（扩容后的数组），之后的代码则是完成原数组向新数组的数据迁移过程
// -------------------------------------------------------------------------------------
// 判断原数组内是否有存储数据，有的话开始迁移数据
if (oldTab != null) {
// 开始循环迁移数据
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 将数组内此下标中的数据赋值给Node类型的变量e，并判断非空
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 1 - 普通元素判断：判断数组内此下标中是否只存储了一个元素，是的话表示这是一个普通元素，并开始转移
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 2 - 红黑树判断：判断此下标内是否是一颗红黑树，是的话进行数据迁移
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 3 - 链表判断：若此下标内包含的数据既不是普通元素又不是红黑树，则它只能是一个链表，进行数据转移
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回初始化完成或扩容完成的新数组
return newTab;
}용량 및 부하 계수에 따라 배열 용량이 결정됩니다. 공간이 너무 많으면 공간 낭비가 발생하고, 너무 많이 사용하면 운영 성능에 영향을 미칩니다.
HashMap이 액세스할 키-값 쌍의 수를 명확하게 알 수 있다면 설정을 고려해 볼 수 있습니다. 미리 적절한 용량을 확보하세요. 용량 확장이 발생하는 조건에 따라 특정 값을 간단하게 추정할 수 있습니다. 이전 코드 분석을 바탕으로 부하율 * 용량 > 요소 수
라는 계산 조건을 충족해야 함을 알 수 있습니다. 사전 설정된 용량은 충족되어야 하며 사전 설정된 것보다 커야 합니다. 요소 수/부하 계수를 추정하면 2
의 거듭제곱이 됩니다. 하지만 주의해야 할 점:
특별한 필요가 없으면 변경하지 마세요. JDK 자체의 기본 로드 요소는 일반적인 시나리오의 요구 사항과 매우 일치하기 때문에 쉽게 수행할 수 있습니다. 정말로 조정이 필요한 경우 0.75를 초과하는 값을 설정하지 않는 것이 좋습니다. 충돌이 크게 증가하고 HashMap의 성능이 저하되기 때문입니다. 너무 작은 부하율을 사용하면 미리 설정된 용량 값도 위 공식에 따라 조정됩니다. 그렇지 않으면 용량 확장이 더 자주 발생하고 불필요한 오버헤드가 증가하며 액세스 성능 자체에도 영향을 미칠 수 있습니다.
HashMap.get()
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 将table赋值给变量tab并判断非空 && tab 的厂部大于0 && 通过位运算得到求模结果确定链表的首节点赋值并判断非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断首节点hash值 && 判断key的hash值（地址相同 || equals相等）均为true则表示first即为目标节点直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 若首节点非目标节点，且还有后续节点时，则继续向后寻找
if ((e = first.next) != null) {
// 1 - 树：判断此节点是否为树的节点，是的话遍历树结构查找节点，查找结果可能为null
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 2 - 链表：若此节点非树节点，说明它是链表，遍历链表查找节点，查找结果可能为null
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}HashMap이 트리형인 이유
데이터 보안 및 관련 작업 효율성을 보장하기 위해
요소 배치 과정에서 객체 해시 충돌이 발생하면 모두 동일한 버킷에서는 연결된 목록이 형성되며, 이는 선형적인 방식으로 액세스 성능에 심각한 영향을 미칩니다. 실제로는 해시 충돌 데이터를 구성하는 것이 악성 코드에 사용될 수 있습니다. 이러한 대량의 데이터가 서버 측과 상호 작용하여 서버 측에서 많은 양의 CPU를 사용하게 되어 해시 충돌 서비스 거부 공격이 발생합니다
위 내용은 Java HashMap 투석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
