哈希表哈希表是一种key-value映射的数据结构。在哈希表中，数据以数组的形式存储，其中每个数据值都有自己唯一的索引值，索引值由哈希表的哈希函数计算得到。下面两步将键哈希值转换为哈希表的索引值。哈希值=哈希函数（key）索引值=哈希值%哈希表长度冲突解决方法对于长度有限的哈希表，冲突是不可避免的。解决冲突的两种方法，拉链法和开放式寻址。zipper方法将冲突位置的元素构造成一个链表。当添加数据发生冲突时，将元素追加到链表中。如下图，添加“SandraDee”时，计算出索引值152与“JohnSmith”冲突，然后追加到链表中。开放式寻址从当前冲突位置开始，按照一定规则检测空位置，并向其中插入元素。更简单的方法是线性检测，它将在固定间隔（通常为1）内循环。如下图，“SandraDee”添加时与“JohnSmith”冲突，通过检测空位插入153，再添加“TedBaker”发现与“SandraDee”冲突，并且然后检测到154空位置插入。性能负载因子负载因子的值是条目数与哈希桶的比值。当负载因子超过理想值时，哈希表将被扩充。例如哈希表的理想值为0.75，初始容量为16，当条目数超过12时，哈希表将扩容并重新哈希。0.6和0.75通常是合理的负载系数。$${\displaystyleloadfactor\(\alpha)={\frac{n}{k}}}$$$n$哈希表中的条目数。$k$桶的数量。影响哈希表性能缓存未命中的主要因素有两个。随着负载因子的增加，缓存未命中的次数增加，搜索和插入的性能显着下降。展开并重新散列。调整大小是一项极其耗时的任务。设置合适的加载因子可以控制扩展的次数。下图可以看出，随着负载因子的增加，cachemiss数开始上升，在0.8之后开始快速攀升。HashMap关于HashMap解释一下它的哈希方法和冲突树。关于hash()，取key的hashCode值，然后高16位和低16位异或，最后取模。staticfinalinthash(Objectkey){//jdk1.8&jdk1.7inth;//h=key.hashCode()获取hashCode值//h^(h>>>16)结合高16位和低16位异或返回(key==null)?0:(h=key.hashCode())^(h>>>16);}//jdk1.7staticintindexFor(inth,intlength){returnh&(length-1);}//jdk1。8(n-1)&hash将高16位和低16位进行异或运算，增加低位的随机性。关于随机性，网上有个测试例子：他随机抽取352个字符串，测试不同长度数组下的碰撞概率。结果表明，当HashMap数组长度为2^9=512时，直接取hashCode有103次冲突，高低位异或后有92次冲突。https://www.todaysoftmag.com/...冲突树HashMap使用拉链法解决冲突。在jdk1.8中，当一个bucket链表节点超过TREEIFY_THRESHOLD=8时，链表会转为红黑树，当bucket中的节点被移除或rehashed小于UNTREEIFY_THRESHOLD=6时，红黑树树将被转换成一个普通的链表。链表的元素从头节点遍历到对应节点，时间复杂度为O(N)。红黑树基于二叉树结构，时间复杂度为O(logN)，所以当元素过多时，使用红黑树存储可以提高查找效率。但是单个树节点需要占用的空间是普通节点的两倍左右，所以树和链表的使用是时间和空间权衡的结果。为什么树的阈值是8？HashMap文档中有这样的描述。一般来说，哈希桶上的链表节点数呈现泊松分布。理想情况下，在随机哈希码下，bin中*节点的频率遵循泊松分布*（http://en.wikipedia.org/wiki/Poisson_distribution），默认调整大小*阈值为0.75，*参数平均约为0.5，尽管由于*调整粒度而具有很大的差异。忽略方差，列表大小k的预期*出现次数为(exp(-0.5)*pow(0.5,k)/*factorial(k))。第一个值是：**0:0.60653066*1:0.30326533*2:0.07581633*3:0.01263606*4:0.00157952*5:0.00015795*6:0.00001316*0:000多于6:0是泊松分布？泊松分布描述了某一事件在一定时间内发生的特定概率。泊松分布可以通过平均值来估计事件发生的概率。$$P(N(t)=n)=\frac{(\lambdat)^ne^{-\lambdat}}{n!}$$$P$概率；$N$某种函数关系；$t$时间；$n$出现的次数；例如，一个程序员平均每天写3个错误，表示为\(P(N(1)=3)\)。由此，我们还可以得到：他明天写1个bug的概率：0.1493612051他明天写2个bug的概率：0.2240418077他明天写3个bug的概率：0.2240418077他明天写10个bug的概率明天的错误：0.0008101512/***@paramn节点数*@paramr平均数*/publicstaticStringpoisson(intn,doubler){doublevalue=Math.exp(-r)*Math.pow(r,n)/IntMath.factorial(n);returnnewBigDecimal(value).setScale(10,ROUND_HALF_UP).toPlainString();}假设HashMap有\(n\)条数据，负载因子为\(k\)，则HashMap的最小长度为\(\frac{n}{k}\)，最大值大约是\(\frac{2n}{k}\)（容量必须是2的幂）所以平均值是\(\frac{3n}{2k}\)，每个桶的平均节点数为$$n\div(\frac{3n}{2k})=\frac{2k}{3}=\frac{2\times0.75}{3}=0.5$$HashMap默认的负载因子是0.75，所以每个桶的平均节点数是0.5。代入泊松公式得到以下数据1个节点1个桶的概率：0.303265329911个桶2个节点的概率：0.07581633251个桶3个节点的概率：0.012636055415541个桶4个节点的概率：0.00157950691的概率5个节点在6个节点的0.00015795071个桶中：0.00001316261个桶中的7个节点节点的概率：0.000000940218个节点出现在一个桶中的概率：0.0000000588树化是哈希极其糟糕的情况下的最后手段，8个节点出现在一个桶中的概率小于千万分之一，所以TREEIFY_THRESHOLD=8。总结哈希表是一种键值映射数据结构。解决冲突的方法有两种：拉链法和开放寻址法。合理设置负载因子和初始容量，避免过多的扩容操作和缓存丢失。了解HashMap的哈希方法和冲突树。
