java 散列,

　　00-1010前言：优化1、优化2、优化3、如何实现总结

　　00-1010假设现在有一个很长的文档。如果要统计文档中的每个单词在文档中出现的次数，应该怎么做？

　　很简单！

　　我们可以构建一个HashMap，String类型作为键，Int类型作为值；

　　遍历文档中的每个单词单词，在键-值对中找到带有该关键字的项，并对相关值进行自增操作。如果HashMap中不存在key=word项，我们将插入一个(word，1)项来表示添加。这样，每组键-值对代表一个单词的相应数字。当遍历整个文档时，我们可以得到每个单词的编号。简单实现下，代码示例如下：

　　导入Java . util . hashmap；导入Java . util . map；public class Test { public static void main(String[]args){ Map Map=new HashMap()；String doc=岳班于飞；string[]words=doc . split()；for(字符串s :字){ if(！map.containsKey(s)) { map.put(s，1)；} else { map.put(s，map . get(s)1)；} } system . out . println(map)；}}那HashMap是如何高效统计对应的字数的呢？下面我们会一步步研究！

　　首先，我们来看看。如果只统计某个词的数量？

　　只需要打开一个变量，遍历所有的单词，遇到和目标单词相同的，才在这个变量上做自增操作；

　　当遍历完成后，我们可以得到这个单词的编号。我们可以列出所有可能的单词。对于每个单词，用单个变量计算其出现的次数，遍历所有单词，并确定当前单词应该累积到哪个变量中。导入Java . util . hashmap；导入Java . util . map；public class Main { public static void Main(String[]args){ int[]CNT=new int[20000]；String doc= a b c dstring[]words=doc . split()；int a=0；int b=0；int c=0；int d=0；for(String s : words){ if(s== a )a；if(s== b )b；if(s== c )c；if(s== d )d；}}}像注意：这样的代码显然有两个大问题：

　　单词和计数器的映射关系是一堆if-else写的，维护的很差；你必须知道所有可能的单词。如果遇到生词，是没有办法处理的。

　　00-1010我们可以打开一个数组来维护计数器。

　　要做到这一点，给每个单词一个数字，只需使用数字对应下标的数组元素作为它的计数器。

　　我们可以建立两个数组：

　　第一个数组用来存放所有的单词，数组的下标是单词的编号，我们称之为字典数组；第二个数组用来存储每个单词对应的计数器，我们称之为计数数组。每当我们遇到一个新单词，我们就遍历字典数组。如果它没有出现，我们将当前单词插入字典数组的末尾。

　　这样整体时间复杂度高，但还是不行。

目录

优化方式：

　　一个是我们维护一个有序的数据结构，让比较和插入的过程更加高效，而不是遍历每一个元素逐一判断。另一个想法是，我们是否可以找到一种方法，直接根据字符串快速计算数字，并将这个数字映射到一个

　　以在O(1)时间内基于下标访问的数组中。以单词为例，英文单词的每个字母只可能是 a-z。

　　我们用0表示a、1表示b，以此类推，用25表示z，然后将一个单词看成一个26进制的数字即可。

import java.util.HashMap;import java.util.Map;public class Main { public static void main(String[] args) { int[] cnt = new int[20000]; String doc = "a b c d"; String[] words = doc.split(" "); for (String s : words) { int tmp = 0; for (char c: s.toCharArray()) { tmp *= 26; tmp += (c - a); } cnt[tmp]++; } String target = "a"; int hash = 0; for (char c: target.toCharArray()) { hash *= 26; hash += c - a; } System.out.println(cnt[hash]); }}

这样我们统计N个单词出现数量的时候，整体只需要O(N)的复杂度，相比于原来的需要遍历字典的做法就明显高效的多。

这其实就是散列的思想了。

 

　　

优化3

使用散列！

　　散列函数的本质，就是将一个更大且可能不连续空间（比如所有的单词），映射到一个空间有限的数组里，从而借用数组基于下标O(1)快速随机访问数组元素的能力。

　　但设计一个合理的散列函数是一个非常难的事情。

　　比如对26进制的哈希值再进行一次对大质数取mod的运算，只有这样才能用比较有限的计数数组空间去表示整个哈希表。取了mod之后，我们很快就会发现，现在可能出现一种情况，把两个不同的单词用26进制表示并取模之后，得到的值很可能是一样的。

