Java HashMap解析
2019-08-26 06:04:47来源:博客园 阅读 ()
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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash