Map 大家族的那点事儿 ( 4 ) :HashMap

原标题:Map 大家族的那点事儿 ( 4 ) :HashMap

HashMap概述

HashMap实现了Map接口,我们常用HashMap进行put和get操作读存键值对数据。下面介绍基于jdk1.8深入了解HashMap底层原理。

HashMap实际是一种“数组 链表”数据结构。在put操作中,通过内部定义算法寻止找到数组下标,将数据直接放入此数组元素中,若通过算法得到的该数组元素已经有了元素(俗称hash冲突,链表结构出现的实际意义也就是为了解决hash冲突的问题)。将会把这个数组元素上的链表进行遍历,将新的数据放到链表末尾。

图片 1

存储数据的对象

static class Node<K,V> implements Map.Entry<K,V> {

final int hash;

final K key;

V value;

Node<K,V> next;

}

我们从jdk1.8源代码看出存储对象Node实际是实现Map.Entry对象接口。

hash:通过hash算法的出来的值。hash值的算法我们看下HashMap源代码的实现

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode ^ (h >>> 16);

}

不同的数据类型的hashCode计算的方法不一样,我们看下String和Integer两种数据类型的hashCode算法

String.hashCode()

public int hashCode() {

int h = hash;

if (h == 0 && value.length > 0) {

char val[] = value;

for (int i = 0; i < value.length; i ) {

h = 31 * h val[i];

}

hash = h;

}

return h;

}

通过将字符串转换成char数组,使用公式s[0]*31^ s[1]*31^ ... s[n-1]进行计算得出最后的值。val[i]值是对应字符的ASCII值.在看到这里的时候,这里为什么使用了一个31作为相乘因子(能为啥,还不是为了性能考虑,那为什么使用31性能能得到优化呢),这里可以延伸讨论。

Integer.hashCode()

public static int hashCode(int value) {

return value;

}

直接返回值.

key:存储数据的key

value:存储数据的value

next:下一个数据,出现哈希冲突时,该数组元素会出现链表结构,会使用next指向链表中下一个元素对象

链表结构导致的问题

通过哈希算法从寻止上能够高效的找到对应的下标,但是随着数据的增长,哈希冲突碰撞过多。在寻找数据上,找到该来链表,会通过遍历在寻找对应数据,如此将会使得get数据效率越来越低。在jdk1.8中,链表元素数量大于等于8将会重组该链表结构形成为“红黑树结构”,这种结构使得在hash冲突碰撞过多情况下,get效率比链表的效率高很多。

HashMap put存储数据是如何处理的

HashMap有几个重要的变量

transient Node<K,V>[] table;

int threshold;

final float loadFactor;

int modCount;

int size;

table:存储数组的变量,初始长度为16通过源代码看出在第一次进行resize扩容(java是静态语言,在定义数组初始化时,需要定义数组的长度,在map数据增长后,内部机制会进行重新定义一个数组做到扩容的操作)初始化时,会将默认静态变量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;复制代码

赋给数组长度进行初始化。

loadFactor:数据的增长因子,默认为0.75。在进行扩容操作会使用到。

threshold:允许的最大的存储的元素数量,通过length数组长度*loadFactor增长因子得出

modCount:记录内部结构发生变化的次数,put操作以及其他...

size:实际存储的元素数量

put的流程

直接通过源代码分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

// 判断数组是否为空,长度是否为0,是则进行扩容数组初始化

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize.length;

// 通过hash算法找到数组下标得到数组元素,为空则新建

if ((p = tab[i = & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

// 找到数组元素,hash相等同时key相等,则直接覆盖

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals

e = p;

// 该数组元素在链表长度>8后形成红黑树结构的对象

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

else {

// 该数组元素hash相等,key不等,同时链表长度<8.进行遍历寻找元素,有就覆盖无则新建

for (int binCount = 0; ; binCount) {

if ((e = p.next) == null) {

// 新建链表中数据元素

p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

// 链表长度>=8 结构转为 红黑树

treeifyBin(tab, hash);

break;

}

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals

break;

p = e;

}

}

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess;

return oldValue;

}

}

modCount;

if ( size > threshold)

resize();

afterNodeInsertion;

return null;

}

便于理解,花了一下图。如下图示(画工不是很好,见谅见谅)

图片 2

下图是一位大神级别画的图,引用一下便于理解

图片 3

1、首选判断table是否为空,数组长度为空,将会进行第一次初始化。(在实例化HashMap是,并不会进行初始化数组)

2、进行第一次resize()扩容之后。开始通过hash算法寻址找到数组下标。若数组元素为空,则创建新的数组元素。若数组元素不为空,同时hash相等,key不相等,同时不是TreeNode数据对象,将遍历该数组元素下的链表元素。若找到对应的元素,则覆盖,如果没有找到,就新建元素,放入上一个链表元素的next中,在放入元素之后,如果条件满足"链表元素长度>8",则将该链表结构转为"红黑树结构"。

3、找到对应的数组元素或者链表元素,同时创建新的数据元素或者覆盖元素之后。如果条件满足元素大小size>允许的最大元素数量threshold,则再一次进行扩容操作。每次扩容操作,新的数组大小将是原始的数组长度的两倍。

4、put操作完成。

调用put方法示例

下面通过使用例子介绍这个过程

HashMap<Integer, String> hashMap = new HashMap<Integer, String>;// 1

int a1 = 1;

int a2 = 2;

int a3 = 5;

System.out.println(String.valueOf " " String.valueOf " " String.valueOf);// 1 2 1 数组下标

