文档章节

5.Java 集合 - HashMap

夕阳晒裤衩
 夕阳晒裤衩
发布于 2017/02/24 18:06
字数 1723
阅读 29
收藏 0
点赞 0
评论 0

#5.Java 集合 - HashMap

@(Java Utils)

##基本概念

HashMap 实现了 Map 接口,继承自 AbstractMap。它接受 Map 接口定义的键映射到值的规则。

HashMap 内部通过维护着一个哈希表来存储元素。

HashMap 是非线程安全的。

HashMap 接受 key 为 null 的键值对,并统统把它们存放在哈希表的第一个位置。


##内部构造

###1.Entry

Entry,即节点,是 HashMap 中一个重要的静态内部类,它由一个键值对(k,v)、指针域(next)、哈希值(hash)构成,不同的节点可组成一个单向链表。

static class Entry<K, V> implements Map.Entry<K, V> {
	final K key; // 键
	V value; // 值
	Entry<K, V> next; // 下一个节点
	int hash; // 哈希值
	
	// 构造函数
	Entry(int h, K k, V v, Entry<K, V> n) {
		key = k; 
		value = v;
		hash = h;
		next = n;
	}

	// 省略部分代码...
}

根据代码,可得结构图如下:

输入图片说明


###2.构造函数

先来看 HashMap 内部几个重要的成员变量:

// 数组(由节点组成),即哈希表
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;

// 空的哈希表
static final Entry<?, ?>[] EMPTY_TABLE = {};

// 负载因子,表示哈希表的饱和程度
final float loadFactor;

// 临界值,哈希表的元素数量超过该值时需要做扩容操作
int threshold;

明白了这个几个成员变量的概念后,再来看它的构造函数:

// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 默认容量(2^4 =16)、最大容量(2^30)
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
static final int MAXIMUM_CAPACITY = 1 << 30;

public HashMap() {
	this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity) {
	this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0){
		//抛出异常...
	}	
	if (initialCapacity > MAXIMUM_CAPACITY){
		initialCapacity = MAXIMUM_CAPACITY;
	}	
	if (loadFactor <= 0 || Float.isNaN(loadFactor)){
		//抛出异常...
	}
	
	this.loadFactor = loadFactor;

	// 关键 -> 临界值 = 初始容量
	threshold = initialCapacity;
	
	// 空方法,留给子类实现
	init();
}

观察它的构造函数,HahsMap 在被创建时需要指定两个变量:初始容量、加载因子。若不指定时,默认会构建一个初始容量为 16,加载因子为 0.75 的哈希表。

关于哈希表,现在可以知道的是它是由多个单向链表组成的数组,根据描述可以绘制下图:

输入图片说明


##操作方法

###1.扩容检测

由于 HashMap 由哈希表组成, 同样有着容量固定的缺陷,所以在每次添加操作之前都需要进行扩容检测,以保证整个哈希表的元素数量不会过于饱和

private void inflateTable(int toSize) {
	
	int capacity = roundUpToPowerOf2(toSize);

	threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
	table = new Entry[capacity];
	initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
	return number >= MAXIMUM_CAPACITY ? 
		MAXIMUM_CAPACITY : (number > 1) ? I
			nteger.highestOneBit((number - 1) << 1) : 1;
}

final boolean initHashSeedAsNeeded(int capacity) {
	boolean currentAltHashing = hashSeed != 0;
	boolean useAltHashing = sun.misc.VM.isBooted() && 
		(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
	boolean switching = currentAltHashing ^ useAltHashing;
	if (switching) {
		hashSeed = useAltHashing ? 
			sun.misc.Hashing.randomHashSeed(this) : 0;
	}
	return switching;
}
void resize(int newCapacity) {
	Entry[] oldTable = table;
	int oldCapacity = oldTable.length;
	if (oldCapacity == MAXIMUM_CAPACITY) {
		threshold = Integer.MAX_VALUE;
		return;
	}

	Entry[] newTable = new Entry[newCapacity];
	transfer(newTable, initHashSeedAsNeeded(newCapacity));
	table = newTable;
	threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	for (Entry<K, V> e : table) {
		while (null != e) {
			Entry<K, V> next = e.next;
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			}
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i];
			newTable[i] = e;
			e = next;
		}
	}
}

