其实刚开始接触HashMap的时候看别人博客以及源码是真的一头雾水,最后还是决定找视频入下门比较合适
https://www.bilibili.com/video/av24032788
关于HashMap的面试题这两篇讲的不错:
https://blog.csdn.net/LE_912/article/details/80599869
https://blog.csdn.net/u012512634/article/details/72735183
关于HahMap中的变量解释这篇讲的不错:
https://www.hollischuang.com/archives/2416
关于HashMap为什么不是线程安全这篇讲的不错:
https://www.cnblogs.com/qiumingcheng/p/5259892.html
关于Hash算法讲解:
https://www.cnblogs.com/xiohao/p/4389672.html
解决Hash算法冲突的四种方法:
https://taoyongpan.iteye.com/blog/2401102
注意:hashmap和hashset是采用拉链法解决冲突的.
ConcurrentHashMap在jdk1.7和1.8的区别
https://baijiahao.baidu.com/s?id=1617089947709260129&wfr=spider&for=pc
ConcurrentHashMap的1.8版本,取消了Segment分段锁的结构,而是采用CAS算法以及Synchronized的方式,数组结构和HashMap一致,锁的颗粒度调整为每个table元素,节点的value和next采用 volatile修饰
简单总结下HashMap:
HashMap底层数据结构:数组+链表+红黑树,可以接受null的key和value值.数组默认初始化大小为16,当链接长度大于8的时候就会转换为红黑树,实现logn的复杂度查询,如果小于6就会再次转换为链表.
其中的结构单体是entry,包括四个元素:key,value,next,hash值.
还有一些全局变量:
HashMap中size表示当前共有多少个KV对，capacity表示当前HashMap的容量是多少，默认值是16，每次扩容都是成倍的。loadFactor是装载因子，当Map中元素个数超过loadFactor capacity的值时，会触发扩容。loadFactor capacity可以用threshold表示。
如何扩容:
默认数组大小为16,扩容每次都是两倍,扩容因子是0.75,即当数组容量达到12的时候就扩容,扩容的时候会创建一个新的数组,然后将原来数组的entry们复制到新数组中,原数组需要null,这样才会被gc回收.注意之前的entry的位置只有两种情况,一种是原来位置,一种是原来位置+原容量大小.这个位置的判断是hash值&初始容量即16,如果高位为0则原来位置,如果高位为1则位置变为原来位置+扩容大小.
如何查找:
首先根据key的hashcode()找到数组的下标,然后根据key的equals()找到数组链表上的对应的entry.
注意这里首先获取hash值有个函数是将高16位和低16位做异或运算,得到hash值.根据hash值&(容量-1)找到数组下标,如果碰撞了就使用equals.
问题:为什么高低位要异或?
因为如果不异或操作,那得到的hash值只保留了低位的特性,和(容量-1)&操作的时候如果数组容量小,容易增加碰撞概率,因为只和低位的&操作,所以需要将hash保留高位特性,这样得到的hash值可以尽量让Node落点分布均匀,减少碰撞概率.
问题:为什么数组容量要2的幂次方?
因为寻找数组下标是依靠这个代码:数组[hash值&(容量-1)]
- 容量-1是为了让得到的下标结果控制在数组大小范围内,不越界.
- 二进制位运算的时候2幂次方-1的结果肯定是111... 可以合理分配数组的位置,如果是其他数-1的话,二进制肯定会有0 如 1101 这样子数组下标判断的时候只会考虑到第1,2,4位, 而第三位就会被忽略,如1011等无法访问,导致数组下标分布不均匀.
put过程
1.判断键值对数组 table 是否为空或为 null,否则执行 resize()进行扩容;
2.根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加,转向6,如果 table[i]不为空,转向3;
3.判断 table[i]的首个元素是否和 key 一样,如果相同直接覆盖 value,否则转向4,这里的相同指的是 hashCode 以及 equals;
4.判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向5;
5.遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现 key 已经存在直接覆盖 value 即可;
6.插入成功后,判断实际存在的键值对数量 size 是否超多了最大容量 threshold,如果超过,进行扩容。
hashMap和hashTable区别?
- hashMap是非线程安全的,hashtable是线程安全的,其实就是在操作方法即get()和put()上加上synchronized.
- hashMap可以添加key和value为null的值,而hashTable不行.
如何将hashMap变为线程安全呢?
可以使用Collections.synchronizedMap(map)方法.
什么是ConcurentHashMap?现在用ConcurrentHashMap代替hashTable.
ConcurrentHashMap采用分段锁,内部分为很多段,每段都相当于一个小的HashTable,他们有自己的锁,只要多个修改操作发生在不同的段上,就可以并发进行.
为了效率一般都会初始化HashMap容量,在这里jdk1.8是构造函数的时候就会实现扩容,而jdk1.7需要在第一次put的时候才会扩容.
jdk1.8构造函数传入的数字并不是HashMap的容量,而是 第一个大于传入数字的2次幂数,如
传入1-->容量2
传入3-->容量4
传入7-->容量8
面试题：初始构造器设置大小为25，hashmap实际大小是多少？注意:hashmap赋值初始值容量的时候,一定是大于等于赋值数的2^n的值.
实际是64，首先，找到比25大的2^n，是32，负载因子为0.75，则能装24个，25>24，触发扩容，为64.
面试中关于HashMap的时间复杂度O(1)的思考
只有理想状态下是O(n)
参考这篇文章:
https://blog.csdn.net/donggua3694857/article/details/64127131/
题外话1:
常考ArrayList和Vector区别?
vector是线程安全的,它在add方法的时候使用了同步函数,方法上加了synchronized关键字,而ArrayList的add方法没有添加这个关键字.
当存储空间不足的时候,ArrayList默认大小变为原来的1.5倍,而vector默认大小变为原来的2倍.
题外话2:HashSet底层是HashMap,这个打死也没想到.实现Set接口,由哈希表支持,不保证set的迭代顺序,允许null元素.
- 默认构造函数是构建一个初始容量为16,负载因子为0.75的HashMap.封装了一个HashMap对象来存储所有的集合元素,所有放入HashSet中的集合元素实际由HashMap的key来保存,而HashMap的value则存储了一个PRESENT,他是一个静态的Object对象.
- 将一个对象放入HashSet中保存,重写该类的equals和hashcode方法很重要,而且这两个方法的返回值必须保持一致:当该类的两个hashcode返回值相同时,他们通过equals方法比较.
- HashSet的其他操作都是基于HashMap的
题外话3:
关于Hash值如果采用求余算法的话,那除数要为不大于散列表长度的最大素数或者不包含质因数小于20的合数.
原因:
除数取合数的话，一旦数据是以合数的某个因子为间隔增长的，那么哈希值只会是几个值不停的重复，冲突很严重，而素数就不会发生这种情况
参考:
https://blog.csdn.net/w_y_x_y/article/details/82288178
http://www.nowamagic.net/academy/detail/3008040
