java.util.HashMap/Hashtable

前文已经提到了实现字典的一种形式,二叉树。下面来说另一种形式,哈希。

其实无论是Treap,SBT或者AVL,RBT,我觉得我们都应该大致了解一下。尤其是treap在实现上比较方便,OI的比赛可能在高级点的比赛中会用到。ACM因为可以使用STL(似乎OI也快了),加上可以抄模版,对这种底层的实现看似要求不大,但我觉得只有了解底层实现之后才会更容易学习其他的东西。更何况ACM/OI更应该是素质教育,不应该不需要自己写的就可以写不出来。

那篇RBT的文章没有任何图和代码哪怕是伪代码,我觉得拿它当教材而且真学会的人我应该额外的感谢一下……这篇讲哈希字典的我会以java里的源码为主。感觉java的代码可读性比cpp和c强太多了。尤其是java语言本身的那些包比如uitl什么的很容易通过读源码来掌握原理,而STL的代码在我看来就是个悲剧……哪怕似乎号称可读性最强的CGI实现我还是很难像java这样轻松读懂。当然,java里也有用二叉树形成的字典,叫TreeMap/TreeSet,底层也是红黑树实现,因此迭代器也是有序的。

先大致将一下什么是hash。简单说就是让每个元素都有一个稍微短小一些的代码,这样很多元素就可以通过一个很小范围的数字进行索引,最普通的hash就是计数排序,即开一个从min到max的数组hash[],看见一个x就hash[x]++,然后就知道每个树有几个,排序什么的也是线性时间的。当数组下标要很大进而很费内存的时候,就要通过一个hash函数来获得一个小得多的数字,很显然会有重复,我们称之为“碰撞”。如何高效的处理碰撞,以及提出一个很好很均匀的hash函数就是哈希表的效率之所在。

在java中,与哈希从名字上直接相关的有三个,HashMap,Hashtable,HashSet。第三个显然是集合而前两个才是字典。而HashSet底层就是用一个约等于 value为空的HashMap(准确的说是搞了一个private static final Object PRESENT = new Object();所有的value都等于这个PRESENT)。因此明白前两个怎么回事就知道set怎么回事了,这点跟STL类似。两者均实现了Map<K,V>接口,而Map接口定义了耳熟能详的put,get,size什么的,因此两者使用上区别不大。唯二的区别在于:HashMap支持null为key,有个private V getForNullKey()方法,hashtable没有;还有一个是hashmap是“不同步”的,用官方文档的原话就是“如果多个线程同时访问此映射,而其中至少一个线程从结构上修改了该映射,则它必须保持外部同步”。当然,跟哈希有关的还有一个hashcode,这是在Object类里的一个方法(跟什么toString之流一样),由于需要底层JVM的支持才能形成int并返回,因此看java源码是看不到object类里的方法都是如何实现的,得看jvm的源码才可以。

除了共用map接口之外,还有俩接口也共用,貌似与本文关系不大,而且我还发现两处的代码虽然implement一个接口但一个java.io一个没写,在两者都import java.io.*的情况下,不知道为何会有这个小bug……

两者均继承自各自专属的一个抽象类,一个AbstractMap,一个Dictionary。前者实现了不少东西(不过继承而来的hashmap好多都给重写了),而后者彻底就是抽象的,无任何实现……所以我们可以通过继承前者来实现我们自己的哈希map方案,后者就很难。而且其实那个字典抽象类本身就是一个接口罢了,所以现在的文档会注明,该类已经过时,请使用map接口而非继承此类。看了看发现hashtable是java1.0就有的,而hashmap是1.2的,map接口也是1.2的,因此这应该是个历史遗留问题吧。总之可以认为hashtable.java实现了全部功能而hashmap.java靠很多父类的东西。甚至我通过这个才发现iterator是1.2才有的接口,开始用一个很不成熟方法名还很长的Enumeration接口,这个在hashtalbe也是能看见的,刚看见还奇怪这是神马……

我们知道hash的精髓是搞出来一个最好独一无二的数字然后分列,一旦发现有碰撞就通过一些方法解决。最常见的方法是用链表,即同样一个hash的都拉出来在一个链表里。java也是这样实现的。无论hashtable还是hashmap都有一个内部静态类Entry<K,V>,但hashmap的不是私有的而是无前缀的包访问权限,不知道为啥。两者的成员均为这四个:

int hash;
K key;
V value;
Entry<K,V> next;