hashMap.put;// 2

hashMap.put;// 3

hashMap.put;// 4

1、创建了一个HashMap对象,初始化initialCapacity为4,增长因子为0.75。threshold初始化为4

2、进行了第一次put,因为table为空,进行了第一次resize()扩容操作,数组进行初始化,默认为16. threshold变为3。同时通过hash算法(数组长度n-1 & hash)即为1。

3、第二次put操作,同时获取数组下标为2,此时数组下标为2当前没有数组元素,则直接创建数据元素放入

4、第三次put操作,得到数组下标为1已经有了一个数组元素。同时我们知道存储数据的Node对象中又一个next,则新的此时的数据元素放入上一个链表中next为空的Node中的next中。

形成了如下图的数据结构

图片 4

结论:通过hash算法进行计算的出来的数组下标,有一定概率会导致hash冲突,那在一个数组元素中,存在hash值一样的key,key却不相等。为了解决这一个hash冲突问题,使用了链表结构进行处理。

HashMap扩容resize()

java是静态方法,在数组进行初始化时,必须给一个数组长度。HashMap定义默认的数组长度为16。条件满足元素size>允许的最大元素数量threshold。则进行扩容。一般来说,在put操作中,HashMap至少进行了一次扩容。

我们在原有的示例加入如下

int a4 = 6;

hashMap.put;

形成了新的结构,如下图

图片 5

放入了2:2的next中,此时size=4,threshold>3,条件满足size>threshold,进行扩容resize()操作

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table;

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap, newThr = 0;

