前言假设有一个很长的文档。如果你想统计文档中的每个单词在文档中出现了多少次，应该怎么办？这很容易！我们可以构建一个HashMap，以String类型为Key，Int类型为Value；遍历文档中的每个单词word，在键值对中找到key为word的项，对相关值进行自增操作。如果key=word项在HashMap中不存在，我们会插入一个(word,1)项来表示新增。这样，每组键值对就代表了某个词对应的数字。遍历整个文档后，我们就可以得到每个词的个数。简单实现，代码示例如下：words=doc.split("");for(Strings:words){if(!map.containsKey(s)){map.put(s,1);}else{map.put(s,map.get(s)+1);}}System.out.println(map);}}HashMap是如何高效统计对应单词个数的？下面我们一步一步来研究！首先我们看看是不是只统计某个词的个数？我们只需要开一个变量，遍历所有的词，遇到和目标词相同的词，变量就自增；遍历完成后，我们就可以得到单词的个数。我们可以列出所有可能的词，每个词，用一个单独的变量统计它出现的次数，遍历所有的词，判断当前词应该累加到哪个变量中。importjava.util.HashMap;importjava.util.Map;publicclassMain{publicstaticvoidmain(String[]args){int[]cnt=newint[20000];Stringdoc="abcd";String[]words=doc.split("");inta=0;intb=0;intc=0;intd=0;for(Strings:words){if(s=="a")a++;if(s=="b")b++;if(s=="c")c++;if(s=="d")d++;}}}注：这样的代码明显有两个大问题：words和counters的映射关系是通过一堆if-else写死的，很差保持;所有可能的词都必须知道，如果遇到新词，就没有办法处理了。优化1我们可以开一个数组来维护计数器。具体做法是对每个单词进行编号，直接将数字下标对应的数组元素作为其计数器。我们可以创建两个数组：第一个数组用来存放所有的单词，数组的下标是单词编号，我们称之为字典数组；第二个数组用来存放每个单词对应的计数器，我们称之为Count数组。每遇到一个新词，就遍历字典数组。如果没有出现，我们将当前单词插入字典数组的末尾。这样一来，整体时间复杂度比较高，还是不够。优化2优化方法：一是我们维护一个有序的数据结构，让比较和插入的过程更加高效，而不是遍历每个元素去一个一个判断。另一种思路是，能不能找到一种方法，直接根据字符串快速计算出数字，并在O(1)时间内将这个数字映射到一个可以根据下标访问的数组。以单词为例，一个英文单词的每个字母只能是a-z。我们用0来表示a，1来表示b，以此类推，用25来表示z，然后把一个词当成一个十六进制数。importjava.util.HashMap;importjava.util.Map;publicclassMain{publicstaticvoidmain(String[]args){int[]cnt=newint[20000];Stringdoc="abcd";String[]words=doc.split("");for(Strings:words){inttmp=0;for(charc:s.toCharArray()){tmp*=26;tmp+=(c-'a');}cnt[tmp]++;}Stringtarget="a";inthash=0;for(charc:target.toCharArray()){hash*=26;hash+=c-'a';}System.out.println(cnt[hash]);}}所以我们数N当词数出现时，整体复杂度仅为O(N)，明显比原来遍历字典的方法效率更高。这其实就是散列的思想。优化3使用哈希！哈希函数的本质是将更大的、可能不连续的空间（比如所有的单词）映射到一个空间有限的数组中，从而借用数组的能力，根据下标O(1)快速随机访问数组元素.但是设计一个合理的哈希函数是一件非常困难的事情。例如，对于26进制的哈希值，对一个大质数进行模运算。只有这样才能用相对有限的计数数组空间来表示整个哈希表。取模后，我们很快会发现，可能会出现这样的情况，两个不同的词用26base表示，取模后得到的值很可能是相同的。这个问题称为散列冲突。如何实现最后，让我们考虑一下哈希函数需要如何设计。以JDK（JDK14）的HashMap为例：主要是在java.util下的HashMap中实现，是最简单的不考虑并发的基于hash的Map实现。找到计算hash值的hash方法：staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h>>>16);}可以找到它是对key.hashCode()的特殊位操作。hashcode方法在Java中生成每个对象时都会生成对应的hashcode。当然不同的数据类型hashcode的计算方式不同，但是必须保证两个对象相同，对应的hashcode也相同；所以在比较两个对象是否相等的时候，我们可以先比较hashcode是否一致，如果不一致就不需要继续调用equals，大大降低了比较对象是否相等的开销。我们来看看JDK中String类型的hashcode是如何计算的。Let'senterthejava.langpackagetoviewtheimplementationoftheStringtype:publicinthashCode(){//ThehashorhashIsZerofieldsaresubjecttoabenigndatarace,//makingitcrucialtoensurethatanyobservableresultofthe//calculationinthismethodstayscorrectunderanypossiblereadof//thesefields.Necessaryrestrictionstoallowthistobecorrect//withoutexplicitmemoryfencesorsimilarconcurrencyprimitivesis//thatwecaneveronlywritetooneofthesetwofieldsforagiven//Stringinstance,andthatthecomputationisidempotentandderived//fromimmutablestateinth=hash;if(h==0&&!hashIsZero){h=isLatin1()?StringLatin1.hashCode(值):StringUTF16.hashCode(值);if(h==0){hashIsZero=true;}else{hash=h;}}returnh;}拉丁和UTF16是字符串的两种编码格式，实现思路其实差不多，来看看StringUTF16的实现哈希码在：publicstaticinthashCode(byte[]value){inth=0;intlength=value.length>>1;for(inti=0;i
