1.什么是数组？忘了在哪本书里看到过这样一句话“所有的数据结构都是数组的进化”。想想其实也有道理，因为计算机的内存其实就是一个线性的存储空间。Java示例代码：int[]array=newint[5]忽略对象头信息和数组长度信息，JVM在执行过程中会在堆中分配20字节的内存空间，看起来是这样的：这样的数据结构可以通过数组下标访问数据非常方便，但查找时需要遍历数组，平均时间复杂度为O(n/2)。当数据量很大或者查找操作比较频繁的时候，这样的遍历操作几乎是不能接受的。那么，如何才能在更短的时间内快速找到数据呢？2.二分查找如果数组中的元素已经排好了序，那么自然的办法就是使用二分查找。比如有一个整数数组，长度为1000，数组中的整数从小到大排列。如果我想知道6000是否在这个数组中。那我可以先查array[500]的个数是不是6000，array[500]的个数是否小于6000，再查array[750]所在位置的数……以此类推，之后最多重复10次，即可确定结果。该算法的时间复杂度为O(logN)。然而，在大多数情况下，数组元素是无序的，排序所需的时间复杂度O(NlogN)通常远远超过遍历所需的时间。那么，问题又回到了原点。如何在无序数据中快速查找数据？3.懵懂思维还记得刚学编程的时候看过《编程珠玑》。里面有一段描述：1970年代MikeLesk为电话公司做了一个电话号码查找功能，比如输入LESK*M**6*对应的数字键5375，可以返回正确的电话号码或者可选列表，错误匹配率仅为0.2%。如何做呢？那时候根本不懂数据结构和算法。还原当时天马行空的思考过程，看起来还是很有意思的。1.将所有的数字相加（*键为11），5375*6*的和为48。输入的总和大多不超过100，也就是说前100位会聚集上万个电话号码的数组，所以这是不可行的。2、乘法将所有的数相乘，乘积为381150。这似乎是可行的，但是有这样一个问题：lesk、lsek、slke……的乘积是一样的，而且每个数键也对应3个字母，表示重复的概率会很高。3、乘法改进①字母相同但字母顺序不同的字符串可以这样避免冲突：先将每个数字乘以序号，再乘以其他值。②每个数字键对应3个英文字母。如果用户不在数字键中输入该字母的序号，则无法进一步准确计算。能考虑的方向只能根据给定的词表做概率统计，就不考虑了。4.位置冲突即使使用改进的乘法，不同名字和字母计算的乘积仍然可能重复，那么当发生冲突时应该怎么办？依次保存到下一个空位置？想想看，这行不通。如果下一个空白位置恰好是另一组字母的产物，则会发生二次冲突。幸运的是，还有素数。一个质数只能被1和它本身整除，所以上面乘法得到的任何乘积都不可能是质数，所以质数位置不保存电话号码。于是，从当前乘积开始，向右搜索下一个素数，如果素数位置还在，则继续搜索下一个最近的素数……至此，问题似乎解决了。用户输入一串数字，根据公式计算乘积，返回下标位置的电话号码。如果不正确，则依次查找后面的质数，直到某个质数下标的数组元素为空，最后返回所有找到的电话号码。在大多数情况下，查找电话号码只需要O(1)的时间复杂度。5.数组太大。唯一的问题是按照上面的思路创建的数组太大了。一个名字有10个字母。如果每个字母对应的数字都是9，那么最终得到的结果大约是9的17次方。这意味着要创建一个大小为9^17的数组，是完全不可行的。6、后来即使不考虑数组太大的因素，以我当时初学编程的水平也写不出这样的程序。我之所以还原这个思考过程，是因为我觉得独立思考的过程非常有趣，也很有价值。想一想，其实现有的算法都是那些大牛在实际工程中一步步寻找解决方案最终推导出来的。所以，在工程中遇到一些难题时，只要愿意去思考分解问题，针对每一个小问题去寻求解决方案，那么很多所谓的难题是可以迎刃而解的。看完《数据结构与算法分析.Java语言描述》，我才知道我的想法其实是OpenAddressing。JDK的HashMap使用分离链。不同点：增加了桶的概念，用于保存冲突的数据；执行取余运算以减小数组的大小。那么，让我们来谈谈Java中的HashMap。四、HashMap结构及算法详解HashMap的本质还是一个数组，而且是一个变长的多维数组，类似于下图的结构：1.简单介绍一下链表的头节点存储在HashMap中的数组中。保存数据：计算出key的hashCode，然后与数组的长度进行取余运算，得到数组下标（链表的头节点）。如果该位置为空，则生成一个新的链表节点并保存到数组中。如果位置不为空，则循环比较链表的每个节点：如果已经有相同key的节点，则覆盖旧节点；如果没有相同key的节点，新节点将作为链表的尾节点（注意：查看JDK1.8源码，新节点总是添加到链表的末尾，而不是被链表的头节点，如JDK1.6）。查找数据：计算出key的hashCode，然后与数组的长度进行取余运算，得到数组下标（链表的头节点）。如果链表不为空，先比较第一个节点。如果第一个节点的key相同（hashCode相同且equals为真），直接返回第一个节点的值；如果第一个节点的key不同，则依次遍历比较链表中的其他节点，返回相同key的值。节点的值（如果没有找到具有相同键的节点，则为null）。HashMap引入链表的目的就是为了解决上一节讨论的重复冲突问题。注意：如果所有key的hashcode都一样，假设都是0，那么0%4=0，所有的元素都会保存到链表0中，需要遍历链表0来保存和查找每一个数据。那么，此时的HashMap本质上已经退化成了一个链表，时间复杂度也从设计的O(1)增加到了O(n/2)。为了尽可能将HashMap查找和保存的时间复杂度保持在O(1)，需要将元素均匀分布在每个链表中，即每个链表只保存一个元素。那么影响因素有哪些呢？一是key的hashcode不能重复。如果重复，肯定会有一个链表至少保存2个元素；二是哈希函数的设计。元素应该分布在一个长度为10的数组中，不管你怎么计算，都会有一个链表存储多个元素，最好的情况是每个链表存储10个；下面将详细介绍这三个因素的算法设计。2.hashcode生成这是String类的hashCode生成代码。 publicinthashCode(){ inth=hash; if(h==0&&value.length>0){ charval[]=value; for(inti=0;i>>16); }下图仍然以字符串“abcabcabcabcabc”为例，使用上述方法得到运行过程和结果.为什么在执行XOR运算之前要先无符号右移16位？看看下图中的二元与运算，你就明白了。你会发现，只要二进制数的后4位不变，不管前面的二进制位如何变化，都会出现相同的结果。为了防止高位变化而低位不变导致运算结果相同，需要加上高位的变化，并对整数的二进制位的高位和低位进行异或运算得到这个效果。为什么要用AND运算？因为hash函数的计算公式是hashCode%tableSize，当tableSize为2的n次方（n≥1）时，相当于hashCode&(tableSize–1)。扰动函数优化前：1954974080%16=1954974080&(16–1)=0扰动函数优化后：1955003654%16=1955003654&(16–1)=6这就是为什么需要加入扰动函数的原因。源码详解在代码讲解之前需要补充一点，jdk1.8引入了红黑树来解决大量冲突时的查找效率，所以当一个链表中的数据达到一定的时候size，链表将转换为红黑树。所以在jdk1.8中，HashMap查找和保存数据的最大时间复杂度其实就是红黑树的时间复杂度O(logN)。下面是HashMap中保存数据的方法源码。相信经过上面的描述，理解这段代码就非常容易了。 finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){ Node[]tab; //HashMap数组 Nodep; //初始化要保存的数据 intn; //数组容量 inti; //数组下标 /*如果数组为空或0,初始容量为16*/ if((tab=table)==null||(n=tab.length)==0){ n=(tab=resize()).length; } /*使用哈希函数获取数组位置（如果为空，则将新节点存入数组）*/ if((p=tab[i=(n-1)&hash])==null){ tab[i]=newNode(hash,key,value,null); } /*如果数组位置已经有值，使用下面的方法保存数据*/ else{ Nodee; //临时节点保存新值 Kk; //临时变量用于比较key //如果头节点新节点的key的hash值相同且key的值相等，则将e赋值给老节点 if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k)))){ e=p; } //如果头节点是红黑树节点，那么e将被保存为树节点 elseif(pinstanceofTreeNode){ e=((TreeNode)p).putTreeVal(this,tab,hash,key,value); } //如果头节点相同与新节点不同，且头节点不是红黑树节点，则循环比较链表的所有节点 else{ for(intbinCount=0;;++binCount){ if((e=p.next)==null){ //如果一直到链表末尾都没有找到相同key的节点，则将新节点作为最后一个节点加入链表 p.next=newNode(hash,key,value,null); //如果链表的节点数大于等于8-1，则转为红黑树；转换成红黑树的最小节点数是8 if(binCount>=TREEIFY_THRESHOLD-1){ treeifyBin(tab,hash); } break; } //如果循环中发现新旧key的值相同，则跳转：是否覆盖旧值 if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k)))){ break; } p=e; } } //是否覆盖旧值 if(e!=null){ VoldValue=e.value; //如果新值不为空且（允许修改旧值oroldvalueisempty),覆盖旧节点的value if(!onlyIfAbsent||oldValue==null){ e.value=value; } afterNodeAccess(e); //回调函数，这里是一个空函数，但是这个方法是在linkedHashMap中实现的 returnoldValue; //返回旧值 } } //用于比较判断其他线程在遍历集合时是否修改了集合。详情请搜索fail-fast快速失败机制 ++modCount；当数量大于允许容量时扩容HashMap中允许的容量为数组长度*填充因子（默认0.75） if(++size>threshold){ resize(); } //回调函数，这里是一个空函数，但是在linkedHashMap中实现了这个方法 afterNodeInsertion(evict); returnnull; }简化伪代码 putval(key,value){ index=key.hashcode%tablesize; if(null==table[index]){ table[index]=newnode(key,value); }else{ firstNode=table[index]; nextNode=firstNode.next; while(nextNode.hasNextNode()){ //如果发现有相同key的旧节点，则覆盖旧节点 if(key==nextNode.key){ nextNode=newnode(key,value); break; } //如果队尾还没有找到相同key的旧节点，则将新节点加入最后一个节点结束 if(nextNode.next==null){ nextNode.next=newnode(key,value); break; } nextNode=nextNode。next; } } }链表的大小设计在t中已经提到代码注释，这里单独讨论。①容量选择HashMap初始容量为1<<4，即16，以后每次扩容都是size<<1，即扩容为原来容量的2倍。这样设计是因为2^n-1（n≥1）的二进制表示永远是一个重复的1，方便求余运算。 中的建议是容量最好是质数，这样有助于减少冲突，但是没有给出证明和实验数据。素数虽然是神奇的数字，但个人感觉在这里用处不是特别大。根据公式index=hashCode%size，无论size是质数还是非质数，index的取值范围都在0到(size-1)之间。看来hashCode的随机性真的是决定性的。这里先不下结论，后面写一个随机函数，比较素数和非素数的重复率。②填充因子默认的填充因子是0.75，也就是说如果数组容量是16，那么当key的个数大于12时，HashMap就会扩容。填充因子设计为0.75，以平衡时间和空间性能。太小，阵列太稀疏，空间利用率不高；如果太大，会增加冲突，增加时间复杂度。关于其他红黑树是在JDK1.8中引入的。用简单的语言来解释红黑树的数据结构、增删改查操作和时间复杂度分析是一项复杂而艰巨的任务，更适合个人描述，留待以后.五、最小完美哈希函数（MinimalPerfectHashFunction，MPHF）Jdk中的HashMap解决了任意数据集的时间复杂度问题，设计的哈希函数在未知数据集的情况下具有良好的性能。但是如果有一个已知的数据集（比如Java关键字集合），如何设计一个hash函数来同时满足以下两个方面的要求：（1）容器容量和大小完全一致数据集；(2)没有冲突。也就是说，当给定一个数据集时，如果一个散列函数允许容器的每个节点有一个且只有一个数据元素，这样的散列函数称为最小完美散列函数。最近在研究编译原理，提到如何解决关键字集的O(1)时间复杂度搜索问题，提到可以使用最小完美哈希函数。看到这样一个名词，立马觉得很好，很高大上。
