HashMap源码阅读

概述：

实现原理

由数组和链表组成，其中数组是hashmap的主体，而链表是为了解决哈希冲突而存在的。是Hashtable的轻量级实现

无序、不安全、效率高、key和value都允许null

继承自Map.Entry<K,V>

结构图：

分析

参数

默认容量16最大容量2的31次方默认的填充因子0.75（太大查询效率低，太小数组利用率低）当bucket上的结点大于8时会转成红黑树树化参数64，当小于64时只是简单的扩容，大于64会树化Node：静态内部类，用来表示键值对TreeNode：红黑树节点

关键概念

存储容器

因为hashmap内部是用一个数组来保存内容的，数组定义如下 transient Node<K,V>[] table;

Node类型

table是一个Node类型的数组，Node是其中定义的静态内部类，主要包含hash、key、value、和next属性 static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }

TreeNode

当桶内的链表达到8的时候，会将链表转化为红黑树，就是TreeNode类型，也就是HashMap中定义的静态内部类 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; }

常见问题

1、HashMap1.7和1.8的区别

数据结构不同

1.7是数组加链表1.8是数组加链表或红黑树

链表插入顺序不同

1.7是头插入1.8是链表尾插入

hashcode抖动次数不同

1.7进行了四次异或运算1.8进行了一次异或运算

扩容

1.7扩容时重新hash1.8扩容时优化，只需要看原来的hash值新增的那个bit是1还是0，是0的话索引没变，是1的话索引变成原索引+原来数组的大小

2、HashMap 工作原理

​ HashMap的底层是hash数组和单向链表实现的，数组中的每个元素都是链表，由Node内部类（实现Map.Entry接口）实现，HashMap通过put&get方法存储和获取

存储对象的时候，将k/v传给put()方法：

初始化table：判断table是否为空或者为null

计算hash值：通过高16位和低16位的异或运算（让高16位也参入进来以便减低冲突）

插入或更新节点：根据（n-1）&hash计算得到插入的数组下标i然后进行判断

table[i]==null：没有hash冲突直接新建节点添加table[i]！=null：判断首个节点和key是否一样 相同：直接更新value不相同：判断是否是红黑树 红黑树：直接在树中插入键值对链表：遍历链表判断是否已经存在此key： 存在更新不存在就插入（1.8是尾插入），然后判断是否转为红黑树

扩容：根据size和数组长度*负载因子来判断是否需要扩容

获取对象时，将 K 传给 get() 方法：

调用 hash(K) 方法（计算 K 的 hash 值）从而获取该键值所在链表的数组下标；

确定桶的位置后，会出现三种情况

单节点类型：只要不发生哈希碰撞就是这种类型链表类型：遍历链表，直到找到key相等的Node红黑树类型：使用红黑树专用的快速查找方法

hashCode 是定位的，存储位置；equals是定性的，比较两者是否相等。

3、为什么要一起重写hashCode()和equal（）方法

假设都不重写

这样hashMap就可以存在key相同的值

只重写hashCode

无法正确地与链表元素进行相等判断，从而无法保证去重

只重写equals()方法

映射到HashMap中不同数组下标，无法保证去重

4、当两个对象的hashCode相同会发生什么

​ 因为hashCode相同，但是不一定就是相等的（需要根据equals方法比较），所以两个对象所在数组的下标相同，碰撞就此发生。

5、hash的实现

​ 在jdk1.8中，是通过hashCode（）的高16位异或低16位实现的：（h=k.hashCode())^h(>>>16)，主要从速度、功效和质量来考虑的，减少系统开销，也不会造成因为高位没有参数下标的计算从而引起的碰撞

6、异或运算符的好处

​ 保证了对象的hashCode32位值只要有一位发生改变，整个hash()返回值就会改变，尽可能减少碰撞

7、数组扩容的过程

创建一个新的数组，其容量为旧数组的两倍，并重新计算旧数组中结点的存储位置。

结点在新数组中的存储位置只有两种：原下标或者原下标+旧数组的大小

8、HashMap的table的容量是如何确定的，以及loadFactory是什么，该容量如何变化，这种变化会带来什么问题

table的数组大小是由capacity这个参数来确定的，默认16，也可以在构造时传入，最大限制1<<30loadFactory是装载因子，主要用来确定table数组是否需要动态扩展，默认是0.75。扩容时，调用resize（）方法，将长度变为原来的两倍（是table的长度，而不是threshold）如果数据很大的情况下，扩展时会带来性能的损失，在性能要求很高的地方，这种损失是致命的。

9、拉链法导致链表过深问题为什么使用红黑树不选择二叉树，为啥不一直使用红黑树

​ 因为二叉查询树在特殊情况下回变成一条线性结构（造成一样的问题），导致遍历查询缓慢，而红黑树可以解决这个问题。

​ 红黑树在插入新数据后，可能需要左旋、右旋、变色这些操作来保持平衡，但是为了保持平衡需要付出一些代价，所以在链表长度较小（8）时，不使用红黑树

10、红黑树的介绍

黑高：叶子节点到根节点的路径黑色节点数量一样叶子节点都是黑色的不能有两个红色节点相连根节点一定是黑色的（红插）插入的节点一定是红色的

11、HashMap、LinkedHashMap、TreeMap有什么区别与使用场景

HashMap：（使用最多）

区别：使用场景：在map中插入、删除和定位元素

LinkedHashMap：

区别：保存了记录的插入顺序，在用Iterator遍历时，先取到的记录肯定是先插入的，遍历比HashMap慢使用场景：在需要输出的顺序和输入的顺序相同的情况下

TreeMap：

区别：实现SortMap接口，能够把它保存的记录根据键排序（默认升序）使用场景：需要按自然顺序或自定义顺序遍历键的情况

12、HashMap和HashTable区别

HashMap是线程不安全的，HashTable是线程安全的，导致效率也低下HashMap最多只允许一条记录的键为null，与韩旭旭多条记录的值为null，而HashTable不允许HashMap默认初始化数组大小为16，扩容为两倍、HashTable为11，扩容为两倍+1

13、Hash介绍

hash是对任意长度的输入输出为相同长度的输出

hash冲突只能尽量规避，不能避免

hash算法：

任何微小的变化hash结果都不同hash不可逆长字符串的hash效率更高hash值尽量散列平均相同的值hash值相同

最后

如果觉得看完有收获，希望能给我点个赞，这将会是我更新的最大动力，感谢各位的支持欢迎各位关注我的公众号【java冢狐】，专注于java和计算机基础知识，保证让你看完有所收获，不信你打我如果看完有不同的意见或者建议，欢迎多多评论一起交流。感谢各位的支持以及厚爱。