Java8 HashMap的实现原理分析

Java8 HashMap的实现原理分析

前言：java8之后新增挺多新东西，在网上找了些相关资料，关于HashMap在自己被血虐之后痛定思痛决定整理一下相关知识方便自己看。图和有些内容参考的这个文章：//jb51.net/article/80446.htm

HashMap的存储结构如图：一个桶（bucket）上的节点多于8个则存储结构是红黑树，小于8个是单向链表。

1：HashMap的一些属性

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L;

// 默认的初始容量是16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

// 最大容量

static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认的填充因子(以前的版本也有叫加载因子的)

static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 这是一个阈值，当桶(bucket)上的链表数大于这个值时会转成红黑树，put方法的代码里有用到

static final int TREEIFY_THRESHOLD = 8;

// 也是阈值同上一个相反，当桶(bucket)上的链表数小于这个值时树转链表

static final int UNTREEIFY_THRESHOLD = 6;

// 看源码注释里说是：树的最小的容量，至少是 4 x TREEIFY_THRESHOLD = 32 然后为了避免(resizing 和 treeification thresholds) 设置成64

static final int MIN_TREEIFY_CAPACITY = 64;

// 存储元素的数组，总是2的倍数

transient Node[] table;

transient Set> entrySet;

// 存放元素的个数，注意这个不等于数组的长度。

transient int size;

// 每次扩容和更改map结构的计数器

transient int modCount;

// 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容

int threshold;

// 填充因子

final float loadFactor;

2：HashMap的构造方法

// 指定初始容量和填充因子的构造方法

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方法计算出临界值，put数据的时候如果超出该值就会扩容，该值肯定也是2的倍数

// 指定的初始容量没有保存下来，只用来生成了一个临界值

this.threshold = tableSizeFor(initialCapacity);

}

// 该方法保证总是返回大于cap并且是2的倍数的值，比如传入999 返回1024

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;

}

//构造函数2

public HashMap(int initialCapacity) {

this(initialCapacity, DEFAULT_LOAD_FACTOR);

}

//构造函数3

public HashMap() {

this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

}

3：get和put的时候确定元素在数组中的位置

static final int hash(Object key) {

int h;

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

}

要确定位置

第一步：首先是要计算key的hash码，是一个int类型数字。那后面的 h >>> 16 源码注释的说法是：为了避免hash碰撞(hash collisons)将高位分散到低位上了，这是综合考虑了速度，性能等各方面因素之后做出的。

第二步： h是hash码，length是上面Node[]数组的长度，做与运算 h & （length-1）。由于length是2的倍数-1后它的二进制码都是1而1与上其他数的结果可能是0也可能是1，这样保证运算后的均匀性。也就是hash方法保证了结果的均匀性，这点非常重要，会极大的影响HashMap的put和get性能。看下图对比：

图3.1是非对称的hash结果

图3.2是均衡的hash结果

这两个图的数据不是很多，如果链表长度超过8个会转成红黑树。那个时候看着会更明显，jdk8之前一直是链表，链表查询的复杂度是O(n)而红黑树由于其自身的特点，查询的复杂度是O(log(n))。如果hash的结果不均匀会极大影响操作的复杂度。相关的知识这里有一个红黑树基础知识博客 网上还有个例子来验证：自定义了一个对象来做key，调整hashCode()方法来看put值得时间

public class MutableKeyTest {

public static void main(String args[]){

class MyKey {

Integer i;

public void setI(Integer i) {

this.i = i;

}

public MyKey(Integer i) {

this.i = i;

}

@Override

public int hashCode() {

// 如果返回1

// return 1

return i;

}

// object作为key存map里，必须实现equals方法

@Override

public boolean equals(Object obj) {

if (obj instanceof MyKey) {

return i.equals(((MyKey)obj).i);

} else {

return false;

}

}

}

// 我机器配置不高，25000的话正常情况27毫秒，可以用2500万试试，如果hashCode()方法返回1的话，250万就卡死

Map map = new HashMap<>(25000,1);

Date begin = new Date();

for (int i = 0; i < 20000; i++){

map.put(new MyKey(i), "test " + i);

}

Date end = new Date();

System.out.println("时间(ms) " + (end.getTime() - begin.getTime()));

4：get方法

public V get(Object key) {

Node e;

return (e = getNode(hash(key), key)) == null ? null : e.value;

}

final Node getNode(int hash, Object key) {

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

// hash & (length-1)得到红黑树的树根位置或者是链表的表头

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

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

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

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

return first;

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

// 如果是树，遍历红黑树复杂度是O(log(n))，得到节点值

if (first instanceof TreeNode)

return ((TreeNode)first).getTreeNode(hash, key);

// else是链表结构

do {

if (e.hash == hash &&

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

return e;

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

}

}

return null;

}

5 ：put方法，put的时候根据 h & (length – 1) 定位到那个桶然后看是红黑树还是链表再putVal

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[] tab; Node p; int n, i;

// 如果tab为空或长度为0，则分配内存resize()

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

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

// (n - 1) & hash找到put位置，如果为空,则直接put

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

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

else {

Node e; K k;

// 第一节节点hash值同，且key值与插入key相同

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

e = p;

else if (p instanceof TreeNode)

// 红黑树的put方法比较复杂，putVal之后还要遍历整个树，必要的时候修改值来保证红黑树的特点

e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);

else {

// 链表

for (int binCount = 0; ; ++binCount) {

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

// e为空，表示已到表尾也没有找到key值相同节点，则新建节点

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

// 新增节点后如果节点个数到达阈值，则将链表转换为红黑树

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

treeifyBin(tab, hash);

break;

}

// 容许空key空value

if (e.hash == hash &&((k = e.key) ==http:// key || (key != null && key.equals(k))))

break;

p = e;

}

}

// 更新hash值和key值均相同的节点Value值

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

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount;

if (++size > threshold)

resize();

afterNodeInsertion(evict);

return null;

}

6：resize方法

final Node[] resize() {

Node[] 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 = (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[] newTab = (Node[])new Node[newCap];

table = newTab;

if (oldTab != null) {

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

Node 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)e).split(this, newTab, j, oldCap);

else { // preserve order

Node loHead = null, loTail = null;

Node hiHead = null, hiTail = null;

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

}

以上所述是给大家介绍的Java8 HashMap的实现原理分析的相关知识，希望对大家有所帮助！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。