最近做信息检索的VSM实验,字典生成这块用的是java自带的Hashtable数据结构,觉得效率还不错。后来有同学提到用词典树来保存字符串,可以用公共前缀来节约存储空间,最大限度的减少无谓的比较,查询效率要高于哈希表。(补充@2011.5.5 在数据较少的情况下,hash的查询效率应该是最高的,基本接近O(1),字典树的优势应该是在空间效率上)回头有时间研究下词典树的实现和分析,这里先分析一下Java的hashtable实现。
为了使用Eclipse去查看java本身的一些基础实现,我们需要先将java的源码加到Eclipse的jre路径中:
1.点 “window”-> "Preferences" -> "Java" -> "Installed JRES"
2.此时"Installed JRES"右边是列表窗格,列出了系统中的 JRE 环境,选择你的JRE,然后点边上的 "Edit..."
3.选中rt.jar文件,点右边的按钮“Source Attachment...”, 选择你的JDK目录下的“src.zip”文件即可
这样,在Eclipse中随便写一个Hashtable对象,然后ctrl单击就可以看到java的Hashtable类的实现了。下面这张是其总体的结构:
总得来说就是每个哈希表都保存了一个Entry数组,然后每个Entry其实是存放碰撞的一个链,其中Entry类部分代码实现是:
- /**
- * Hashtable collision list.
- */
- private static class Entry<K,V> implements Map.Entry<K,V> {
- int hash;
- K key;
- V value;
- Entry<K,V> next;
- protected Entry(int hash, K key, V value, Entry<K,V> next) {
- this.hash = hash;
- this.key = key;
- this.value = value;
- this.next = next;
- }
除了hash值和键值对,就是指向下一个Entry的“指针”了。哈希表还有两个主要的属性,一个是initialCapacity表示初始的大小,如果使用默认的构造函数,系统就设为11,注意这里容量不是可以存放字符串的个数,而是哈希的范围,设为11的话,所有的hash值都会映射到这11个位置上。另一个是loadFactor,表示存放元素的个数栈总的hash范围的比例,默认的是设为0.75,这是在空间和时间之间的一个权衡,如果过大,则会有很多的碰撞出现,搜索效率不高,而如果过低,则会占用很大的空间。还有一些其他的属性,比如总的元素个数,阈值等等,这里不再详述。
下面看下几个关键的函数实现,首先自然是put函数:
- public synchronized V put(K key, V value) {
- // Make sure the value is not null
- if (value == null) {
- throw new NullPointerException();
- }
- // Makes sure the key is not already in the hashtable.
- Entry tab[] = table;
- int hash = key.hashCode();
- int index = (hash & 0x7FFFFFFF) % tab.length;
- for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
- if ((e.hash == hash) && e.key.equals(key)) {
- V old = e.value;
- e.value = value;
- return old;
- }
- }
- modCount++;
- if (count >= threshold) {
- // Rehash the table if the threshold is exceeded
- rehash();
- tab = table;
- index = (hash & 0x7FFFFFFF) % tab.length;
- }
- // Creates the new entry.
- Entry<K,V> e = tab[index];
- tab[index] = new Entry<K,V>(hash, key, value, e);
- count++;
- return null;
- }
这里我们可以看到,对key的hash做了一个与操作,保证其是一个正整数,然后对数组的长度求余,得到索引,然后遍历这个索引位置的链表中的每一个元素,如果存在一个元素的key和插入的key相同,就修改其值。否则,就新建一个Entry放在index位置链表的最前面,其中用到了rehash函数,可以在当哈希表中的总个数超过当前容量乘以loadFactor(就是threshold)的时候,进行扩建和重排序:
- protected void rehash() {
- int oldCapacity = table.length;
- Entry[] oldMap = table;
- int newCapacity = oldCapacity * 2 + 1;
- Entry[] newMap = new Entry[newCapacity];
- modCount++;
- threshold = (int)(newCapacity * loadFactor);
- table = newMap;
- for (int i = oldCapacity ; i-- > 0 ;) {
- for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
- Entry<K,V> e = old;
- old = old.next;
- int index = (e.hash & 0x7FFFFFFF) % newCapacity;
- e.next = newMap[index];
- newMap[index] = e;
- }
- }
- }
容量扩大2倍加1,采用这个策略应该是有一定考虑的,我没有细究。在拷贝完之后,进行了一个重新的hash,因为容量已经变了,所以这个步骤是必须的。还有一些其他的函数,类似这里就不介绍了,最后我们来看下java的字符串hash是采用的什么算法:
- public int hashCode() {
- int h = hash;
- if (h == 0) {
- int off = offset;
- char val[] = value;
- int len = count;
- for (int i = 0; i < len; i++) {
- h = 31*h + val[off++];
- }
- hash = h;
- }
- return h;
- }
这个函数在String中,看上面非常简洁,就是对字符串中的每一个字符的ASCII码值进行的一个加和乘运算,乘数是31。这个算法是BKDR哈希算法,来自于Brian Kernighan 和 Dennis Ritchie的The C Programming Language一书,可以说是常用的hash算法中较为简洁的一个了,但是效率确实最好的之一,其中乘数的形式是31 131 1313 13131 131313...。关于常见的字符串hash算法,我会在以后的博客给予介绍,并用这次VSM的实验进行一个简单的测试。
相关推荐
实现了链表法(Chaining)和开放地址寻址(Open Addressing)中的Hash表实现,开放地址寻址采用双重散列解决冲突
介绍了java hashtable实现代码,有需要的朋友可以参考一下
·基于JDK 11,将Java8、Java9、Java10、Java11新特性一网打尽 ·课程中,Eclipse和IDEA这两种企业一线开发环境都使用到了 3.技术讲解更深入、更全面: ·课程共30天,715个知识视频小节,涉及主流Java使用的...
Hashtable是Java中的一种散列表实现,它可以存储键值对,并根据键的哈希值来快速查找和访问值。
HashMap、HashTable和HashSet是Java中常用的数据结构,它们的底层实现原理以及区别如下:HashMap底层实现原理: HashMap基于哈希表(HashTable)实现,它通过散列算法将键值对映射到数组中。在HashMap中,每个键值对...
java软件技术文档
import java.util.Hashtable; import java.util.Map; import java.util.Set; public class ChatRoomServer { private ServerSocket ss; private Map,Socket> onlineUsers; public ChatRoomServer(){ try {...
实现hashtable按值排序和按key排序,可直接运行
HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。 1. HashMap几乎可以等价于Hashtable,除了HashMap是非...
HashSet实现了Set接口,它不允许集合中有重复的值,当我们提到HashSet时,第一件事情就是在将对象存储在HashSet之前,要先确保对象重写equals()和hashCode()方法,这样才能比较对象的值是否相等,以确保set中没有...
Java面试题11.HashMap和HashTable的区别 Java面试题12.实现一个拷贝文件的工具类要使用字节流还是字符串 Java面试题13.线程的的实现方式?怎么启动线程?怎么区分线程? Java面试题14.线程并发库和线程池的作用 Java...
HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
线性结构与顺序表、单向链表、循环链表、栈的基本概念、链式堆栈、中缀表达式、队列、链式队列、串、MyString、Brute-Force算法、MySet类实现、矩阵类、递归算法、哈夫曼树、希尔排序、HashTable算法等内容
Java集合详解4:HashMap和HashTable Java集合详解5:深入理解LinkedHashMap和LRU缓存 Java集合详解6:TreeMap和红黑树 Java集合详解7:HashSet,TreeSet与LinkedHashSet Java集合详解8:Java集合类细节精讲 JavaWeb
2.1.6 JMX的当前实现及应用 2.1.7 小结 2.2 应用 JMX 最佳实践 2.3 Java/J2EE中文问题终极解决之道 2.4 Java Web应用中的任务调度 2.5 用连接池提高Servlet访问数据库的效率 2.6 应用服务器的集群策略及Java EE 5.0 ...
Hashtable继承自Dictionary类,而HashMap是Java1.2引进的Map interface的一个实现。 最大的不同是,Hashtable的方法是Synchronize的,而HashMap不是,在多个线程访问Hashtable时,不需要自己为它的方法实现同步,而...
│ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分线程.mp4 │ Java面试题14.线程并发库和线程池...
但上述功能,不符我们的实际要求,另外查询遍历也不方便,我们需要在Array的基础上进行扩展, 下面我们可以用js中的数组来实现类似的hashtable的功能, 代码如下: function Hashtable(){ this.clear = hashtable_...
Hashtable继承自Dictionary类,而HashMap是Java1.2引进的 Map interface的一个实现。 最大的不同是,Hashtable的方法是Synchronize的,而HashMap 不是,在多个线程访问Hashtable时,不需要自己为它的方法实 现同步,...