if (oldCap > 0) {

// 超过最大限制,不进行扩容

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

// 进行原始长度*2扩容

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

// 第一次初始化

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

else { // zero initial threshold signifies using defaults

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

// 第一次初始化

if (newThr == 0) {

float ft = newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ?

ft : Integer.MAX_VALUE);

}

// 新的最大允许元素数量值

threshold = newThr;

@SuppressWarnings({"rawtypes","unchecked"})

// 新的数组

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab;

if (oldTab != null) {

// 遍历老数组

for (int j = 0; j < oldCap; j) {

Node<K,V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

// 直接按照原始索引放入新数组中

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

else if (e instanceof TreeNode)

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

else { // preserve order

// 遍历链表

Node<K,V> loHead = null, loTail = null;

Node<K,V> hiHead = null, hiTail = null;

Node<K,V> next;

do {

next = e.next;

// 放入原索引

if ((e.hash & oldCap) == 0) {

if (loTail == null)

loHead = e;

else

loTail.next = e;

loTail = e;

}

// 原索引+oldCap

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ( != null);

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

在put6:6之后,直接就执行了扩容,新数组长度为8,新的结构如下

图片 6

在新的结构中,将原始的数组下标为1和2链表元素均匀分布新数组的其他数组元素中。此间扩容的变化的过程如下

老数组长度为4,通过算法得出数据的下标1:1为1,5:5为1,2:2和6:6为2

1(1:1 == > 5:5)

2(2:2 == > 6:6)

在进行扩容操作是,数组元素链表中的第一个数组下标不会产生变化,在遍历链表其他元素中通过算法"e.hash & oldCap"!=0则将链表元素放入新数据数组下标为[原始数据下标 原始数据长度]

再次引用大神的图,便于理解扩容的数据移动变化

图片 7

在扩容操作中,因无需重新计算hash值,同时均匀将链表冲突的元素均匀分布到新的数组中。这设计实在是巧妙。

get寻找数据

final Node<K,V> getNode(int hash, Object key) {

Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

if ((tab = table) != null && (n = tab.length) > 0 &&

(first = tab[ & hash]) != null) {

if (first.hash == hash && // always check first node

((k = first.key) == key || (key != null && key.equals

return first;

if ((e = first.next) != null) {

if (first instanceof TreeNode)

return ((TreeNode<K,V>)first).getTreeNode(hash, key);

do {

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals

return e;

} while ((e = e.next) != null);

}

}

return null;

}

get方法比较简单,基本流程为通过key的hashCode和寻址算法得到数组下标,若数组元素中的key和hash相等,则直接返回。若不想等,同时存在链表元素,则遍历链表元素进行匹配。由于1.8引用了红黑树结构,在链表元素过多时,1.8的实现将比1.7在get和put操作上效率高上很多。

在本文中,未详细说明,寻址的算法的优越性和红黑树的优点。这里不进行讨论。

            afterNodeAccess(e);
            return oldValue;
        }
    }

HashMapmap=newHashMap();map.put;map.put;map.put;for(Entry entry :map.entrySet { System.out.println(entry.getKey() ": " entry.getValue;}运行结果是:key1:1key2:2key3:3

来源:SylvanasSun's Blog ,

//将旧的table对于到扩容的table上
//扩了一倍,那么其实是就是高位新增一位判断是1 还是0
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

看到这里你一定想知道HashMap存储数据后的结构是怎么样的。

光从名字上应该也能猜到,HashMap肯定是基于hash算法实现的,这种基于hash实现的map叫做散列表(hash table)。

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果第一个存在,并可以key值相同返回first
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//没有找到的话
if ((e = first.next) != null) {
//先判断是否是红黑树
if (first instanceof TreeNode)
return ((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);
}
}
return null;
}

– 数组:

散列表中维护了一个数组,数组的每一个元素被称为一个桶(bucket),当你传入一个key

"a"进行查询时,散列表会先把key传入散列(hash)函数中进行寻址,得到的结果就是数组的下标,然后再通过这个下标访问数组即可得到相关联的值。

图片 8

我们都知道数组中数据的组织方式是线性的,它会直接分配一串连续的内存地址序列,要找到一个元素只需要根据下标来计算地址的偏移量即可(查找一个元素的起始地址为:数组的起始地址加上下标乘以该元素类型占用的地址大小)。因此散列表在理想的情况下,各种操作的时间复杂度只有O(1),这甚至超过了二叉查找树,虽然理想的情况并不总是满足的,关于这点之后我们还会提及。

为什么是hash?

hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法,它将任意大小的数据(输入)映射到一个固定大小的序列(输出)上,这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。

图片 9

hash是具有唯一性且不可逆的,唯一性指的是相同的输入产生的hash code永远是一样的,而不可逆也比较容易理解,数据摘要算法并不是压缩算法,它只是生成了一个该数据的摘要,没有将数据进行压缩。压缩算法一般都是使用一种更节省空间的编码规则将数据重新编码,解压缩只需要按着编码规则解码就是了,试想一下,一个几百MB甚至几GB的数据生成的hash code都只是一个拥有固定长度的序列,如果再能逆向解压缩,那么其他压缩算法该情何以堪?

我们上述讨论的仅仅是在密码学中的hash算法,而在散列表中所需要的散列函数是要能够将key寻址到buckets中的一个位置,散列函数的实现影响到整个散列表的性能。

一个完美的散列函数要能够做到均匀地将key分布到buckets中,每一个key分配到一个bucket,但这是不可能的。虽然hash算法具有唯一性,但同时它还具有重复性,唯一性保证了相同输入的输出是一致的,却没有保证不同输入的输出是不一致的,也就是说,完全有可能两个不同的key被分配到了同一个bucket(因为它们的hash code可能是相同的),这叫做碰撞冲突。总之,理想很丰满,现实很骨感,散列函数只能尽可能地减少冲突,没有办法完全消除冲突。

散列函数的实现方法非常多,一个优秀的散列函数要看它能不能将key分布均匀。首先介绍一种最简单的方法:除留余数法,先对key进行hash得到它的hash code,然后再用该hash code对buckets数组的元素数量取余,得到的结果就是bucket的下标,这种方法简单高效,也可以当做对集群进行负载均衡的路由算法。

private int hash(Key key) {

// & 0x7fffffff 是为了屏蔽符号位,M为bucket数组的长度

return (key.hashCode() & 0x7fffffff) % M;

}

要注意一点,只有整数才能进行取余运算,如果hash code是一个字符串或别的类型,那么你需要将它转换为整数才能使用除留余数法,不过Java在Object对象中提供了hashCode()函数,该函数返回了一个int值,所以任何你想要放入HashMap的自定义的抽象数据类型,都必须实现该函数和equals()函数,这两个函数之间也遵守着一种约定:如果a.equals(b) == true,那么a与b的hashCode()也必须是相同的。

下面为String类的hashCode()函数,它先遍历了内部的字符数组,然后在每一次循环中计算hash code(将hash code乘以一个素数并加上当前循环项的字符):

/** The value is used for character storage. */

private final char value[];

/** Cache the hash code for the string */

private int hash; // Default to 0

public int hashCode() {

int h = hash;

if (h == 0 && value.length > 0) {

char val[] = value;

for (int i = 0; i < value.length; i ) {

h = 31 * h val[i];

}

hash = h;

}

return h;

}

HashMap没有采用这么简单的方法,有一个原因是HashMap中的buckets数组的长度永远为一个2的幂,而不是一个素数,如果长度为素数,那么可能会更适合简单暴力的除留余数法(当然除留余数法虽然简单却并不是那么高效的),顺便一提,时代的眼泪Hashtable就使用了除留余数法,它没有强制约束buckets数组的长度。

HashMap在内部实现了一个hash()函数,首先要对hashCode()的返回值进行处理:

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

该函数将key.hashCode()的低16位和高16位做了个异或运算,其目的是为了扰乱低位的信息以实现减少碰撞冲突。之后还需要把hash()的返回值与table.length

  • 1做与运算(table为buckets数组),得到的结果即是数组的下标。

table.length -

final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果超过了最大容量,不会扩容的
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//没有的话讲容量变成两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//初始化
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//重新计算下次扩容的临界值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//为null利于gc回收处理
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;

针对这个流程,网上出现了一张比较好的流程图,这里借用下(若有冒犯请留言,我将重新画一个)

1就像是一个低位掩码(这个设计也优化了扩容操作的性能),它和hash()做与操作时必然会将高位屏蔽(因为一个HashMap不可能有特别大的buckets数组,至少在不断自动扩容之前是不可能的,所以table.length

1的大部分高位都为0),只保留低位,看似没什么毛病,但这其实暗藏玄机,它会导致总是只有最低的几位是有效的,这样就算你的hashCode()实现得再好也难以避免发生碰撞。这时,hash()函数的价值就体现出来了,它对hash code的低位添加了随机性并且混合了高位的部分特征,显著减少了碰撞冲突的发生(关于hash()函数的效果如何,可以参考这篇文章An introduction to optimising a hashing strategy)。

HashMap的散列函数具体流程如下图:

图片 10

解决冲突

在上文中我们已经多次提到碰撞冲突,但是散列函数不可能是完美的,key分布完全均匀的情况是不存在的,所以碰撞冲突总是难以避免。

那么发生碰撞冲突时怎么办?总不能丢弃数据吧?必须要有一种合理的方法来解决这个问题,HashMap使用了叫做分离链接(Separate chaining,也有人翻译成拉链法)的策略来解决冲突。它的主要思想是每个bucket都应当是一个互相独立的数据结构,当发生冲突时,只需要把数据放入bucket中(因为bucket本身也是一个可以存放数据的数据结构),这样查询一个key所消耗的时间为访问bucket所消耗的时间加上在bucket中查找的时间。

HashMap的buckets数组其实就是一个链表数组,在发生冲突时只需要把Entry(还记得Entry吗?HashMap的Entry实现就是一个简单的链表节点,它包含了key和value以及hash code)放到链表的尾部,如果未发生冲突(位于该下标的bucket为null),那么就把该Entry做为链表的头部。而且HashMap还使用了Lazy策略,buckets数组只会在第一次调用put()函数时进行初始化,这是一种防止内存浪费的做法,像ArrayList也是Lazy的,它在第一次调用add()时才会初始化内部的数组。

图片 11

不过链表虽然实现简单,但是在查找的效率上只有O(n),而且我们大部分的操作都是在进行查找,在hashCode()设计的不是非常良好的情况下,碰撞冲突可能会频繁发生,链表也会变得越来越长,这个效率是非常差的。Java 8对其实现了优化,链表的节点数量在到达阈值时会转化为红黑树,这样查找所需的时间就只有O(log n)了,阈值的定义如下:

/**

* The bin count threshold for using a tree rather than list for a

* bin. Bins are converted to trees when adding an element to a

* bin with at least this many nodes. The value must be greater

* than 2 and should be at least 8 to mesh with assumptions in

* tree removal about conversion back to plain bins upon

* shrinkage.

*/

static final int TREEIFY_THRESHOLD = 8;

如果在插入Entry时发现一条链表超过阈值,就会执行以下的操作,对该链表进行树化;相对的,如果在删除Entry(或进行扩容)时发现红黑树的节点太少(根据阈值UNTREEIFY_THRESHOLD),也会把红黑树退化成链表。

/**

* 替换指定hash所处位置的链表中的所有节点为TreeNode,

* 如果buckets数组太小,就进行扩容。

*/

final void treeifyBin(Node<K,V>[] tab, int hash) {

int n, index; Node<K,V> e;

// MIN_TREEIFY_CAPACITY = 64,小于该值代表数组中的节点并不是很多

// 所以选择进行扩容,只有数组长度大于该值时才会进行树化。

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

resize();

else if ((e = tab[index = (n - 1) & hash]) != null) {

TreeNode<K,V> hd = null, tl = null;

// 转换链表节点为树节点,注意要处理好连接关系

do {

TreeNode<K,V> p = replacementTreeNode(e, null);

if (tl == null)

hd = p;

else {

p.prev = tl;

tl.next = p;

}

tl = p;

} while ((e = e.next) != null);

if ((tab[index] = hd) != null)

hd.treeify(tab); // 从头部开始构造树

}

}

// 该函数定义在TreeNode中

final void treeify(Node<K,V>[] tab) {

TreeNode<K,V> root = null;

for (TreeNode<K,V> x = this, next; x != null; x = next) {

next = (TreeNode<K,V>)x.next;

x.left = x.right = null;

if (root == null) { // 初始化root节点

x.parent = null;

x.red = false;

root = x;

}

else {

K k = x.key;

int h = x.hash;

Class<?> kc = null;

for (TreeNode<K,V> p = root;;) {

int dir, ph;

K pk = p.key;

// 确定节点的方向

if ((ph = p.hash) > h)

dir = -1;

else if (ph < h)

dir = 1;

// 如果kc == null

// 并且k没有实现Comparable接口

// 或者k与pk是没有可比较性的(类型不同)

// 或者k与pk是相等的(返回0也有可能是相等)

else if ((kc == null &&

(kc = comparableClassFor(k)) == null) ||

(dir = compareComparables(kc, k, pk)) == 0)

dir = tieBreakOrder(k, pk);

// 确定方向后插入节点,修正红黑树的平衡

TreeNode<K,V> xp = p;

if ((p = (dir <= 0) ? p.left : p.right) == null) {

x.parent = xp;

if (dir <= 0)

xp.left = x;

else

xp.right = x;

root = balanceInsertion(root, x);

break;

}

}

}

}

// 确保给定的root是该bucket中的第一个节点

moveRootToFront(tab, root);

}

static int tieBreakOrder(Object a, Object b) {

int d;

if (a == null || b == null ||

(d = a.getClass().getName().

compareTo(b.getClass().getName())) == 0)

// System.identityHashCode()将调用并返回传入对象的默认hashCode()

// 也就是说,无论是否重写了hashCode(),都将调用Object.hashCode()。

// 如果传入的对象是null,那么就返回0

d = (System.identityHashCode(a) <= System.identityHashCode(b) ?

-1 : 1);

return d;

}

解决碰撞冲突的另一种策略叫做开放寻址法(Open addressing),它与分离链接法的思想截然不同。在开放寻址法中,所有Entry都会存储在buckets数组,一个明显的区别是,分离链接法中的每个bucket都是一个链表或其他的数据结构,而开放寻址法中的每个bucket就仅仅只是Entry本身。

开放寻址法是基于数组中的空位来解决冲突的,它的想法很简单,与其使用链表等数据结构,不如直接在数组中留出空位来当做一个标记,反正都要占用额外的内存。

当你查找一个key的时候,首先会从起始位置(通过散列函数计算出的数组索引)开始,不断检查当前bucket是否为目标Entry(通过比较key来判断),如果当前bucket不是目标Entry,那么就向后查找(查找的间隔取决于实现),直到碰见一个空位(null),这代表你想要找的key不存在。

如果你想要put一个全新的Entry(Map中没有这个key存在),依然会从起始位置开始进行查找,如果起始位置不是空的,则代表发生了碰撞冲突,只好不断向后查找,直到发现一个空位。

开放寻址法的名字也是来源于此,一个Entry的位置并不是完全由hash值决定的,所以也叫做Closed hashing,相对的,分离链接法也被称为Open hashing或Closed addressing。

根据向后探测(查找)的算法不同,开放寻址法有多种不同的实现,我们介绍一种最简单的算法:线性探测法(Linear probing),在发生碰撞时,简单地将索引加一,如果到达了数组的尾部就折回到数组的头部,直到找到目标或一个空位。

图片 12

基于线性探测法的查找操作如下:

private K[] keys; // 存储key的数组

private V[] vals; // 存储值的数组

public V get(K key) {

// m是buckets数组的长度,即keys和vals的长度。

// 当i等于m时,取模运算会得0(折回数组头部)

for (int i = hash(key); keys[i] != null; i = (i 1) % m) {

if (keys[i].equals(key))

return vals[i];

}

return null;

}

插入操作稍微麻烦一些,需要在插入之前判断当前数组的剩余容量,然后决定是否扩容。数组的剩余容量越多,代表Entry之间的间隔越大以及越早碰见空位(向后探测的次数就越少),效率自然就会变高。代价就是额外消耗的内存较多,这也是在用空间换取时间。

public void put(K key, V value) {

// n是Entry的数量,如果n超过了数组长度的一半,就扩容一倍

if (n >= m / 2) resize(2 * m);

int i;

for (i = hash(key); keys[i] != null; i = (i 1) % m) {

if (keys[i].equals(key)) {

vals[i] = value;

return;

}

}

// 没有找到目标,那么就插入一对新的Entry

keys[i] = key;

vals[i] = value;

n ;

}

接下来是删除操作,需要注意一点,我们不能简单地把目标key所在的位置(keys和vals数组)设置为null,这样会导致此位置之后的Entry无法被探测到,所以需要将目标右侧的所有Entry重新插入到散列表中:

public V delete(K key) {

int i = hash(key);

// 先找到目标的索引

while (!key.equals(keys[i])) {

i = (i 1) % m;

}

V oldValue = vals[i];

// 删除目标key和value

keys[i] = null;

vals[i] = null;

// 指针移动到下一个索引

i = (i 1) % m;

while (keys[i] != null) {

// 先删除然后重新插入

K keyToRehash = keys[i];

V valToRehash = vals[i];

keys[i] = null;

vals[i] = null;

n--;

put(keyToRehash, valToRehash);

i = (i 1) % m;

}

n--;

// 当前Entry小于等于数组长度的八分之一时,进行缩容

if (n > 0 && n <= m / 8) resize(m / 2);

return oldValue;

}

动态扩容

散列表以数组的形式组织bucket,问题在于数组是静态分配的,为了保证查找的性能,需要在Entry数量大于一个临界值时进行扩容,否则就算散列函数的效果再好,也难免产生碰撞。

所谓扩容,其实就是用一个容量更大(在原容量上乘以二)的数组来替换掉当前的数组,这个过程需要把旧数组中的数据重新hash到新数组,所以扩容也能在一定程度上减缓碰撞。

HashMap通过负载因子(Load Factor)乘以buckets数组的长度来计算出临界值,算法:threshold = load_factor * capacity。比如,HashMap的默认初始容量为16(capacity = 16),默认负载因子为0.75(load_factor = 0.75),那么临界值就为threshold = 0.75 * 16 = 12,只要Entry的数量大于12,就会触发扩容操作。

还可以通过下列的构造函数来自定义负载因子,负载因子越小查找的性能就会越高,但同时额外占用的内存就会越多,如果没有特殊需要不建议修改默认值。

/**

* 可以发现构造函数中根本就没初始化buckets数组。

* (之前说过buckets数组会推迟到第一次调用put()时进行初始化)

*/

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);

this.loadFactor = loadFactor;

// tableSizeFor()确保initialCapacity必须为一个2的N次方

this.threshold = tableSizeFor(initialCapacity);

}

buckets数组的大小约束对于整个HashMap都至关重要,为了防止传入一个不是2次幂的整数,必须要有所防范。tableSizeFor()函数会尝试修正一个整数,并转换为离该整数最近的2次幂。

/**

* Returns a power of two size for the given target capacity.

*/

static final int tableSizeFor(int cap) {

int n = cap - 1;

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;

}

图片 13

还记得数组索引的计算方法吗?index = (table.length - 1) & hash,这其实是一种优化手段,由于数组的大小永远是一个2次幂,在扩容之后,一个元素的新索引要么是在原位置,要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算,之前提到过&运算只会关注n – 1(n = 数组长度)的有效位,当扩容之后,n的有效位相比之前会多增加一位(n会变成之前的二倍,所以确保数组长度永远是2次幂很重要),然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置,如果是0,那么索引没有发生变化,如果是1,索引就为原索引加上扩容前的容量。

图片 14

这样在每次扩容时都不用重新计算hash,省去了不少时间,而且新增有效位是0还是1是带有随机性的,之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开。下面是resize()的源码:

final Node<K,V>[] resize() {

Node<K,V>[] oldTab = table; // table就是buckets数组

int oldCap = (oldTab == null) ? 0 : oldTab.length;

int oldThr = threshold;

int newCap, newThr = 0;

// oldCap大于0,进行扩容,设置阈值与新的容量

if (oldCap > 0) {

// 超过最大值不会进行扩容,并且把阈值设置成Interger.MAX_VALUE

if (oldCap >= MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return oldTab;

}

// 没超过最大值,扩容为原来的2倍

// 向左移1位等价于乘2

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

oldCap >= DEFAULT_INITIAL_CAPACITY)

newThr = oldThr << 1; // double threshold

}

// oldCap = 0,oldThr大于0,那么就把阈值做为新容量以进行初始化

// 这种情况发生在用户调用了带有参数的构造函数(会对threshold进行初始化)

else if (oldThr > 0) // initial capacity was placed in threshold

newCap = oldThr;

// oldCap与oldThr都为0,这种情况发生在用户调用了无参构造函数

// 采用默认值进行初始化

else { // zero initial threshold signifies using defaults

newCap = DEFAULT_INITIAL_CAPACITY;

newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

}

// 如果newThr还没有被赋值,那么就根据newCap计算出阈值

if (newThr == 0) {

float ft = (float)newCap * loadFactor;

newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?

(int)ft : Integer.MAX_VALUE);

}

threshold = newThr;

style="font-size: 16px;">@SuppressWarnings({"rawtypes","unchecked"})

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

table = newTab;

// 如果oldTab != null,代表这是扩容操作

// 需要将扩容前的数组数据迁移到新数组

if (oldTab != null) {

// 遍历oldTab的每一个bucket,然后移动到newTab

for (int j = 0; j < oldCap; j) {

Node<K,V> e;

if ((e = oldTab[j]) != null) {

oldTab[j] = null;

// 索引j的bucket只有一个Entry(未发生过碰撞)

// 直接移动到newTab

if (e.next == null)

newTab[e.hash & (newCap - 1)] = e;

// 如果是一个树节点(代表已经转换成红黑树了)

// 那么就将这个节点拆分为lower和upper两棵树

// 首先会对这个节点进行遍历

// 只要当前节点的hash & oldCap == 0就链接到lower树

// 注意这里是与oldCap进行与运算,而不是oldCap - 1(n - 1)

// oldCap就是扩容后新增有效位的掩码

// 比如oldCap=16,二进制10000,n-1 = 1111,扩容后的n-1 = 11111

// 只要hash & oldCap == 0,就代表hash的新增有效位为0

// 否则就链接到upper树(新增有效位为1)

// lower会被放入newTab[原索引j],upper树会被放到newTab[原索引j oldCap]

// 如果lower或者upper树的节点少于阈值,会被退化成链表

else if (e instanceof TreeNode)

((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

else { // preserve order

// 下面操作的逻辑与分裂树节点基本一致

// 只不过split()操作的是TreeNode

// 而且会将两条TreeNode链表组织成红黑树

Node<K,V> loHead = null, loTail = null;

Node<K,V> hiHead = null, hiTail = null;

Node<K,V> next;

do {

next = e.next;

if ((e.hash & oldCap) == 0) {

if (loTail == null)

loHead = e;

else

loTail.next = e;

loTail = e;

}

else {

if (hiTail == null)

hiHead = e;

else

hiTail.next = e;

hiTail = e;

}

} while ((e = next) != null);

if (loTail != null) {

loTail.next = null;

newTab[j] = loHead;

}

if (hiTail != null) {

hiTail.next = null;

newTab[j oldCap] = hiHead;

}

}

}

}

}

return newTab;

}

使用HashMap时还需要注意一点,它不会动态地进行缩容,也就是说,你不应该保留一个已经删除过大量Entry的HashMap(如果不打算继续添加元素的话),此时它的buckets数组经过多次扩容已经变得非常大了,这会占用非常多的无用内存,这样做的好处是不用多次对数组进行扩容或缩容操作。不过一般也不会出现这种情况,如果遇见了,请毫不犹豫地丢掉它,或者把数据转移到一个新的HashMap。

添加元素

我们已经了解了HashMap的内部实现与工作原理,它在内部维护了一个数组,每一个key都会经过散列函数得出在数组的索引,如果两个key的索引相同,那么就使用分离链接法解决碰撞冲突,当Entry的数量大于临界值时,对数组进行扩容。

接下来以一个添加元素(put())的过程为例来梳理一下知识,下图是put()函数的流程图:

图片 15

然后是源码:

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

// table == null or table.length == 0

// 第一次调用put(),初始化table

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// 没有发生碰撞,直接放入到数组

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

else {

Node<K,V> e; K k;

// 发生碰撞(头节点就是目标节点)

if (p.hash == hash &&

((k = p.key) == key || (key != null && key.equals(k))))

e = p;

// 节点为红黑树

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) // -1 for 1st

// 链表过长,转换为红黑树

treeifyBin(tab, hash);

break;

}

// 找到目标节点,退出循环

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

}

// 节点已存在,替换value

if (e != null) { // existing mapping for key

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

// afterNodeXXXXX是提供给LinkedHashMap重写的函数

// 在HashMap中没有意义

afterNodeAccess(e);

return oldValue;

}

}

modCount;

// 超过临界值,进行扩容

if ( size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

系列

【关于投稿】

如果大家有原创好文投稿,请直接给公号发送留言。返回搜狐,查看更多

责任编辑:

Hashmap 源码分析之基本操作

JDK1.8中,对扩容算法做了优化。我们观察下key1和key2在扩容前和扩容后的位置计算过程:

HashMap

接下来就是hashmap扩容了

publicVput(K key, Vvalue){// 对key的hashCode()做hashreturnputVal, key,value,false,true);}final VputVal(inthash, K key, Vvalue, boolean onlyIfAbsent, boolean evict){ Node[] tab; Node p;intn, i;//判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容if((tab = table) ==null|| (n = tab.length) ==0) n = (tab = resize.length;//根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加if((p = tab[i = & hash]) ==null) tab[i] = newNode(hash, key,value,null);else{ Node e; K k;//判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,这里的相同指的是hashCode相等if(p.hash == hash && ((k = p.key) == key || (key !=null&& key.equals e = p;//判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对elseif(p instanceof TreeNode) e= (p).putTreeVal(this, tab, hash, key,value);else{//遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;for(intbinCount =0; ; binCount) {if((e = p.next) ==null) { p.next = newNode(hash, key,value,null);if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1sttreeifyBin(tab, hash);break; }if(e.hash == hash && ((k = e.key) == key || (key !=null&& key.equalsbreak; p = e; } }if {// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null) e.value=value; afterNodeAccess;returnoldValue; } } modCount;//插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。if( size > threshold) resize(); afterNodeInsertion;returnnull;}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//数组tab table是内部数组
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
// resize()是扩容函数
n = (tab = resize()).length;
//取到hash地址,如果为null就可以填入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//不为null
Node<K,V> e; K k;
//如果map中已经存在,就将值覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果这个结点是红黑树的结点,那么使用putTreeVal来实现。
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);
//假如这个链表结点个数大于等于TREEIFY_THRESHOLD - 1的时候的时候,直接转换成树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已经存在直接覆盖value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent if true, don't change existing value
if (!onlyIfAbsent || oldValue == null)
e.value = value;

2.length是数组的长度,取模运算求出数组索引。当length总是2的n次方时,h& 运算等价于对length取模,也就是h%length,但是&比%具有更高的效率。

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

链表

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

图片 16

正如上面写的,应该是和LinkedhashMap有关系。

安全性

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

HashMap使用 键值对 存储,只需传入相应的键-值即可存储。看下面的例子:

那么其实我们可以看到hashmap扩容其实非常的耗时间,如果可以预测这个map可以存的值数量,其实在初始化的时候定义是更加合算的。

图片 17

我们从流程中看一下,这个hashmap究竟是这么实现的。
我们先了解一下put方法实现

图片 18

读源码,是我们了解大神领域的一大捷径
生命不息,奋斗不止

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243 这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

至于afterNodeInsertion这些,在hashmap中其实是没有实现的,

分析:

接下来的才是真正实现:

HashMap的扩容方法

                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);

接下来,看存储的数据结构代码:

//这个是一个安全机制 modCount在LinkedList讲过
modCount;
if ( size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

HashMap中存储数据用的是一个数组:Node[] table,即哈希桶数组,明显它是一个Node的数组。对照上图中的第一列。

同样真正实现是在

HashMap的 存储结构 原理

我们接下来看,get方法,注意hashmap是可以有null值的

2.数组的特点是:寻址容易,插入和删除困难。

在理解HashMap的扩容流程之前,我们得先了解下HashMap的几个字段。

例如存储:map.put;

扩容原理

intthreshold;// 所能容纳的key-value对极限 finalfloatloadFactor;// 负载因子intmodCount;intsize;

可以看到如下结果:

HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。

就是HashMap中实际存在的键值对数量。

图片 19

3.当链表长度大于8时,将这个链表转换成红黑树,利用红黑树快速增删改查的特点提高HashMap的性能。想了解更多红黑树数据结构的工作原理可以参考

HashMap存储数据的工作流程就是:

modCount

图片 20

数组中存储的黑点的数据结构就是这里的Node结构:

staticclassNodeimplementsMap.Entry{finalinthash;//用来定位数组索引位置finalK key; V value; Node next;//链表的下一个nodeNode(inthash, K key, V value, Node next) { ... }publicfinalKgetKey(){ ... }publicfinalVgetValue(){ ... }publicfinalStringtoString(){ ... }publicfinalinthashCode(){ ... }publicfinalVsetValue(V newValue){ ... }publicfinalbooleanequals{ ... }}

具体代码,有兴趣的可以仔细品读以下代码:

Node[] table的初始化长度length

JDK1.7中的扩容较好理解:使用一个容量更大的数组来代替已有的容量小的数组,并把数据从原来的数组中重新按照原来的计算方法放到新的数组中。

从结构实现来讲,HashMap是数组 链表 红黑树(JDK1.8增加了红黑树部分)实现的。

size

map.get;

图片 21

分析:

HashMap中 put、get方法 实现

本文涉及HashMap的:

图片 22

具体实现方法

1finalNode[] resize() {2Node[] oldTab = table;3intoldCap = (oldTab ==null) ?0: oldTab.length;4intoldThr = threshold;5intnewCap, newThr =0;6if(oldCap >0) {7// 超过最大值就不再扩充了,就只好随你碰撞去吧8if(oldCap >= MAXIMUM_CAPACITY) {9threshold = Integer.MAX_VALUE;10returnoldTab;11}12// 没超过最大值,就扩充为原来的2倍13elseif((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&14oldCap >= DEFAULT_INITIAL_CAPACITY)15newThr = oldThr <<1;// double threshold16}17elseif(oldThr >0)// initial capacity was placed in threshold18newCap = oldThr;19else{// zero initial threshold signifies using defaults20newCap = DEFAULT_INITIAL_CAPACITY;21newThr = (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);22}23// 计算新的resize上限24if(newThr ==0) {2526floatft = newCap * loadFactor;27newThr = (newCap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY ?28ft : Integer.MAX_VALUE);29}30threshold = newThr;31@SuppressWarnings({"rawtypes","unchecked"})32Node[] newTab = newNode[newCap];33table = newTab;34if(oldTab !=null) {35// 把每个bucket都移动到新的buckets中36for(intj =0; j < oldCap; j) {37Node e;38if((e = oldTab[j]) !=null) {39oldTab[j] =null;40if(e.next==null)41newTab[e.hash & (newCap -1)] = e;42elseif(einstanceofTreeNode)43(e).split(this, newTab, j, oldCap);44else{// 链表优化重hash的代码块45Node loHead =null, loTail =null;46Node hiHead =null, hiTail =null;47Nodenext;48do{49next= e.next;50// 原索引51if((e.hash & oldCap) ==0) {52if(loTail ==null)53loHead = e;54else55loTail.next= e;56loTail = e;57}58// 原索引 oldCap59else{60if(hiTail ==null)61hiHead = e;62else63hiTail.next= e;64hiTail = e;65}66}while !=null);67// 原索引放到bucket里68if(loTail !=null) {69loTail.next=null;70newTab[j] = loHead;71}72// 原索引 oldCap放到bucket里73if(hiTail !=null) {74hiTail.next=null;75newTab[j oldCap] = hiHead;76}77}78}79}80}81returnnewTab;82}

方法一:staticfinalinthash(Object key){//jdk1.8 & jdk1.7inth;// h = key.hashCode() 为第一步 取hashCode值// h ^ (h >>> 16) 为第二步 高位参与运算return(key ==null) ?0: (h = key.hashCode ^ (h >>>16);}方法二:staticintindexFor(inth,intlength){//jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的returnh & ;//第三步 取模运算}

2.链表的特点是:寻址困难,插入和删除容易。

1.数组存储区间是连续的,占用内存严重,故空间复杂的很大。

HashMap为了能做到 寻址 容易, 插入、删除 也容易使用了如下的结构。

结合图看代码更清晰移动点。

HashMap的简单使用

2.有时两个key会定位到相同的位置,表示发生了Hash碰撞。Java中HashMap采用了链地址法来解决Hash碰撞。(链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。)

HashMap的 简单使用

读取对应键的值:

voidtransfer(Entry[] newTable) { Entry[] src = table;//src引用了旧的Entry数组intnewCapacity = newTable.length;for(intj =0; j < src.length; j ) {//遍历旧的Entry数组Entry e = src[j];//取得旧Entry数组的每个元素if { src[j] =null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)do{ Entrynext= e.next;inti = indexFor(e.hash, newCapacity);//!!重新计算每个元素在数组中的位置e.next= newTable[i];//标记[1]newTable[i] = e;//将元素放在数组上e =next;//访问下一个Entry链上的元素}while; } } }

– 高位运算

是HashMap所能容纳的最大数据量的Node个数:threshold = length * loadFactor。超过这个数目就重新resize,扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择,建议大家不要修改。

HashMap中 定位数据索引 实现

voidresize(intnewCapacity) {//传入新的容量Entry[] oldTable =table;//引用扩容前的Entry数组intoldCapacity = oldTable.length;if(oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大了threshold = Integer.MAX_VALUE;//修改阈值为int的最大值,这样以后就不会扩容了return; } Entry[] newTable =newEntry[newCapacity];//初始化一个新的Entry数组transfer;//!!将数据转移到新的Entry数组里table= newTable;//HashMap的table属性引用新的Entry数组threshold = (newCapacity * loadFactor);//修改阈值}

HashMap的存储结构

– 取模运算

图片 23

1.链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O。

确定哈希桶数组索引的位置

threshold

– 取key的hashCode值

高低位异或运算如下图:(n为table的长度)

主要用来记录HashMap内部结构发生变化的次数,主要用于迭代的快速失败。强调一点,内部结构发生变化指的是结构发生变化,例如put新键值对,但是某个key对应的value值被覆盖不属于结构变化。

我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引 oldCap”。

1.将“key1”这个key用hashCode()方法得到其hashCode 值,然后再通过Hash算法的后两步运算(高位运算和取模运算,下文有介绍)来定位该键值对的存储位置(即数据在table数组中的索引)

Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射。

1.求hash值方法中,用h = key.hashCode()。然后将h的低16位和高16位异或,是为了保证在数组table的length比较小的时候,让高低位数据都参与到Hash的计算中,同时不会有太大的开销。

staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;// aka 16

这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。

staticfinalfloatDEFAULT_LOAD_FACTOR =0.75f;

HashMap的 扩容方法 原理

小编整理了一些java进阶学习资料和面试题,需要资料的请加JAVA高阶学习Q群:664389243 这是小编创建的java高阶学习交流群,加群一起交流学习深造。群里也有小编整理的2019年最新最全的java高阶学习资料!

分三步确定:

loadFactor为负载因子,

HashMap的put方法

可以看看下图为16扩充为32的resize示意图:

HashMap综合了数组和链表的优缺点,实现了自己的存储方式。那么先看一下数组和链表的存储方式:

本文由betway必威登录平台发布于互联网比赛,转载请注明出处:Map 大家族的那点事儿 ( 4 ) :HashMap

Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。