构造方法也类似,只是代码风格不一样(要是让HLP或者一些老师看,写hashtable的学生分会高,因为hashmap有很多单字母变量,不符合编码规范)。这里拿符合规范的,map的只是没有protected关键字而已:

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,任何一个新对象都是通过封装成Entry后实现的。这里插播一句,发现有个transient关键字,讲开来太复杂,而且我也没太懂,可以自己google。

然后两者就有很大的不同了。先从古老的hshtable说起。

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;

}

可以看出,hash的获得是靠获得该对象的hashcode然后取与再取模,至于为何是0x7FFFFFFF,应该跟hashcode有关。然后写个程序看了看一般对象的hashcode值,发现int(其实应该是一个Integer对象,因为int变量不是对象,因此java其实并非是100%面向对象的)的hashcode就是那个数,而long的hashcode是正数一样,负数的话就变正再减1.字符串的就约等于不一定了。总之,就是一个很明显的东西得到index,然后放进tab那个数组。而且可以看出来,后进的离根更近。

public synchronized V get(Object key) {

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)) {

return e.value;

}

}

return null;

}

get就差不多了,可以看到只要是计算hash就都得有那行算式,而一会看hashmap就知道人家搞了个专门的函数,需要算就调用一下。因此hashtable的代码其实写的并没有hashmap好。

我们知道,两种hash都有两个可选构造参数,容量和加载因子,默认分别为11和0.75,前者就是初始数组大小,两者相乘再取整是最大容积。一旦整个hash表内的元素个数达到这个制,就要进行rehash操作(put函数里有体现),rehash代码如下:

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(之所以要加1是因为一般hash的容量为尽量质数起码得是奇数,可以减少碰撞的可能,而初始的11似乎也是比较不错的,因为11,23,47都是质数),然后重新入新的数组。顺便提一句,arraylist的初始容量是10,每次不够了就容量*2,vector类似。可以看出0.75的默认因子会经常导致rehash,但这意味着尽量避免碰撞的发生(因为统计学上平均4个坑给3个萝卜,俩萝卜撞上的概率不太大,仨萝卜就更小了)。总之0.75是一个经验上最好的平衡,当然可以手动修改,至于大了或者小了会怎样,如果你理解我说的了也就明白了。

hashtable就是如此的简单,我觉得这个让我们写也不难写出来差不多的。没准比人家写的好,尤其是不会写for (int i = oldCapacity ; i– > 0 😉 这类装13代码……

下面讲hashmap,之前说过获取hash的值hashtable没有将算式代码复用,而hashmap的hash函数就是干这个的:

static int hash(int h) {

// This function ensures that hashCodes that differ only by

// constant multiples at each bit position have a bounded

// number of collisions (approximately 8 at default load factor).

h ^= (h >>> 20) ^ (h >>> 12);

return h ^ (h >>> 7) ^ (h >>> 4);

}

这个hash就是各种异或,我也不知道为啥这样就好。知道的可以给我讲讲。

hashmap的get、put和hashtable基本没区别,只不过因为map支持key==null,因此有一个专门的处理。null的hash永远是0.此外hashmap的各种操作都封装了,比如void addEntry(int hash, K key, V value, int bucketIndex)。不过有个不同是hashmap在rehash的时候用这个:

void resize(int newCapacity) {

Entry[] oldTable = table;

int oldCapacity = oldTable.length;

if (oldCapacity == MAXIMUM_CAPACITY) {

threshold = Integer.MAX_VALUE;

return;

}

Entry[] newTable = new Entry[newCapacity];

transfer(newTable);

table = newTable;

threshold = (int)(newCapacity * loadFactor);

}

里面的transfer就是跟hashtable一样的链表式的插入。因为新的容量是参数,所以需要告诉大家调用此函数的时候是resize(2 * table.length),就是说大小只是单纯的扩大了2倍而非再+1,而且hashmap有个最大的容量MAXIMUM_CAPACITY= 1 << 30,超过这个就不扩容了,而hashtable似乎没这个限制。不过实际上如果真的不限制到最后一定会悲剧的。至于为何不必+1,只能说是因为hash函数太好了因而不用那么麻烦了……

到这里本文就大功告成了。最后总结一下:

hash很简单,难的是hash函数。而我们不可能所有的都用hashcode来获取这个几乎很随机的码,大多数我们要hash的东西得由我们自己写hash,无论参数还是算法。

java提供的东西很多,因为比c++更年轻而且随时更新所以比c++在库上要好一些,但依然有新旧好坏。那这个来说,hashmap应该好于hashtable。不过文档说hashmap是不同步的,但我没看出来两者有何区别,也许只是因为加了那几个关键字造成的?


已发布

分类

来自

标签:

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注