文档章节

5.Java 集合 - HashMap

oxf
 oxf
发布于 2017/02/24 18:06
字数 1723
阅读 36
收藏 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
  • 找到指定位置的链表,遍历链表查询指定元素

© 著作权归作者所有

共有 人打赏支持
上一篇: 1.JUC - 概述
oxf

oxf

粉丝 4
博文 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
14
0
再分享几道面试题目,学习学习

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

Baclk5
2014/08/05
564
5
8张图理解Java

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

Panda_Jerry
2017/10/31
0
0
Map集合以及Collections集合工具类

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

走了丶
2017/08/07
0
0
java面试热点:集合框架(二)

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

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

没有更多内容

加载失败,请刷新页面

加载更多

Kubernetes里的secret最基本的用法

Secret解决了密码、token、密钥等敏感数据的配置问题,使用Secret可以避免把这些敏感数据以明文的形式暴露到镜像或者Pod Spec中。 Secret可以以Volume或者环境变量的方式使用。 使用如下命令...

JerryWang_SAP
昨天
1
0
可重入锁和非可重入锁

广义上的可重入锁指的是可重复可递归调用的锁,在外层使用锁之后,在内层仍然可以使用,并且不发生死锁(前提得是同一个对象或者class),这样的锁就叫做可重入锁。 可重入锁: ReentrantLoc...

狼王黄师傅
昨天
1
0
2018-11-20学习笔记

1. python数据类型: 给变量赋值什么样的值,变量就是什么样的类型 给变量赋值整数,变量就是整数类型 给变量赋值字符串,变量就是字符串类型 123 和“123”一样吗? 在python中 单引号 与双...

laoba
昨天
1
0
使用 React 和 Vue 创建相同的应用,他们有什么差异?

在工作中应用 Vue 之后,我对它有了相当深刻的理解。 不过,俗话说「外国的月亮比较圆」,我好奇「外国的」 React 是怎么样的。 我阅读了 React 文档并观看了一些教程视频,虽然它们很棒,但...

阿K1225
昨天
2
0
2天闭门培训|以太坊智能合约从入门到实战(北京)

2天培训 16个课时 探寻技术原理,精通以太坊智能合约开发 以太坊智能合约是现在应用的最广泛的区块链应用开发方式,HiBlock区块链社区针对以太坊智能合约的学习特别推出2天闭门研修班,通过2...

HiBlock
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部