`
吖龙Sam
  • 浏览: 21172 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

基于JDK1.6的HashMap底层实现与分析

    博客分类:
  • Java
阅读更多

最新仔细看了一遍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
分享到:
评论

相关推荐

    jdk1.6 源码jdk1.6 源码

    7. **集合框架**:JDK 1.6的`java.util`包包含了各种集合实现,如ArrayList、LinkedList、HashMap等。源码分析可以揭示它们的内部结构和操作算法,这对于理解性能和选择合适的集合类型很有帮助。 8. **网络编程**:...

    JDK1.6 源代码

    JDK1.6的源代码还包含了HotSpot虚拟机的实现,这是一台解释型和即时编译(JIT)的混合型虚拟机。通过分析`src/share/vm`目录下的代码,可以学习到以下内容: - 解释器:理解Java字节码如何被解释执行。 - JIT编译器...

    Java_JDK1.6api手册中文版

    Java JDK1.6 API中文手册是Java开发者的重要参考资料,它详尽地解释了JDK1.6版本中的各种类库、接口、方法和异常等核心组件。这份文档为中文用户提供了方便,使得开发者能更直观地理解Java语言的底层机制和编程规范...

    jdk1.6源码

    JDK1.6作为历史版本,虽然已被更新的JDK版本所替代,但它仍然具有重要的学习价值,尤其对于理解Java语言的底层机制和优化实践而言。本文将主要围绕JDK1.6的源码展开,探讨其中的关键组件和设计思想。 1. **核心类库...

    jdk1.6 源码(包括sun公司实现的代码)

    一、JDK 1.6源码分析 1. **核心类库**:Java的核心类库位于`java`、`javax`、`org`等包下,包括了各种基础数据类型、集合框架、网络编程、I/O流、多线程、反射、日期时间处理、国际化等模块。例如,`java.util`包中...

    JDK1.6源码 JAVA

    通过深入研究JDK1.6的源码,开发者不仅可以提升自己的编程技巧,还能掌握更底层的技术,从而优化程序性能,解决复杂问题,并更好地利用Java平台的优势。同时,对于想要成为Java专家或者从事JVM优化、虚拟机开发的人...

    JDK_API_1.6中文版

    API(Application Programming Interface)是一组预定义的函数、类、对象和常量,开发者可以调用这些接口来实现特定的功能,而无需了解底层的实现细节。 在JDK 1.6版本中,包含了丰富的Java SE(标准版)平台核心...

    JDK_1.6帮助文档API

    API(Application Programming Interface)是一组预定义的函数、类、对象和常量,开发者可以使用它们来实现特定功能,而无需了解底层实现的细节。在Java中,API主要由核心库和扩展库组成,这些库包含了处理I/O、网络...

    source jdk

    **Java JDK 1.6 源代码解析** 在编程领域,Java JDK(Java Development Kit)是开发和运行Java应用程序的基础。JDK 1.6是Oracle公司发布的一个早期版本,它包含了Java编译器、Java运行时环境、类库以及开发者工具。...

    jdk学习笔记

    林信良的JDK学习笔记中可能详细解析了这些特性的使用方法和底层实现,通过深入源代码,我们可以学习到如何有效地利用这些特性进行编程,同时也能理解Java在设计上的考量和优化策略。 此外,阅读和分析JDK源代码是...

    jdk-1.6.0 源代码 三

    4. **并发与多线程**:JDK 1.6.0在并发编程方面有许多增强,如并发工具类(java.util.concurrent)的引入,它们基于高级并发原语,如锁、信号量、原子变量等。这部分源代码值得深入学习,以提升多线程编程的能力。 ...

    java参考文档

    JDK 1.6版本是Java历史上的一个重要里程碑,它引入了许多新特性,提升了性能,并对API进行了扩展和完善。 参考文档中涵盖了以下主要知识领域: 1. **基础类库**:包括集合框架、IO流、多线程、网络编程、反射、...

    HashSet详解和使用示例_动力节点Java学院整理

    HashSet是Java编程语言中的一种集合类,它是一个不包含重复元素的集合,其内部实现基于HashMap。HashSet不保证元素的顺序,允许存储null元素,并且是非同步的,这意味着在多线程环境下,如果需要保证线程安全,需要...

    Java集合常见面试题总结(上)-JavaGuide面经思维导图总结

    - 基于`HashMap`实现,使用`HashMap`存储元素。 - 特点:插入、删除和查找速度非常快,但不保证元素的顺序。 - **LinkedHashSet** - `HashSet`的子类,内部通过`LinkedHashMap`实现。 - 特点:保持元素的插入...

    JDK_API_1_6_zh_CN.zip

    HashMap和TreeMap则对应Map接口,前者基于哈希表,后者基于红黑树,保证了快速查找和排序。 三、多线程 Java 1.6在多线程方面提供了Thread类和Runnable接口,使得并发编程成为可能。线程的创建、启动、同步和终止都...

    Java 中文 API.zip

    这个"Java 中文 API.zip"文件提供了Java 1.8 jdk的中文版API文档,同时附带了jdk1.6和Java SE的文档,这对于中文环境下的学习者来说尤其方便,因为语言障碍将不再是理解和掌握Java技术的阻碍。 Java API主要分为几...

Global site tag (gtag.js) - Google Analytics