static int indexFor(int h, int length) {
	return h & (length - 1);
}

###2.添加(修改)操作

在 HashMap 中执行添加、修改操作都通过 put 方法来实现,下面来看它的源码:

public V put(K key, V value) {
	// 第一次添加时,哈希表为空则进行扩容操作
	if (table == EMPTY_TABLE) {
		inflateTable(threshold);
	}
	
	// 判断 key 是否为空,为空则添加到数组的第一个
	if (key == null){
		return putForNullKey(value);
	}
	
	// 根据 key 的哈希值计算其要放置的数组位置	
	int hash = hash(key);
	int i = indexFor(hash, table.length);
	
	// 遍历该位置上的链表
	for (Entry<K, V> e = table[i]; e != null; e = e.next) {
		Object k;
		
		// 判断是否存在相同节点,存在则执行修改操作
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			V oldValue = e.value;
			e.value = value;
			
			// 空方法,留给子类实现
			e.recordAccess(this);
		
			return oldValue;
		}
	}

	modCount++;

	// 不存在相同节点,执行添加操作
	addEntry(hash, key, value, i);
	return null;
}

private V putForNullKey(V value) {
	// 关键 -> 当 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++;
	addEntry(0, null, value, 0);
	return null;
}

分析代码, HashMap 的 put 方法的执行过程如下:

  • 判断哈希表是否为空,为空则进行扩容操作
  • 判断要添加的键值对 key 是否为 null,为空则放置到数组第一个位置的链表上
  • 不为空则进行计算键值对的位置,遍历该位置的链表,执行添加或修改操作。

修改操作在上面已经介绍过,具体来看下添加操作:

void addEntry(int hash, K key, V value, int bucketIndex) {
	if ((size >= threshold) && (null != table[bucketIndex])) {
		// 扩充容量
		resize(2 * table.length);

		// 计算新的数组位置
		hash = (null != key) ? hash(key) : 0;
		bucketIndex = indexFor(hash, table.length);
	}
	
	// 创建新节点,并插入链表
	createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
	// 取得数组 bucketIndex 位置上链表的头结点
	Entry<K, V> e = table[bucketIndex];
	
	// 将新加入的节点设置为头结点
	table[bucketIndex] = new Entry<>(hash, key, value, e);
	size++;
}

整个过程如下图所示:

输入图片说明


###3.删除操作

在 HahsMap 中的删除操作只有删除指定元素一种:

public V remove(Object key) {
	Entry<K, V> e = removeEntryForKey(key);
	return (e == null ? null : e.value);
}

final Entry<K, V> removeEntryForKey(Object key) {
	// 判断哈希表是否为空,为空返回 null
	if (size == 0) {
		return null;
	}

	// 找到该节点所在链表的数组位置,并取得链表的头节点
	int hash = (key == null) ? 0 : hash(key);
	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;
		Object k;

		// 判断是否存在该节点
		if (e.hash == hash && 
			((k = e.key) == key || (key != null && key.equals(k)))) {
			
			modCount++;
			size--;

			// 判断该节点是否是链表的头节点
			if (prev == e){
				// 设置其下个节点设置为新的头节点
				table[i] = next;
			}else{
				// 修改前节点的指针
				prev.next = next;
			}
			
			// 空方法,留给子类实现	
			e.recordRemoval(this);
			return e;
		}

		// 准备下一轮遍历
		prev = e;
		e = next;
	}

	return e;
}

分析代码,整个过程跟添加操作大同小异,具体如下:

  • 获取指定节点索引位置。
  • 遍历索引位置的单链表。
  • 存在相同的节点能移除并返回该节点 ,不存在返回 null

输入图片说明


###4.查询操作

这里介绍下 HashMap 查询时常用的 get 方法:

public V get(Object key) {

	if (key == null){
		return getForNullKey();
	}
	
	Entry<K, V> entry = getEntry(key);
	
	return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
	if (size == 0) {
		return null;
	}
	for (Entry<K, V> e = table[0]; e != null; e = e.next) {
		if (e.key == null){
			return e.value;
		}	
	}
	return null;
}

