标签:key hash HashMap 链表 数组 长度 原理 底层
HashMap主要用来存放键值对,它基于哈希表的Map接口实现,是常用的java集合之一,是非线程安全的。
HashMap可以存储null的key和value,但null作为键只能存在一个,作为值则可有多个。
jdk1.7 底层使用数组+链表的方式实现,每次插入使用的是头插法。
数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突)。
jdk1.8 底层使用数组+链表+红黑树的方式实现,每次使用的是尾插法。
引入红黑树的目的是避免单条链表长度过长而影响查询效率
jdk8解决冲突:当链表长度大于等于阈值(默认为 8)(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。
HashMap默认的初始大小为16,之后每次扩容会变成原来的2倍。、
底层分析
JDK8之前
1、数据结构
jdk1.8之前,HashMap底层是数组和链表结合在一起使用也就是链表散列。这样结合了链表在增删方面的高效和数组在寻址方面的优势。
hashmap结构:数组+链表,数组默认长度是16,注意hashtable数组的默认长度是11(可以自动变长。构造HashMap的时候也可以指定长度),数组中每个元素存储的是一个链表的头节点,链表的节点由key、value和next组成,next指向下一个节点。
2、HashMap的存取
HashMap通过key的hashCode经过hash方法处理过后(减少碰撞)得到hash值,接着hash(key) & (len-1),也就是元素的key的hash值对数组长度进行位运算得到存放位置索引值,然后判断该位置是否有元素,如果没有则直接添加,如果有则先判断元素的hash值以及key是否相同,如果相等直接替换,如果不相等则进行“拉链”, 链表中如果有相同则不添加,如果没有则添加到链表尾部。
这就是所谓的“拉链法”,将数组和链表结合,数组的每一格就是一个链表。遇到hash冲突时将冲突的值加到链表中即可。
JDK8之后
jdk8之后解决hash冲突问题有了较大的变化。增加了红黑树。
按照“拉链”的判断方法将元素添加到链表尾部时,会立即判断当前链表长度是否达到阈值(默认为8),达到阈值首先会调用 treeifyBin()
方法。这个方法根据hashMap数组来决定是否转化为红黑树,只有当数组长度大于或等于64的情况下,才会执行树化操作,减少搜索时间;如果小于64就会先对数组扩容调用 resize()
方法,调用这个方法会对hashMap中的元素进行重新散列hash。
标签:key,
hash,
HashMap,
链表,
数组,
长度,
原理,
底层
From: https://www.cnblogs.com/nliu/p/17776467.html