HashMap源码分析
HashMap用来存储key-value对，内部使用拉链法Hash表作为存储结构，key-value被封装成Entry<K, V>，Entry也是链表结点。
1. Hash表的内部结构如下：
Entry<K, V> table[];
table[0]-->Entry(K,V)-->Entry(K,V)
table[1]-->Entry(K,V)
table[2]
table[3]-->Entry(K,V)
table[.]
Entry<K,V>数据域代码:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
}
HashMap的Key-Value对，被包装成Entry(K,V)，根据key计算hash值，确定在table数组的下标位置，数组元素为链表的链表头，被计算hash映射到相同数组下标位置的key-value都被存储在这个链表当中，这就是解决hash冲突的办法 。
2.HashMap中查找目标Entry<K,V>
也就是说根据key进行hash只能找到Entry(K,V)在哪个链表当中，查找到具体确切的Entry(K,V)还需要遍历整个链表的每个节点，针对每个节点去匹配key值，如果链表很长，那么效率就会很低，体现不出Hash表的优势。理想的情况是每个链表不多于一个节点，这样通过hash就可以直接找到目标Entry(K,V)，能够在O(1)内实现元素的查找，像数组一样，在存储内容与存储位置之间建立直接的映射关系。
3.HashMap中的扩容
为了提升Hash表的性能，在HashMap中存储的k-v对数目超过了预定的负载量threshold时，就对HashMap进行扩容，实际上就是使用table[]数组成倍增加，这样做的目的是使每个链表长度较为短小，能够实现快速的定位目标结点；但是扩容需要对原HashMap中的每个结点重新计算存储位置，迁移到新的table[]当中，这也是一笔不少的开销，应该减少扩容的次数，所以根据应用场景选择一个合适的loadFactor和capacity比较重要,loadFactor和capacity可以在HashMap的构造函数中设置。
Threshold计算: threshold = (int)(capacity * loadFactor);( 当前容量 * 负载因子)
默认的容量和负载因子:
Static int final DEFAULT_INITIAL_CAPACITY = 16;
Static int final DEFAULT_LOAD_FACTOR = 0.75f;
4.HashMap不是线程安全的，代码中没有任何的同步措施，在多线程中环境中需要注意。
5.代码分析
构造函数
//指定初始容量和负载因子的构造函数
public HashMap(int initialCapacity, float loadFactor) {
//检测参数的合法性initialCapacity, loadFactor
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//当HashMap存储的键值对数，超过threshold，就需要对整个hash table进行扩展
//threshold = capactiy * loadFactor;通过负载因子计算得来.
threshold = (int)(capacity * loadFactor);
//为HashMap依赖的table申请空间
table = new Entry[capacity];
init();
}
//使用默认的负载因子，默认的初始容器，
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
get(k)方法
public V get(Object key) {
//如果key是null,返回一个Object对象作内部处理，HashMap中可以使用null作为key
Object k = maskNull(key);
//计算此k(key)对应的hash值
int hash = hash(k);
//indexFor:h & (length-1)
//计算此key在hash表中的映射到的数组元素位置(每个元素是一个指向链表的头结点)
int i = indexFor(hash, table.length);
//取得链表头，映射到数组同一位置的元素被组织成一个链表(冲突解决方法)
Entry<K,V> e = table[i];
while (true) {
//如果查找到链表末尾，表示没有查找到，返回null
if (e == null)
return null;
//判断所以给key,与存储在HashTable中key是否完全相等
//如果完全相等，则查找到目标key-value对，返回value object
//x与y两个key完全相等的条件:x == y || x.equals(y);
//也就是说如果两个key内容相等或者指向同一个对象引用，均算作相等。
if (e.hash == hash && eq(k, e.key))
return e.value;
//继续查找下一个元素
e = e.next;
}
}
put(k,V)
public V put(K key, V value) {
//如果key为null，通过maskNull转换成Object对象进行内部存储操作
K k = maskNull(key);
//计算key对应的hash值，确定在Hash数组中的位置
int hash = hash(k);
int i = indexFor(hash, table.length);
//找到链表的头结点后，首先在链表中确定此key是否被其它的key-value对所占用
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果此key已经在HashMap中存在，则更新此key-value中的value值
if (e.hash == hash && eq(k, e.key)) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
//并且返回oldValue
return oldValue;
}
}
modCount++;
//确定此key不存在HashMap中后，直接将key-value存入HashMap中，也就是插入链表中
addEntry(hash, k, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
//Entry内部用来封装key-value对
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//如果当前HashMap中存储的k-v对数目(size)超过threshold，需要对整个HashMap进行扩容
//扩展成原来的2倍大小
if (size++ >= threshold)
resize(2 * table.length);
}
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//为HashMap分配新的内存空间
Entry[] newTable = new Entry[newCapacity];
//迁移旧HashMap上的数据到新的空间newTable上
transfer(newTable);
table = newTable;
//重新计算负载上限
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
//取出数组元素中的链表头结点
Entry<K,V> e = src[j];
//如果链表不是空的
if (e != null) {
src[j] = null;
//为链表中的每一个结点重新分配新的位置在newTable当中
//因为位置的计算是hash & (length-1);length改变了，所以存储位置也跟着变了
do {
Entry<K,V> next = e.next;
//计算结点e的新的存储位置在newTable中
int i = indexFor(e.hash, newCapacity);
//将结点添加到链表newTable[i]中
e.next = newTable[i];
newTable[i] = e;
//e指向下一个结点
e = next;
} while (e != null);
}
}
}
remove(k)方法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
Entry<K,V> removeEntryForKey(Object key) {
//根据key计算hash值，映射到数组下标位置，找到链表头
Object k = maskNull(key);
int hash = hash(k);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
//查找封装目标key-value的Entry
if (e.hash == hash && eq(k, e.key)) {
modCount++;
size--;
//这种情况只有在链表中只有一个结点时候才会才成立
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//在遍历过程中记录当前结点e的前驱
prev = e;
e = next;
}
return e;
}
eq()用于比较两个key是否相等
两个key相等的条件是:(1).两者指向同一个引用
(2).两者equals相等(考虑是否要重写key类的equals()，根据需要)
static boolean eq(Object x, Object y) {
return x == y || x.equals(y);
}
分享到：
相关推荐
1.面试必考之HashMap源码分析与实现 伸缩性角度看HashMap的不足
面试中，HashMap的源码分析与实现是一个常见的考察点，因为它涉及到数据结构、并发处理和性能优化等多个核心领域。本篇文章将深入探讨HashMap的内部工作原理、关键特性以及其在实际应用中的考量因素。 HashMap基于...
《HashMap 源码解析——JDK11版本》 HashMap是Java中广泛使用的非同步散列表，其设计和实现是高效且灵活的。在JDK1.8之前，HashMap的底层数据结构采用的是数组+链表的方式，这种方式称为“拉链法”来解决哈希冲突。...
hashmap的原理啊思想。
#### 二、HashMap线程安全问题分析 在多线程环境中，`HashMap`的主要线程安全问题包括但不限于： 1. **链表死循环问题**：在JDK 1.7中，当多个线程同时进行`put`操作时，可能会出现链表死循环的情况，这是一个严重...
Java集合系列之HashMap源码分析 Java集合系列之HashMap源码分析是Java集合系列中的一篇非常重要的文章，它详细介绍了Java集合系列之HashMap源码，具有很高的参考价值。下面我们将对HashMap源码进行详细的分析。 ...
哈希映射（HashMap）是Java编程语言中广泛使用的数据结构之一，主要提供键值对的存储和查找功能。HashMap的实现基于哈希表的概念，它通过计算对象的哈希码来快速定位数据，从而实现了O(1)的平均时间复杂度。在深入...
微信小程序详细图文教程 泉州大白网络科技 目录 一.微信小程序申请 二....1.申请服务器 2.部署服务器 3.域名申请和配置 三....一....申请，并认证（未认证不能发布，认证需要300元，目前只支持企业认证）详细见官网说明。...
JAVA之hashmap源码分析 Mobile-Dev-Analysis Analysis of android or java 红岩网校工作站移动开发部学员分组学习 为了让大家学的更加坚固，采取小组学习的方式帮助大家学习，同时在学习研究的过程中需要不断的做...
JAVA之hashmap源码分析 无头Android堆分析器 “哈哈！” -纳尔逊 此存储库已弃用 创建该项目的目的是通过重新打包其他存储库中的堆转储解析器来提供堆转储解析器。 LeakCanary现在有它自己的。 该解析器在Maven ...
JAVA之hashmap源码分析Superword是Java开源项目，致力于研究英语单词分析和辅助阅读，包括但不限于拼写相似度，定义相似度，发音相似度，拼写转换规则，前缀和动态前缀，后缀以及动态后缀，词根，复合词，文本辅助...
四、HashMap源码分析 HashMap是一种基于散列表实现的Map，提供了快速的键值对存储和检索能力。HashMap的继承体系中，它继承了AbstractMap，实现了Map接口。 HashMap的主要属性包括键值对数组table、键值对个数size...
面试必考之HashMap源码分析与实现 ，微服务架构之Spring Cloud Eureka 场景分析与实战，高性能必学之Mysql主从架构实践 ，架构师不得不知道的Spring事物不能回滚的深层次原因 ，分库分表之后分布式下如何保证ID全局...
在本文中，我们将深入探讨如何使用Java在Android平台上实现模拟登录知乎并抓取用户信息的过程。... 首先，我们需要了解的是Android的网络访问机制。Android系统为了安全性和用户体验，对网络访问进行了限制，必须在...
注意看更新历史注如果需要学习资料，可以加我微信纪实西川笔记Java系列java进阶java 泛型java实例化的软件开发方式nio基础ArrayList源码分析LinkedList源代码分析HashSet和TreeSet源码分析HashMap源码分析(JDK1.8)...
《HashMap源码剖析》 HashMap是Java编程语言中一个非常重要的数据结构，它在实际开发中被广泛应用。作为集合框架的一部分，HashMap实现了Map接口，提供了高效、非同步的键值对存储功能。在这个10页的PDF文档中，...