前几天在群里看到有人在讨论为什么hashmap中的loadingfactor默认是0.75。HashMap源码中的负载因子staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;当时我觉得应该是“哈希碰撞”和“空间利用”的矛盾之间的折衷。同数据结构不是查询快就是插入快一样，hashmap是一种插入慢查询快的数据结构。加载因子是Hsah表中元素被填充的程度。loadingfactor越大，填充的元素越多，空间利用率越高，但是冲突的几率也增加了。反之，loadingfactor越小，填充的元素越少，冲突的几率会降低，但空间浪费也越大。冲突的可能性越大，搜索的成本就越高。反之，搜索成本较小。因此，必须在“冲突机会”和“空间利用”之间找到平衡和妥协。但为什么必须是0.75？0.6不是0.8，而是本着不太大的问题的精神继续深入挖掘。在此之前，先简单补充一下本文需要的一些基础知识：1.冲突的定义：假设哈希表的地址集为[0,n)，冲突是指在该位置已经存在一条记录关键字得到的哈希地址为j(0<=j<=n-1)。关键字得到的哈希地址上已经有记录，所以称为冲突2.冲突处理：为关键字的记录再取一个“空”的哈希地址。即在处理hash地址冲突时，如果得到的另一个hash地址H1仍然冲突，则寻找下一个地址H2，如果H2仍然冲突，则寻找H3，直到Hk不冲突，则Hk为记录中的地址桌子。处理冲突的几种方法：1.开放寻址法Hi=(H(key)+di)MODmi=1,2,...k(k<=m-1)其中H(key)是一个hash函数;m是哈希表的长度；di是增量序列。开寻址法按步长大小可分为三种：1）线性探测法（LinearProbing）：di=1,2,3,...,m-1 简单的说，电流冲突position为起点，步长为1，循环查找，直到找到空位置，插入元素。如果循环结束，找不到，说明容器满了。就好比你去街边的饭馆吃饭，问第一个就说满了，然后挨着挨着问有没有位子。2）线性补偿检测法：di=Q 下一个位置满足Hi=(H(key)+Q)modmi=1,2,...k(k<=m-1)，要求Q和m是互质的，因此哈希表中的所有单元格都可以被检测到。继续上面的例子，现在不是去每个房子问，而是拿出你的计算器算一算，然后问每个Q房子有没有空位。3）伪随机检测和重新散列：di=伪随机数序列。还是一样的例子，看心情选了store问下缺点：这种方法创建的hash表在冲突多的时候容易堆数据，这时候搜索起来不友好；删除节点不能简单地将被删除节点的空间设置为空，否则会截断其后填充在哈希表中的同义词节点的搜索路径。因此，当对使用开放地址法处理冲突的哈希表进行删除操作时，被删除的节点只能被标记为已删除，而节点不能被删除。当空间已满时，必须建立溢出表来存储多余的元素。2、重新散列法Hi=RHi(key),i=1,2,...kRHi都是不同的散列函数，即当同义词产生地址冲突时，计算另一个散列函数地址，直到不发生冲突为止。这种方法不太容易聚类，但会增加计算时间。缺点：增加计算时间。3.建立公共溢出区假设哈希函数的取值范围为[0,m-1]，设置向量HashTable[0...m-1]为基础表，为每个分量存储一条记录，并设置一个向量OverTable[0....v]是一个溢出表。基本表中的所有关键字及其关键字同义的记录，无论通过哈希函数得到的哈希地址是什么，一旦发生冲突，就会被填充到溢出表中。简单的说就是新建一个表来存放冲突的元素。4、链地址法（拉链法）将关键字为同义词的所有记录存储在同一个线性链表中，即将冲突位置的元素构造成一个链表。zipper方法的优点：zipper方法处理冲突简单，没有堆积现象，即非同义词永远不会冲突，所以平均搜索长度更短；由于zipper方法中每个链表上的节点空间是动态申请的，所以更适合建表前无法确定表长的情况；在拉链法构造的哈希表中，删除节点的操作很容易实现。只需简单地删除链表上的相应节点即可。zipper方式的缺点：指针需要额外的空间，所以当节点大小较小时，开放式寻址方式节省空间，如果将节省下来的指针空间用于扩展哈希表的大小，可以降低填充因子，这又减少了开放寻址方法中的冲突，从而提高了平均搜索速度。JavaHashMap中HashMap的数据结构实际上是一种“链表哈希”数据结构，即数组和链表的结合。看图就知道Java中的hashMap是用zipper的方式来处理冲突的。HashMap有一个初始容量大小，默认是16staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16为了减少冲突的概率，当hashMap数组长度达到临界值时，会触发扩容，rehash所有元素，放入扩容后的容器中，这是一个非常耗时的操作.而这个临界值是由[负载因子]和当前容器的容量决定的：DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR，即默认16x0.75=12时，会触发扩容操作。因此，在使用hash容器时，尽量预估自己的数据量来设置初始值。具体的代码实现要自己去研究HashMap的源码。补充完基础知识，回到正题，为什么加载因子默认为0.75呢？我从hashmap源代码注释中找到了这段话。理想情况下，在随机哈希码下，bin中节点的频率遵循泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution)，默认调整大小阈值0.75的参数平均约为0.5，尽管有很大的由于调整粒度的差异。忽略方差，列表大小k的预期出现次数为(exp(-0.5)*pow(0.5,k)/factorial(k))。Thefirstvalues??are:0:0.606530661:0.303265332:0.075816333:0.012636064:0.001579525:0.000157956:0.000013167:0.000000948:0.00000006more:lessthan1intenmillionUsingrandomhashcodes,thefrequencyofnodesappearinginthehash桶服从泊松分布，给出了桶中元素个数和概率的对照表。从上表我们可以看出，当桶中的元素个数达到8时，概率已经变得很小了，也就是说以0.75为加载因子，几乎不可能每个元素的链表长度collisionposition超过8。好吧，如果再深挖，我们会走到统计这边，所以就此打住，再重申一下，在使用hash容器时，请尽量指定初始容量，并且是2的幂。关于泊松分布的知识请看http://www.ruanyifeng.com/blog/2015/06/poisson-distribution.html#comment-356111作者：EricShinnosuke链接：https://www.jianshu.com/p/dff...来源：简书补充为什么部分是1还是0.5首先说一下hash的数据结构。jdk1.8之前是数组+链表，jdk1.8之后是数组+链表+红黑。当加载因子为1.0时，表示只有当数组的8个值（本图为8）都被填充时，才会发生扩容。这就带来了一个很大的问题，因为Hash冲突是无法避免的。当负载因子为1.0时，意味着会出现大量的Hash冲突，底层的红黑树变得异常复杂。对查询效率极为不利。在这种情况下，牺牲时间来保证空间利用率。当加载因子为0.5时，表示当数组中的元素达到一半时，就会开始扩容。由于填充的元素少了，Hash冲突也会减少，所以底层链表的长度或者红黑树的高度都会变小。查询效率会提高。当负载因子为0.75时，空间利用率比较高，避免了很多Hash冲突，使得底层链表或者红黑树的高度比较低，提高了空间效率。补充一、书籍项目：codeGoogler/ProgramBooks2：视频教程：程序员必读的Java书籍SpringBoot、Spring、Mybatis、Redis、RabbitMQ、SpringCloud，对高并发感觉不错的朋友记得点赞收藏，会在中持续更新未来的精选技术文章！
