现在是晚上11点了,学校屠猪馆的自习室因为太晚要关闭了。勤奋且疲惫的小鲁班也从屠猪馆出来了,正准备回宿舍洗洗睡,由于自习室位置比较偏僻所以是接收不到手机网络信号的,因此小鲁班从兜里掏出手机的时候,信息可真是炸了呀。小鲁班心想,微信群平时都没什么人聊天,今晚肯定是发生了什么大事。仔细一看,才发现原来是小鲁班的室友达摩(光头)拿到了阿里巴巴 Java 开发实习生的 Offer,此时小鲁班真替他室友感到高兴的同时,心里也难免会产生一丝丝的失落感,那是因为自己投了很多份简历,别说拿不拿得到 Offer,就连给面试邀的公司也都寥寥无几。小鲁班这会可真是受到了一万点 真实暴击。 不过小鲁班还是很乐观的,很快调整了心态,带上耳机,慢慢的走回了宿舍,正打算准备向他那神室友达摩取取经。
片刻后~
小鲁班:666,听说你拿到了阿里的 Offer,能透露一下面试内容和技巧吗?
达摩:嘿嘿嘿,没问题鸭,叫声爸爸我就告诉你。
小鲁班:耙耙(表面笑嘻嘻,心里MMP)
达摩:其实我也不是很记得了(请继续装),但我还是记得那么一些。如果你是面的 Java,首先当然是JAVA的基础知识:数据结构(Map / List / Set等)、 设计模式 、算法、线程相关、IO/NIO、序列化等等。其次是高级特征:反射机制,并发与锁,JVM(GC策略,类加载机制,内存模型)等等。
小鲁班:问这么多内容,那岂不是一个人都面试很久吗?
达摩:不是的,面试官一般都会用连环炮的方式提问的。
小鲁班:你说的连环炮是什么意思鸭?
达摩:那我举个例子:
无穷无尽深入,直到你回答不出来或者面试官认为问题到底了。
小鲁班捏了一把汗,我去……这是魔鬼吧,那我们来试试呗(因为小鲁班刚刚在自习室才看了这章的知识,想趁机装一波逼,毕竟刚刚叫了声爸爸~~)
于是达摩 and 小鲁班就开始了对决:
我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时,我们先对键调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。
这里关键点在于指出,HashMap 是在 bucket 中储存键对象和值对象,作为Map.Node 。
简化的模拟数据结构:
Node[] table = new Node[16]; // 散列桶初始化,table class Node { hash; //hash值 key; //键 value; //值 node next; //用于指向链表的下一层(产生冲突,用拉链法) }
考虑特殊情况:如果两个键的 hashcode 相同,你如何获取值对象?
当我们调用 get() 方法,HashMap 会使用键对象的 hashcode 找到 bucket 位置,找到 bucket 位置之后,会调用 keys.equals() 方法去找到链表中正确的节点,最终找到要找的值对象。
原理是如果两个不相等的对象返回不同的 hashcode 的话,那么碰撞的几率就会小些。这就意味着存链表结构减小,这样取值的话就不会频繁调用 equal 方法,从而提高 HashMap 的性能(扰动即 Hash 方法内部的算法实现,目的是让不同对象返回不同hashcode)。
不可变性使得能够缓存不同键的 hashcode,这将提高整个获取对象的速度,使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。
因为 String 是 final,而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的,因为为了要计算 hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的 hashcode 的话,那么就不能从 HashMap 中找到你想要的对象。
我们可以看到,在 hashmap 中要找到某个元素,需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。
前面说过,hashmap 的数据结构是数组和链表的结合,所以我们当然希望这个 hashmap 里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个。那么当我们用 hash 算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。 所以,我们首先想到的就是把 hashcode 对数组长度取模运算。这样一来,元素的分布相对来说是比较均匀的。
但是“模”运算的消耗还是比较大的,能不能找一种更快速、消耗更小的方式?我们来看看 JDK1.8 源码是怎么做的(被楼主修饰了一下)
static final int hash(Object key) { if (key == null){ return 0; } int h; h = key.hashCode();返回散列值也就是hashcode // ^ :按位异或 // >>>:无符号右移,忽略符号位,空位都以0补齐 //其中n是数组的长度,即Map的数组部分初始化长度 return (n-1)&(h ^ (h >>> 16)); }
简单来说就是:
之所以选择红黑树是为了解决二叉查找树的缺陷:二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,造成层次很深的问题),遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡。引入红黑树就是为了查找数据快,解决链表查询深度的问题。我们知道红黑树属于平衡二叉树,为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候,会使用红黑树;如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢。
当冲突发生时,使用某种探查技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找,直到找到给定的地址。按照形成探查序列的方法不同,可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
下面给一个线性探查法的例子:
问题:已知一组关键字为 (26,36,41,38,44,15,68,12,06,51),用除余法构造散列函数,用线性探查法解决冲突构造这组关键字的散列表。
解答:为了减少冲突,通常令装填因子 α 由除余法因子是13的散列函数计算出的上述关键字序列的散列地址为 (0,10,2,12,5,2,3,12,6,12)。
前5个关键字插入时,其相应的地址均为开放地址,故将它们直接插入 T[0]、T[10)、T[2]、T[12] 和 T[5] 中。
当插入第6个关键字15时,其散列地址2(即 h(15)=15%13=2)已被关键字 41(15和41互为同义词)占用。故探查 h1=(2+1)%13=3,此地址开放,所以将 15 放入 T[3] 中。
当插入第7个关键字68时,其散列地址3已被非同义词15先占用,故将其插入到T[4]中。
当插入第8个关键字12时,散列地址12已被同义词38占用,故探查 hl=(12+1)%13=0,而 T[0] 亦被26占用,再探查 h2=(12+2)%13=1,此地址开放,可将12插入其中。
类似地,第9个关键字06直接插入 T[6] 中;而最后一个关键字51插人时,因探查的地址 12,0,1,…,6 均非空,故51插入 T[7] 中。
HashMap 默认的负载因子大小为0.75。也就是说,当一个 Map 填满了75%的 bucket 时候,和其它集合类一样(如 ArrayList 等),将会创建原来 HashMap 大小的两倍的 bucket 数组来重新调整 Map 大小,并将原来的对象放入新的 bucket 数组中。这个过程叫作 rehashing 。
因为它调用 hash 方法找到新的 bucket 位置。这个值只可能在两个地方,一个是原下标的位置,另一种是在下标为 <原下标+原容量> 的位置。
重新调整 HashMap 大小的时候,确实存在条件竞争。
因为如果两个线程都发现 HashMap 需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来。因为移动到新的 bucket 位置的时候,HashMap 并不会将元素放在链表的尾部,而是放在头部。这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。多线程的环境下不使用 HashMap。
HashMap 的容量是有限的。当经过多次元素插入,使得 HashMap 达到一定饱和度时,Key 映射位置发生冲突的几率会逐渐提高。这时候, HashMap 需要扩展它的长度,也就是进行Resize。
(这个过程比较烧脑,暂不作流程图演示,有兴趣去看看我的另一篇博文“ HashMap扩容全过程 ”)
达摩:哎呦,小老弟不错嘛~~意料之外呀
小鲁班:嘿嘿,优秀吧,中场休息一波,我先喝口水
达摩:不仅仅是这些哦,面试官还会问你相关的集合类对比,比如:
首先第一步的时候会尝试获取锁,如果获取失败肯定就有其他线程存在竞争,则利用 scanAndLockForPut() 自旋获取锁。
CocurrentHashMap 抛弃了原有的 Segment 分段锁,采用了 CAS + synchronized
来保证并发安全性。 其中的 val next
都用了 volatile 修饰,保证了可见性。
借助 Unsafe 来实现 native code。CAS有3个操作数,内存值 V、旧的预期值 A、要修改的新值 B。当且仅当预期值 A 和内存值 V 相同时,将内存值V修改为 B,否则什么都不做。Unsafe 借助 CPU 指令 cmpxchg 来实现。
对 sizeCtl 的控制都是用 CAS 来实现的:
解决:对变量增加一个版本号,每次修改,版本号加 1,比较的时候比较版本号。
此时躺着床上的张飞哄了一声:睡觉了睡觉了~
见此不太妙:小鲁班立马回到床上把被子盖过头,心里有一丝丝愉悦感。不对,好像还没洗澡……
by the way
ConcurrentHashMap 在 Java 8 中存在一个 bug 会进入死循环,原因是递归创建 ConcurrentHashMap 对象,但是在 JDK 1.9 已经修复了。场景重现如下:
public class ConcurrentHashMapDemo{ private Map<Integer,Integer> cache =new ConcurrentHashMap<>(15); public static void main(String[]args){ ConcurrentHashMapDemo ch = new ConcurrentHashMapDemo(); System.out.println(ch.fibonaacci(80)); } public int fibonaacci(Integer i){ if(i==0||i ==1) { return i; } return cache.computeIfAbsent(i,(key) -> { System.out.println("fibonaacci : "+key); return fibonaacci(key -1)+fibonaacci(key - 2); }); } }