Java的Hashtable实现

最近做信息检索的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的实验进行一个简单的测试。