Java HashMap解析

2019-08-26 06:04:47来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

Java HashMap解析

HashMap继承了AbstractMap,实现了Map, Cloneable, Serializable

HashMap的底层数据结构是存储了Node内部类的数组。HashMap基本的工作原理是将key-value对构造为Node实例类,利用hash()对每个key取hash值,根据hash值分配实例类到数组空间;此外,HashMap还具有利用链表或红黑树处理hash冲突、拥有自动扩容机制、非线程安全等特点

分析HashMap的主要要素

1.构造方法
关键参数:容量、负载因子
容量表示HashMap数组的大小,负载因子影响着HashMap的自动扩容发生的条件;
当HashMap初始化时,根据容量和负载因子计算出扩容界限threshold,当数组使用大小超过界限时,调用resize()自动扩容
默认的HashMap的无参构造方法中,容量时16,负载因子是0.75
为什么是0.75?https://blog.csdn.net/chen45682kang/article/details/81037425

2.hash()
调用key对象的hashCode(),并根据数组的长度折中适应

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

由于哈希表的容量都是 2 的 N 次方,在当前,元素的 hashCode() 在很多时候下低位是相同的,这将导致冲突(碰撞),因此 1.8 以后做了个移位操作:将元素的 hashCode() 和自己右移 16 位后的结果求异或。再计算出下标。

3.Node节点
Node节点实现了Entry接口,成员变量包括hash、key、value、next(冲突时的指针)

3.put()
根据hash值计算出数组存放位置;
该位置没有元素,插入Node节点到该位置;
该位置存在元素,调用equals()判断是否key相等;相等则覆盖;
否则出现了哈希冲突;
当长度较短时,对Node节点的next指针赋值,形成链表;
长度较长时,默认从第八个元素开始,红黑树化;
(较短的长度用链表遍历速度影响较低,但长度较长时利用红黑树可以保证最坏时间复杂度)
插入结束后检查是否需要扩容

由此过程可见HashMap是无序的,且根据key值的相等性保证key唯一

如果需要仅仅根据key的地址作唯一性的判断,可以使用IdentifyHashMap
HashMap的判断方法

(k1==null?k2==null:k1.equals(k2))==true

IdentifyHashMap的判断方法

(k1==k2)

4.get()
计算出key的hash,根据hash值到数组对应下标查找;
若存在哈希冲突,在对应冲突链表或红黑树上寻找equals()为true的Node节点

5.自动扩容
创建新的HashMap, 且容量翻倍;
遍历复制
由于容量的改变,原本的hash分布也需要变,过程中会rehash

拓展:
1.Map
TreeMap
CurrentHashMap
LinkedhashMap
WeakedHashMap
IdentifyHashMap
HashTable

2.哈希算法


原文链接:https://www.cnblogs.com/elinlinlinlog/p/11378573.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Netty基础系列(5) --零拷贝底层分析

下一篇:最常见的Java面试题及答案汇总(三)