前文已经提到了实现字典的一种形式，二叉树。下面来说另一种形式，哈希。
其实无论是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的不是私有的而是无前缀的包访问权限，不知道为啥。两者的成员均为这四个：
构造方法也类似，只是代码风格不一样（要是让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是不同步的，但我没看出来两者有何区别，也许只是因为加了那几个关键字造成的？
发表回复