最新仔细看了一遍JDK1.6 HashMap的源码,收获颇深,写一篇博客来记录下自己的学习心得。HashMap也是Java中一个非常重要的集合,确实值得研究和学习。
本文主要分几个步骤来讲HashMap:
一、HashMap底层实现
二、HashMap源码分析
1.成员变量
2.构造方法
3.put()方法和get()方法
三、HashMap需要注意的关键点
一、HashMap底层实现
HashMap底层是通过数组和链表来实现的。
HashMap是Java中存储键值对的容器,当我们调用HashMap的put()方法往Map存储数据时,HashMap先通过“hash算法”得出该key的hashCode值,再通过hash值和数组长度计算出该key存储在数组中的索引位置,如果该索引位置上存在相同的hashCode和相同的key,则新值覆盖旧值,并返回旧值;如果存在相同的hashCode,但是key不相同,这时就产生hash冲突,hash冲突后数组里单个元素存放的不是一个Entry,而是一个Entry链,Entyr存放的是key-value,HashMap结构如下图:

二、HashMap源码分析
1、成员变量
static final int DEFAULT_INITIAL_CAPACITY = 16;// 默认容量
static final int MAXIMUM_CAPACITY = 1 << 30;// 最大容量,其实就是2的30次幂
static final float DEFAULT_LOAD_FACTOR = 0.75f;// 默认加载因子
transient Entry[] table;// 存放key-value的数组
transient int size;// Map容器里存放的元素个数
int threshold;// 临界值
final float loadFactor;// 加载因子
transient volatile int modCount;// Map被操作的次数
分析:
treashold 表示Map容量的临界值,当存放的元素超过这个临界值时,Map就会扩容,threashold=capacity * loadFactor,loadFactor 是加载因子,默认为0.75f这是时间和空间的权衡,当loadFactor配置得过大时,内存的利用率比较高,也就是table数组可以存放更多的元素,同时也降低了查询效率,因为hash冲突机会大了,当loadFactor配置得过小时,减少了hash冲突,提高了查询效率,但是内存的利用率低了,table数组很多位置还没存放元素就开始扩容了。
2、构造方法
public HashMap(int initialCapacity, float 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);
// 找到2的n次幂 >= 指定容量值
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);// 计算临界值
table = new Entry[capacity];// 创建容量为capacity的数组
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
分析:
2.1)public HashMap(int initialCapacity, float loadFactor)
从代码中可以看出,HashMap并不是直接使用传入的initialCapactiy来创建数组,而是通过一个算法来取得需要创建的数组大小,这个算法就是找到2的n次幂,使得这个数大于等于initialCapcity,使用这个数来创建存放键值对的数组。
2.2)public HashMap(int initialCapacity)
使用指定的容量和默认的加载因子来创建Map
2.3)public HashMap()
使用默认的容量和默认的加载因子来创建Map
3、put()方法
public V put(K key, V value) {
// 如果key为null,为把key-value存放在table[0]的位置上
if (key == null)
return putForNullKey(value);
// 如果key不为null,则通过“hash算法”计算出key的hash值,并通过hash值计算出该值存储在table数组中的索引位置
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
// 如果该索引位置上存放的不是单独的Entry元素,而是一个Entry链,则遍历该链表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果hash值和key都相同,则新值覆盖旧值,并返回旧值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;// 操作数+1
addEntry(hash, key, value, i);// 将键值对存入数组
return null;
}
put()方法工作流程:
1)如果key为null,则把键值对存到talbe[0]位置上;
2)如果key不为null,则通过“hash算法”计算出key的hash值,并通过hash值计算出该值存储在table数组中的索引位置;
3)如果该索引位置上的元素是空,则直接将键值对存入数组中;
3)如果该索引位置上不为空,并且是一个Entry链,则遍历该链表,如果找到hash值和key都相同,则新值覆盖旧值,并返回旧值;
4)如果存在相同的hash值,但是key不同,这时就形成hash冲突,hash冲突时,会形成一个Entry链,新的元素会存在链表的首位置,并用一个next对象指向下一个元素。
接着我们一步一步分析put里面调用的每一个方法,首先看看putNullForKey()方法的源码:
private V putForNullKey(V value) {
// 获取table[0]位置上的元素,如果该元素是一个Entry链表,则遍历该链表
// 找到key==null的元素,新值替换旧值,返回旧值
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;// 操作数+1
// 如果数组不存在key为null的元素,则存储在table[0]的位置上
addEntry(0, null, value, 0);
return null;
}
接着我们看看hash()源码:
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
这个方法我们可以不用理解细节,只要认为它可以算出一个合理的hash值就好,接着我们看看indexFor()的源码:
static int indexFor(int h, int length) {
return h & (length-1);
}
该方法是通过key的hash值和数组的长度,计算出元素所要存储的索引位置,它能比较均匀的散列在数组的各个索引中,相当于取模,但是取模用到除法,效率比较低,这个通过二进制的位运算,效率高很多。
接着我们看看addEntry()方法源码:
void addEntry(int hash, K key, V value, int bucketIndex) {
// 取得计算出来的索引位置上的元素
Entry<K,V> e = table[bucketIndex];
// 创建新的Entry对象,存入table数组中,并用一个next变量指向原来的元素
// 如果原来为空,则next=null,否则形成一个Entry链表
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
// 添加元素后,如果存放的元素个数超过临界值,则扩容
if (size++ >= threshold)
// 数组扩容以2的倍数扩展
resize(2 * table.length);
}
addEntry() 方法是形成链表的核心代码,需要重点分析下,首先取得table[bucketIndex]上的元素,这个bucketIndex就是上面通过hash算法计算出来的索引值,然后通过传入的hash,key,value构建一个新的Entry对象,存入table[bucketIndex]中,并用一个Entry对象的next变量指向原来的元素,形成链表。
接着我们看看扩容方法resize()的源码:
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
// 如果原来数组的容量已经等于最大值,则临界值直接等于Integer的最大值,并且不再扩容
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
// 根据指定容量创建一个新的数组
Entry[] newTable = new Entry[newCapacity];
// 数组拷贝,把原来的数组内容拷贝到新的数组中(该方法最耗时)
transfer(newTable);
// 新的数组引用指向给table
table = newTable;
// 重新计算临界值
threshold = (int)(newCapacity * loadFactor);
}
扩容时,最耗时的就是数组拷贝,我们看看数组拷贝的 transfer()源码:
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;// 旧的元素引用已经不再使用,置空操作,方便GC回收
do {
Entry<K,V> next = e.next;// 如果数组存放的是Entry链,则取得当前元素的下一个元素
int i = indexFor(e.hash, newCapacity);// 重新计算当前元素在新数组的索引位置
e.next = newTable[i];// 新数组当前索引下如果有值,则赋值给需要添加进来的元素的下一个元素
newTable[i] = e;// 把当前元素存入新的数组中
e = next;// 遍历下一个元素
} while (e != null);
}
}
}
transfer()方法也需要重点分析下,因为它不是一个普通的数组拷贝,元素里存放的不是一个简单的对象,而一个是链表。首先用一个src指向旧的数组引用,遍历旧的数组,遍历过程中取得每个元素,如果旧的数组元素是一个Entry链,则用一个next变量取得当前元素的下一个元素,重新计算当前元素需要存放在新数组中的索引位置,如果新数组该索引位置上有值,则把该索引位置上的元素赋值给需要存放在新数组的元素的next变量上,并把旧数组中的元素存入新的数组中,把旧的数组的元素引用置空,然后遍历下一个元素。从中可以看出数组拷贝之后,原来的链表顺序已经发生了变化,所以说HashMap是不保证顺序的。说得有点绕,需要读者仔细体会这其中的思想,最好亲自上手写一遍。
我们再来看看put的方法声明:
public V put(K key, V value)
从上面的源码分析中,我们知道如果需要存储的key-value在HashMap中不存在,则直接将其存入数组相应的位置中,并返回null;
如果存在相同的hash和相同的key,则会用新值替换旧值,并返回旧值;
如果存在相同的hash,但是key不相同,则会形成链表,新加入的元素会存在链表的表头位置,并返回null;
如果key为null,则会检查数组中第一个元素table[0]是否存在key为null的值,如果有,则新值替换旧值,并返回旧值;如果没有找到key为null,则直接把key存入talbe[0]位置上,并返回null;
这说明put()返回值,要么返回与key关联的旧的值,如果没有关联过,则返回null。
4、get()方法
理解完put()方法之后,再来理解get()方法就容易多了,原来怎么存,现在就怎么取,我们看看get()源码:
public V get(Object key) {
// 如果key为null,则从数组的第一个元素中查找
if (key == null)
return getForNullKey();
// 如果key不为null,则计算key的hash值,并通过hash和数组长度计算出该key在数组中的索引
int hash = hash(key.hashCode());
// 如果该索引下的元素是一个链表,则遍历该链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 如果hash和key都相同,则返回该key对应的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
// 查找不到,则返回null
return null;
}
分析get()方法:
如果key为null,则从table[0]的位置上去查找;
如果key不为null,则通过hash算法计算得出该key在数组中的索引,取得该索引下的元素,如果该索引下存储的是一个链表,则遍历链表,找到hash和key都相同的元素,如果找到,则返回该key对应的value值,如果找不到,则返回null。
接着我们看看getForNullKey()方法的源码:
private V getForNullKey() {
// 取得数组中的第一个元素,如果是链表,则遍历链表,
// 找到key为null的元素,如果有则返回该key对应的value值,否则返回null
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
分析getFroNullKey()方法:
取得数组中的第一个元素,如果元素是一个链表,则遍历链表,找到key等于null的元素,如果找到则返回该key对应的value值,否则返回null。
我们后看看get()方法声明:
public V get(Object key)
从上面的源码中,我们知道如果该HashMap存在映射关键,则返回该key下对应的value值,否则返回null
返回null,还表示该key下对应的映射值就是null。
三、HashMap需要注意的关键点
1.HashMap怎么实现的?
HashMap底层是通过数组和链表来实现。
2.什么是hash冲突,HashMap怎么解决冲突?
当需要存入的key和原来数组中的某个元素的key,存在hash值相同,但是key不相同时,这时就产生了hash冲突;HashMap通过链表来解决冲突,当存在hash冲突时,就把需要存入的元素存在冲突元素的表头上,并用一个next变量指向原来的元素,形成链表。
3.HashMap什么时候扩容,以什么方式扩容?
当HashMap调用put()方法存入元素之后,会检查当前存放的元素个数是否超过临界值,如果超过临界值,则进行扩容,扩容时以原来长度的2倍进行扩容。这个临界值threashold是通过这种方式计算的:threashold = size * loadFactor,其中size是HashMap元素个数,loadFactor是加载因子。从这个公式可以看出,当size不变时,loadFactor越大,临界值threashold就越大,也就是数组可以存放更多的元素,这样提高了内存利用率,但是增加了冲突概率,也就是降低了查询效率;当loadFactor越小,临界值threashold就越小,数组还没使用完就开始扩容,这样提高了查询效率,却浪费了很多内存空间,因为很多元素还没使用数组就开始扩容了。

- 大小: 36.5 KB
分享到:
相关推荐
7. **集合框架**:JDK 1.6的`java.util`包包含了各种集合实现,如ArrayList、LinkedList、HashMap等。源码分析可以揭示它们的内部结构和操作算法,这对于理解性能和选择合适的集合类型很有帮助。 8. **网络编程**:...
JDK1.6的源代码还包含了HotSpot虚拟机的实现,这是一台解释型和即时编译(JIT)的混合型虚拟机。通过分析`src/share/vm`目录下的代码,可以学习到以下内容: - 解释器:理解Java字节码如何被解释执行。 - JIT编译器...
Java JDK1.6 API中文手册是Java开发者的重要参考资料,它详尽地解释了JDK1.6版本中的各种类库、接口、方法和异常等核心组件。这份文档为中文用户提供了方便,使得开发者能更直观地理解Java语言的底层机制和编程规范...
JDK1.6作为历史版本,虽然已被更新的JDK版本所替代,但它仍然具有重要的学习价值,尤其对于理解Java语言的底层机制和优化实践而言。本文将主要围绕JDK1.6的源码展开,探讨其中的关键组件和设计思想。 1. **核心类库...
一、JDK 1.6源码分析 1. **核心类库**:Java的核心类库位于`java`、`javax`、`org`等包下,包括了各种基础数据类型、集合框架、网络编程、I/O流、多线程、反射、日期时间处理、国际化等模块。例如,`java.util`包中...
通过深入研究JDK1.6的源码,开发者不仅可以提升自己的编程技巧,还能掌握更底层的技术,从而优化程序性能,解决复杂问题,并更好地利用Java平台的优势。同时,对于想要成为Java专家或者从事JVM优化、虚拟机开发的人...
API(Application Programming Interface)是一组预定义的函数、类、对象和常量,开发者可以调用这些接口来实现特定的功能,而无需了解底层的实现细节。 在JDK 1.6版本中,包含了丰富的Java SE(标准版)平台核心...
API(Application Programming Interface)是一组预定义的函数、类、对象和常量,开发者可以使用它们来实现特定功能,而无需了解底层实现的细节。在Java中,API主要由核心库和扩展库组成,这些库包含了处理I/O、网络...
**Java JDK 1.6 源代码解析** 在编程领域,Java JDK(Java Development Kit)是开发和运行Java应用程序的基础。JDK 1.6是Oracle公司发布的一个早期版本,它包含了Java编译器、Java运行时环境、类库以及开发者工具。...
林信良的JDK学习笔记中可能详细解析了这些特性的使用方法和底层实现,通过深入源代码,我们可以学习到如何有效地利用这些特性进行编程,同时也能理解Java在设计上的考量和优化策略。 此外,阅读和分析JDK源代码是...
4. **并发与多线程**:JDK 1.6.0在并发编程方面有许多增强,如并发工具类(java.util.concurrent)的引入,它们基于高级并发原语,如锁、信号量、原子变量等。这部分源代码值得深入学习,以提升多线程编程的能力。 ...
JDK 1.6版本是Java历史上的一个重要里程碑,它引入了许多新特性,提升了性能,并对API进行了扩展和完善。 参考文档中涵盖了以下主要知识领域: 1. **基础类库**:包括集合框架、IO流、多线程、网络编程、反射、...
HashSet是Java编程语言中的一种集合类,它是一个不包含重复元素的集合,其内部实现基于HashMap。HashSet不保证元素的顺序,允许存储null元素,并且是非同步的,这意味着在多线程环境下,如果需要保证线程安全,需要...
- 基于`HashMap`实现,使用`HashMap`存储元素。 - 特点:插入、删除和查找速度非常快,但不保证元素的顺序。 - **LinkedHashSet** - `HashSet`的子类,内部通过`LinkedHashMap`实现。 - 特点:保持元素的插入...
HashMap和TreeMap则对应Map接口,前者基于哈希表,后者基于红黑树,保证了快速查找和排序。 三、多线程 Java 1.6在多线程方面提供了Thread类和Runnable接口,使得并发编程成为可能。线程的创建、启动、同步和终止都...
这个"Java 中文 API.zip"文件提供了Java 1.8 jdk的中文版API文档,同时附带了jdk1.6和Java SE的文档,这对于中文环境下的学习者来说尤其方便,因为语言障碍将不再是理解和掌握Java技术的阻碍。 Java API主要分为几...