Java中Hash类容器使用指南

经常看到Hash这个东西，比如emule，每次下载完一个文件，它都要对这个文件hash半天，让我们来看看在java里面使用hash类容器的方法。
Hash类容器乃是一类map，具有一个key－value对应关系，最简单的例子，数组就是这样，一个数组下标对应一个值，你可以使用下标……飞快的……定位，而不用象list那样还要用个iterator去一个一个查找，这在容器元素很多的时候是很有用的。（学过桶排序么，那里的bucket在这里也被用到了，bucket就是hash类容器的一个特征哦，后面会提到桶的作用）

每个被放入Hash类容器里面的Object（容器里面是不能放int之类的简单数据结构的，必须放入Object）都会通过自己的hashCode()函数产生一个hashCode值，这个东西可以是你自己定义的，通过重载hashCode()函数（建议是，equals()，compareTo()函数也一起重载掉），用来提供一个特定的hash值，这样any object can be used as a key and it will hash by default。

注意，你提供的每个key必须是独一无二的（天下无双^_^），然而hash出来的hashCode不一定是不重复的。比如我们用了一个散列函数是n % m，如果m比较小，那么对于不同的n来说就有可能得到同样的hashcode，至于如何找到一个好的散列函数……问数学系的同学，或者参考《Effective Java》 Java 的首席架构师 Joshua Bloch写的。如果两个hashcode重复了，hash类容器会把有相同hashcode的Object挂在同一个hashcode节点下，用list保存起来，这样如果下次我们查找到这个hashcode节点，就再在这个list里面去查找，这就叫做碰撞(collision)，所以如果散列函数设计得不好，碰撞(collision)就会很多，但是吖，鱼和熊掌不可得兼，如果要让碰撞少，就会导致空间浪费严重。还是以数组为例子，你开一个很大的数组才能保证下标取到很大的时候不会取不到，可是中间就有很多用不到的元素了。（这就是桶的作用，桶越多，桶里面就越有可能放到少的元素，参见数学书中关于抽屉原理的说明^_^）

当然你不重载也可以，java中的元类型，就是那个继承体系的祖先Object里面已经提供了hashCode()，至于功能如何……参看下面的文字
The method as it is implemented in Object in Java, however, isn’t a panacea. Since it usually uses the memory address where an object is stored to produce the hash value, distinct objects always produce different hash values. In one sense this is a plus, because the more likely it is that a unique hash value will be produced for each key, the more efficient the operation of the hash map is going to be. The downside is that different object instances that have identical data will produce different hash values, so you can’t compare them.

This becomes a nuisance if you use the default hashCode() method in objects that you’re using as keys. In this case, an object stored in a hash map can never be retrieved using a different key object instance, even though that key object may be identical in all other respects. Yet this is precisely what you’ll want to do in many cases.
意思说，Object里面那个hashCode()不是万能的，它通常是使用内存地址来产生hash值的，故不同的objects产生不同的hash值往往是正确的……可是……这虽然是一个好处，因为碰撞比较少……但是（语文没学好）……负面效应是你就会找不到这个东西了……怎么回事呢，听我解释
如果一个object被放到hash map里面，那么你要找到它，必须用它自己去找，而不能用一个和它一模一样的对象实例去查找，比如，我放进去一个Integer class，然后我要找这给Integer的话，习惯上肯定是用Integer的intValue去找，如果两个intValue相等就找到了，而不可能用一个引用去找，那样的话还找它干嘛，直接用它的引用就可以拉……问题就是，如果使用了原来的那个hashCode函数，就只能通过引用（这是我自己理解的，还不知道对不对……先说说大话）才能在hash map里面找到它。这就很麻烦了

学会一个好词panacea，哈哈哈。发现什么Oxford Cambridge Collins电子词典比起来，Macmillan的速度很快，词也很丰富。不过很奇怪，查不到Spain，而可以查到Spanish……我又说废话了

考虑一个地址薄之类的对象，可以使用诸如名字，地址之类不大可能重复的数据成员来做key，这样查找的时候就可以用名字，地址来查找。

依照上面的讨论，下面来解释一下为什么要在重载hashCode()的时候把equals()函数也一起重载掉。如果是使用对象的数据成员来做key，那么在往容器里面插入的时候要比较是否有重复的key（前面说过，天下无双，嘿嘿），e