前言假设现在有一个很长的文档，如果你想统计文档中的每个词在文档中出现了多少次，应该怎么办？非常简单！我们可以构建一个HashMap，String类型为Key，Int类型为Value。遍历文档中的每个词word，在键值对中找到key为word的项，对相关值进行自增操作。如果key=word项在HashMap中不存在，我们会插入一个(word,1)项来表示新增。这样，每组键值对就代表了某个词对应的数字。遍历整个文档后，我们就可以得到每个词的个数。简单实现，代码示例如下：Stringdoc="越版飞羽";String[]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(地图);}}HashMap是如何高效统计对应词的个数的？下面我们一步一步来研究！首先，我们看看是不是只统计某个词的个数？我们只需要开一个变量，用同样的方式遍历所有的单词。当我们遇到与目标词相同的词时，我们将自动增加变量；当遍历完成后，我们就可以得到单词的个数。我们可以列出所有可能的词，每个词，用一个单独的变量统计它出现的次数，遍历所有的词，判断当前词应该累加到哪个变量中。importjava.util.HashMap;importjava.util.Map;publicclassMain{publicstaticvoidmain(String[]args){int[]cnt=newint[20000];Stringdoc="abcd";String[]words=doc.split("");整数=0；整数b=0;整数c=0；诠释d=0;for(Strings:words){if(s=="a")a++;如果(s=="b")b++;如果(s=="c")C++;如果(s=="d")d++;}}}注意：这段代码显然有两个大问题。words和counter的映射关系是通过一堆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;对于(charc:s.toCharArray()){tmp*=26;tmp+=(c-'a');}cnt[tmp]++;}字符串目标="a";整数散列=0;对于(charc:target.toCharArray()){hash*=26;散列+=c-'a';}系统.out.println(cnt[hash]);}}这样，当我们统计N个词出现的次数时，整体复杂度仅为O(N)，明显比原来遍历字典的方法效率更高。这其实就是散列的思想。优化3使用hash！哈希函数的本质是将一个更大的、可能不连续的空间（比如所有的单词）映射到一个空间有限的数组中，从而使数组可以根据下标快速随机化O(1)访问数组元素的能力.但是设计一个合理的哈希函数是一件非常困难的事情。例如，对于26进制的哈希值，对一个大质数进行模运算。只有这样才能用相对有限的计数数组空间来表示整个哈希表。取模后，我们很快会发现，可能会出现这样的情况，两个不同的词用26base表示，取模后得到的值很可能是相同的。这个问题称为散列冲突。如何实现最后，让我们考虑一下哈希函数需要如何设计。以JDK（JDK14）的HashMap为例：主要是在java.util下的HashMap中实现，是最简单的不考虑并发的基于hash的Map实现。找到用于计算哈希值的哈希方法：staticfinalinthash(Objectkey){inth;返回（键==空）？0:(h=key.hashCode())^(h>>>16);}可以发现对key.hashCode()进行了特殊的位操作。Hashcode方法：Java中每个对象在生成的时候都会生成一个对应的hashcode。当然数据类型不同，hashcode的计算方式也不同，但是会保证有两个相同的对象，对应的hashcode也是一样的。因此，在比较两个对象是否相等时，我们可以先比较hashcodes是否一致。如果不一致，就不需要继续调用equals，大大降低了比较对象是否相等的开销。我们来看看JDK中String类型的hashcode是如何计算的。进入java.lang包查看String类型的实现：//在任何可能读取这些字段的情况下，此方法中的计算都保持正确。在没有明确的内存栅栏或类似的并发原语的情况下，允许这是正确的必要限制//我们只能为给定的//String实例写入这两个字段之一，并且计算是幂等的和派生的//来自不可变状态inth=hash;如果（h==0&&！hashIsZero）{h=isLatin1（）？StringLatin1.hashCode(值):StringUTF16.hashCode(值);如果(h==0){hashIsZero=true;}else{散列=h;}}returnh;}Latin和UTF16是两个字符串的编码格式，实现思路其实差不多。我们看一下StringUTF16中的hashcode实现：publicstaticinthashCode(byte[]value){inth=0;intlength=value.length>>1;for(inti=0;i