final Entry<K, V> getEntry(Object key) {
	if (size == 0) {
		return null;
	}

	int hash = (key == null) ? 0 : hash(key);
	for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
		Object k;
		if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
			return e;
		}	
	}
	return null;
}

这里只贴出源码,不再分析,大致过程如下:

  • 判断 key 是否为空,为空则在数组第一个位置的链表上查询
  • 判断哈希表是否为空,为空返回 null
  • 找到指定位置的链表,遍历链表查询指定元素

© 著作权归作者所有

共有 人打赏支持
夕阳晒裤衩
粉丝 3
博文 15
码字总数 18485
作品 0
天津
程序员
5.Java基础复习----Map

1.Map java.util.Map<K,V> interface 实现Map接口的类用来存储键-值 对; 可以存储null键 Map类中存储的键 -- 值 对通过键来标识,所以键值不能重复 public int size();集合大小 public boo...

baibuxiha ⋅ 2016/01/24 ⋅ 0

再分享几道面试题目,学习学习

1.面向对象对象的特征。重写与重载的区别。 2.jsp内置对象及作用。 3.HashMap与Hashtable的区别,Vector与ArrayList的区别。 4.application的特点,与session的的联系和区别。 5.java如何调用...

Baclk5 ⋅ 2014/08/05 ⋅ 5

8张图理解Java

理解Java 1.字符串不变性 2.equals()方法、hashCode()方法的区别 HashCode被设计用来提高性能。equals()方法与hashCode()方法的区别在于: 3.Java异常类的层次结构 图中红色部分为受检查异常...

Panda_Jerry ⋅ 2017/10/31 ⋅ 0

115个Java面试题和答案——终极列表(上)

本文我们将要讨论Java面试中的各种不同类型的面试题,它们可以让雇主测试应聘者的Java和通用的面向对象编程的能力。下面的章节分为上下两篇,第一篇将要讨论面向对象编程和它的特点,关于Jav...

LCZ777 ⋅ 2014/04/23 ⋅ 0

day18-----------集合框架(map集合)(传智视频)

Map集合的获取功能测试 package cn.itcast_01; import java.util.HashMap;import java.util.Map; /* * 作为学生来说,是根据学号来区分不同的学生的,那么假设我现在已经知道了学生的学号,我...

萧小蚁 ⋅ 2016/02/16 ⋅ 0

Map集合以及Collections集合工具类

一、Collection集合主要特点与Map集合的区别 Collection: 单列集合;有两个子接口 List集合元素是有序的,可以重复的 Set集合元素是无序的,不可以重复 List:元素可重复,有序 ArrayList:底层...

走了丶 ⋅ 2017/08/07 ⋅ 0

HashMap和Hashtable的区别

HashMap和Hashtable的比较是Java面试中的常见问题,用来考验程序员是否能够正确使用集合类以及是否可以随机应变使用多种思路解决问题。HashMap的工作原理、ArrayList与Vector的比较以及这个问...

LCZ777 ⋅ 2014/03/29 ⋅ 0

JAVA 115个面试题及个人部分(1)

本文我们将要讨论Java面试中的各种不同类型的面试题,它们可以让雇主测试应聘者的Java和通用的面向对象编程的能力。下面的章节分为上下两篇,第一篇将要讨论面向对象编程和它的特点,关于Jav...

ForingY ⋅ 2016/03/31 ⋅ 0

【转】115个Java面试题和答案——终极列表

本文我们将要讨论Java面试中的各种不同类型的面试题,它们可以让雇主测试应聘者的Java和通用的面向对象编程的能力。下面的章节分为上下两篇,第一篇将要讨论面向对象编程和它的特点,关于Jav...

一只死笨死笨的猪 ⋅ 2014/09/30 ⋅ 0

java面试热点:集合框架(二)

Set接口 Set接口与List接口的重要区别就是它不支持重复的元素,至多可以包含一个null类型元素。Set接口定义的是数学意义上的“集合”概念。 Set接口主要定义了以下方法: 关于set家族,有一下...

神秘的寇先森 ⋅ 2017/12/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部