　　这个问题被称之为哈希碰撞。

如何实现

最后我们考虑一下散列函数到底需要怎么设计。

　　以JDK（JDK14）的HashMap为例：

　　主要实现在java.util下的HashMap中，这是一个最简单的不考虑并发的、基于散列的Map实现。找到其中用于计算哈希值的hash方法：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

可以发现就是对key.hashCode()进行了一次特别的位运算。

　　hashcode方法

　　在Java中每个对象生成时都会产生一个对应的hashcode。

　　当然数据类型不同，hashcode的计算方式是不一样的，但一定会保证的是两个一样的对象，对应的hashcode也是一样的；所以在比较两个对象是否相等时，我们可以先比较hashcode是否一致，如果不一致，就不需要继续调用equals，大大降低了比较对象相等的代价。

　　我们就一起来看看JDK中对String类型的hashcode是怎么计算的，我们进入java.lang包查看String类型的实现：

public int hashCode() { // The hash or hashIsZero fields are subject to a benign data race, // making it crucial to ensure that any observable result of the // calculation in this method stays correct under any possible read of // these fields. Necessary restrictions to allow this to be correct // without explicit memory fences or similar concurrency primitives is // that we can ever only write to one of these two fields for a given // String instance, and that the computation is idempotent and derived // from immutable state int h = hash; if (h == 0 && !hashIsZero) { h = isLatin1() ? StringLatin1.hashCode(value) : StringUTF16.hashCode(value); if (h == 0) { hashIsZero = true; } else { hash = h; } } return h;}

Latin和UTF16是两种字符串的编码格式，实现思路其实差不多，我们来看看StringUTF16中hashcode的实现：

public static int hashCode(byte[] value) { int h = 0; int length = value.length >> 1; for (int i = 0; i < length; i++) { h = 31 * h + getChar(value, i); } return h;}

其实就是对字符串逐位按照下面的方式进行计算，和展开成26进制的想法本质上是相似的。

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

为什么选择了31？

 

　　

首先在各种哈希计算中，我们比较倾向使用奇素数进行乘法运算，而不是用偶数。

　　因为用偶数，尤其是2的幂次，进行乘法，相当于直接对原来的数据进行移位运算；这样溢出的时候，部分位的信息就完全丢失了，可能增加哈希冲突的概率。

　　为什么选择了31这个奇怪的数，这是因为计算机在进行移位运算要比普通乘法运算快得多，而31*i可以直接转化为(i << 5)- i，这是一个性能比较好的乘法计算方式，现代的编译器都可以推理并自动完成相关的优化。

具体可以参考《Effective Java》中的相关章节。

 

　　

h>>>16

　　我们现在来看^ h >>> 16又是一个什么样的作用呢？

它的意思是就是将h右移16位并进行异或操作，为什么要这么做呢？

 

　　

因为那个hash值计算出来这么大，那怎么把它连续地映射到一个小一点的连续数组空间呢？

所以需要取模，我们需要将hash值对数组的大小进行一次取模。

 

　　

我们需要对2的幂次大小的数组进行一次取模计算。

　　但对二的幂次取模相当于直接截取数字比较低的若干位，这在数组元素较少的时候，相当于只使用了数字比较低位的信息，而放弃了高位的信息，可能会增加冲突的概率。

　　所以，JDK的代码引入了^ h >>> 16这样的位运算，其实就是把高16位的信息叠加到了低16位，这样我们在取模的时候就可以用到高位的信息了。

　　如何处理哈希冲突呢？

　　JDK中采用的是开链法。

　　哈希表内置数组中的每个槽位，存储的是一个链表，链表节点的值存放的就是需要存储的键值对。

　　如果碰到哈希冲突，也就是两个不同的key映射到了数组中的同一个槽位，我们就将该元素直接放到槽位对应链表的尾部。

总结

手写数据结构统计单词的数量正确的思路就是：

　　根据全文长度大概预估一下会有多少个单词，开一个数倍于它的数组，再设计一个合理的hash函数，把每个单词映射到数组的某个下标，用这个数组计数统计就好啦。

　　当然在实际工程中，我们不会为每个场景都单独写一个这样的散列表实现，也不用自己去处理复杂的扩容场景。

　　到此这篇关于如何在Java中实现一个散列表的文章就介绍到这了,更多相关Java散列表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。