一、Hashtable的优势——高效的查找
时间复杂度：
这无疑是Hashtable最大的优势所在，对于之前提到的数据结构：ArrayList采用顺序查找，时间复杂度为O(n)，而SortedList采用二分查找，时间复杂度为O(logN)，而Hashtable则是O(1)。
原理：
当Hashtable添加数据时，(例如:hash.Add(key)) 首先调用当前键值key的GetHashCode()方法，得到哈希值（该值为Int32），取该哈希值的绝对值跟内部数组（上面代码的buckets）的总容量进行余运算(就是'%'操作)，得到一个小于总容量的值，把该值当做数组序号，存在对应的位置。
Hashtable之所以查找高效，是因为其存储的元素都是通过键值对的形式进行存储的，需要某个元素的值时，可通过映射Key值，找到数组中对应的索引位置，然后取出元素，整个过程无需循环。
代价：
哈希表高效的查找是有代价的，那就是内存，不过，介于现在硬件的发展速度，这种用空间换时间的做法显然没有任何压力。
二、Hashtable的不足
1、哈希表不能有重复键值
这意味着我们在进行哈希表构造时，需要在添加元素时进行判断，若其Key值不存在，则不用重复添加，否则报错。
2、哈希表会占用更多内存
之前提到哈希表高效的查找是以内存为代价的，而原理又是怎样的呢？
首先，我们实例化ArrayList或List
哈希表也有一个类似的情况，new Hashtable()如果不指定长度，则会将内置bucket数组的长度默认指定为11。如果给定一个值如new Hashtable(20)，也并不会将bucket数组长度设置为20，而是循环内部一个素数数组,设置为刚好大于20的素数（此处是23，由此可知，哈希表内部存取数组长度总是一个素数）。
此外，哈希表在未存满的情况下就要扩充： Hashtable有一个加载因子为0.72f。实际能存储的数据量等于内部长度* 0.72f。也就是说在Hashtable中，假如初始化了100个位置，只有72个可用，其他28个不能用，但仍然要占着地方。由于哈希算法本身的特点，哈希表内部存取数组长度总是一个素数，所以当需要扩充时，新的数组长度是刚好大于原数组二倍长度的素数，也就是说略大于二倍。
三、Hashtable——Q&A
其实，在刚接触Hashtable的时候，就看到一句话，也是上文提到的——哈希表内部存取数组长度总是一个素数，比较不解，如果你和我当时一样有着相同的疑问，那么下面的话希望能够解答。
哈希表大小为素数在理论上是有依据的，针对不同的哈希算法有不同的证明。例如，对于平方探测法，有如下定理：如果使用平方探测，且表大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。
hash函数用质数来做模运算(%)，分析发现,如果不是用质数来做模运算的话，很多生活中的数据分布会集中在某些点上，所以需要采用质数做模的除数。
因为用质数做了模的除数，自然存储空间的大小也用质数了，因为模完之后,数据是在[0-所选质数]之间。
四、HashSet
之前提到的一个Hashtable不允许添加重复值，所以我们构造词典的时候代码会是这样：
可以看到Hashtable是使用键-值方式进行存储的，但有些时候，我们只需要其中一个值，比如上图所示的情况，我只需要词典中的词，对于value我们不需要进行设置，所以这样就造成了内存浪费。
不过其实有一种数据结构可以改变这样的情况，那就是HashSet
HashSet
HashSet
但HashSet
所以上面的代码就可以写作：
看着舒心了些吧。。。
五、HashSet
好了，介绍的差不多，来看下最终的效果吧，以之前的那个完整的测试文本进行测试：
启动毫无压力，运行结果也灰常满意。
到此为此，介绍了个人在分词软件上对于算法、数据结构等方面的研究、测试与改进，最后的这个HashSet
不过之前的所有测试使用的词典都是以文本形式存储的，下篇将介绍使用数据库进行词典存储后，分词软件的性能表现及相关改进。
本文部分内容参考了园子里面的文章，在此附上友情链接：http://www.cnblogs.com/hkncd/archive/2011/05/06/2035684.html
作者：Rocky翔 出处：http://www.cnblogs.com/RockyMyx/ 本文版权归作者和博客园共有，欢迎转载，但请在文章明显位置给出原文连接，否则保留追究法律责任的权利。
最新评论