hashmap底层原理面试 hashmap源码扩容 _hashmap

HashMap实现原理和源码详细分析

ps：本博客基于Jdk1.8

学习要点：

1、知道HashMap的数据结构
【hashmap底层原理面试 hashmap源码扩容】2、了解HashMap中的散列算法
3、知道HashMap中put、remove、get的代码实现
4、HashMap的哈希冲突是什么？怎么处理的？
5、知道HashMap的扩容机制
1、什么是HashMap？

HashMap 基于哈希表的 Map 接口实现，是以 key-value 存储形式存在， HashMap 的实现不是同步的，这意味着它不是线程安全的。它的 key、value 都可以为 null ，此外， HashMap 中的映射不是有序的。
2、HashMap的特性

Hash存储无序的
key和value都可以存储null值，但是key只能存唯一的一个null值
jdk8之前的数据结构是数组链表， Jdk8之后变成数组链表红黑树
阀值大于8并且数组长度大于64才会转为红黑树

3、HashMap的数据结构
JDK7的情况，是数组加链接， hash冲突时候，就转换为链表：
jdk8的情况， jdk8加上了红黑树，链表的数量大于8而且数组长度大于64之后，就转换为红黑树，红黑树节点小于6之后，就又转换为链表：
翻下HashMap源码，对应的节点信息：

static class Node implements Map.Entry {// hashCodefinal int hash;final K key;V value;// 链表的next指针就不为nullNode next;Node(int hash, K key, V value, Node next) {this.hash = hash;this.key = key;this.value = https://www.shwenmu.com/wenda/value;this.next = next;}// ...}

4、HashMap初始化操作4.1、成员变量

public class HashMap extends AbstractMapimplements Map, Cloneable, Serializable {	/*** 序列号版本号*/private static final long serialVersionUID = 362498820763181265L;/*** 初始化容量 ， 为16=2的4次幂*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 最大容量 ， 为2的30次幂*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认的负载因子 ， 默认值是0.75*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 链表节点树超过8就转为为红黑树*/static final int TREEIFY_THRESHOLD = 8;/*** 红黑树节点少于6就再转换回链表*/static final int UNTREEIFY_THRESHOLD = 6;/*** 桶中结构转化为红黑树对应的数组长度最小的值*/static final int MIN_TREEIFY_CAPACITY = 64;// .../*** HashMap存储元素的数组*/	transient Node[] table;/*** 用来存放缓存*/transient Set> entrySet;/*** HashMap存放元素的个数*/transient int size;/*** 用来记录HashMap的修改次数*/transient int modCount;/*** 用来调整大小下一个容量的值（容量*负载因子）*/int threshold;/*** Hash表的负载因子*/final float loadFactor;}

4.2、构造方法

public HashMap(int initialCapacity, float loadFactor) {// 初始容量不能小于0 ， 小于0直接抛出IllegalArgumentExceptionif (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: "initialCapacity);// 初始容量大于最大容量的时候 ， 取最大容量作为初始容量if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;// 负载因子不能小于0 ， 而且要是数值类型 ， isNan:true,表示就是非数值类型if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: "loadFactor);// 将指定的负载因子赋值给全局变量this.loadFactor = loadFactor;// threshold= (容量) * (负载因子)this.threshold = tableSizeFor(initialCapacity);}public HashMap(int initialCapacity) {// 初始化容量和默认负载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {// 默认的负载因子为0.75	this.loadFactor = DEFAULT_LOAD_FACTOR;}