H5W3
当前位置:H5W3 > java > 正文

【Java】深入解析HashMap

导言

常见的逻辑数据结构有: 数组、栈、队列、链表、树、图、散列表、堆。本文的核心就是讲散列表(Hash表)。以下首先介绍Hash相关知识,再以jdk1.8中的HashMap做一个源码解读。

Hash表

什么是Hash表

它最大的特点就是可以快速实现查找、插入和删除。因为它的快速性,常被广大程序员拿来处理大数据问题。

为什么要Hash表

常和Hash放在一起选型考虑的有数组、链表,数组增删困难、队列寻址困难。而Hash就很好的结合两者的优点,使用自定义的下标索引HashCode,加快寻址、插入、删除的操作,本质上就是一个优化的k-v存储。

Hash表核心原理

核心概念

Hash表

散列表。根据关键值(key)访问其value(真正的数据实体),也就是最常用到的Map。

hash函数

哈希函数是Hahs表的映射函数,它可以把任意长度的输入变换成固定长度的输出,该输出就是哈希值。该哈希值就是该k-v存储的key。设计出一个简单、均匀、存储利用率高的散列函数是散列技术中最关键、最重要的问题。

一句话总结: hash函数是为了快速确定数据所在的"下标"

常见的hash映射策略有:

  1. 直接定址法:取关键字或关键字的某个线性函数值为散列地址。
  2. 数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。
  3. 平方取中法:取关键字平方后的中间几位为哈希地址。

  4. 折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
  5. 随机数法
  6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

常见冲突解决方法

理想情况下每个Key都被分配到一个唯一的,但大多数的Hash函数都不能支持这一要求,如果要支持则每次分配新的key时需要知道旧的Keys的值,一般来说这并不值的。因此我们需要处理散列冲突。

常见的Hash冲突有如下几种:

开放地址法(再散列法)

开放地址法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1) 其中,m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1,称线性探测再散列。如果di取1,则每次冲突之后,向后移动1个位置.如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2),称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

再哈希法

当发生冲突时,使用第二个、第三个哈希函数…计算地址,直到无冲突时。缺点:计算时间增加。比如上面第一次按照姓首字母进行哈希,如果产生冲突可以按照姓字母首字母第二位进行哈希,再冲突,第三位,直到不冲突为止.这种方法不易产生聚集,但增加了计算时间。

链地址法(拉链法)

将所有关键字为同义词的记录存储在同一线性链表中.基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

java HashMap原理浅析

一张图表示(图片来源):

<img alt=”图1″ />

java hashMap就是基于的“链地址法”,链地址法中的“同义词链表”在jdk hashmap中通过java.util.HashMap.Node构成链表表示,Node源码主要内容如下所示(暂不考虑红黑树节点: TreeNode):

static class Node<K,V> implements Map.Entry<K,V> {
//省略构造函数和get、set方法,以及其他例如Hash、equals的方法
final int hash;
final K key;
V value;
Node<K,V> next;
}

所有的桶元素存储在transient Node<K,V>[] table;这里~源码396行~。jdk1.8中使用(n - 1) & hash来获取桶的下标位置~此处的与操作逻辑上等价于%~,如果冲突了则在加在其链表尾。

Node的hash值来自于:

static final int hash(Object key) {
int h;
// 从此可以看错HashMap支持key为null的对象
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash和key的关系: hash值就是key的hashcode经过一个位运算得到。ps: 对于java.lang.Object#hashCode,该方法是专门用来支持hash数据结构的。

hash值决定该value在哪个桶,key保证在全局上唯一(桶链表上更是唯一)。

java HashMap核心AIP

略过各种便于开发使用的api不谈,java中的HashMap就是个支持增、删、查的散列表。

先从最简单的查开始。所有的查都是调用方法getNode实现的:

final HashMap.Node<K, V> getNode(int hash, Object key) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> first, e;
int n;
K k;
// 如果table有元素则使用hash索引到对应的Node
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 如果第一个就是则直接返回
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果第一个不是:
if ((e = first.next) != null) {
// 红黑树则走红黑树getNode逻辑
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
// 非红黑树则走链表逻辑: 遍历链表
do {
//遍历找到了,返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果找不到则返回null
return null;
}

增的核心就是java.util.HashMap#putVal这个方法:

// hash: 用于定位桶的位置,
// evict: 当table处于初始化时为false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent/*存在则添加*/,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 不存在则初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果对应的hashMap桶不存在则直接新建一个桶
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果对应的桶(也就是p)存在
else {
Node<K,V> e; K k;
// 桶数组上的node.key和要put的key相同=>将这个桶node赋值到e上
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
/* 不是桶上的node*/
// 如果是红黑树结构走红黑树putVal逻辑
else if (p instanceof TreeNode)
// 和链表大同小异,暂且不表
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 普通链表结构的走这个逻辑
else {
// 遍历桶链表,将放到链表尾
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 该链表大于8了
treeifyBin(tab, hash); // 可以简单理解成"尝试"转为红黑树,当tab太短时就不转
break;
}
// 如果在该桶里找到了对应key,退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//当执行到这里时,e就是key对应的node(不管是查出来的还是new出来的)
if (e != null) {
V oldValue = e.value;
// 替换旧数据
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // linkHashMap相关,暂时不管
return oldValue;
}
}
// 无关代码
/*   ++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);*/
return null;
}

final HashMap.Node<K, V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, index;
// 存在对应的桶
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
HashMap.Node<K, V> node = null, e;
K k;
V v;
// key相同了=>找出要删除的Node=>赋值给node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// key不同则遍历查找(树查找或链表查找)
else if ((e = p.next) != null) {
// 树查找
if (p instanceof HashMap.TreeNode)
node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
// 链表查找
else {
// 如果走链表查找分支,则p就不是桶里的Node了,并且p!=node
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// node不为null表示之前的操作找到了对应的key
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 树的删除
if (node instanceof HashMap.TreeNode)
((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
//node就是桶中的那个node
else if (node == p)
tab[index] = node.next;
// 链表中的节点的删除
else
p.next = node.next;
/* 无关代码先忽略
++modCount;
--size;
afterNodeRemoval(node);*/
return node;
}
}
// 不存在对应的桶或桶里没有数据
return null;
}

其他

快速失败机制 Fail-Fast

上文中的modCount字段就与此有关,当用户通过迭代器访问HashMap时,会对比这个值,如果不符合预期就会抛出异常ConcurrentModificationException;

//java.util.HashMap.EntrySet#forEach
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}

总结

无论是增、删、查,HashMap的查询过程都是先判断hash,在判断key。如果key相同则hash一定相同(因为hash就是key的hashCode)。但是,当hash相同时,key不一定相同,因为hash相同知识表示他们在一个桶链表上,但不一定是同一个key。

所以那个常见的问题: 重写hashCode()和重写equals()的关系可以这样理解(结论是一起重写):

  1. 重写hashCode确定桶下标,重写equals确定全局唯一
  2. 重写了equals一定要重写hashCode方法,因为要保证两个equals的对象hashCode也一样(保证全局唯一),否则的话可能插入两个一样(equals)的对象
  3. 重写了hashCode一定要重写equals,因为不在同一个的桶链表上(hash不同)的一定不equals。

参考文章

  1. 数据结构与算法: hashMap
  2. HashMap实现原理
  3. 为什么重写equals同时要重写hashCode?

本文地址:H5W3 » 【Java】深入解析HashMap

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址