关于hash的一点理解

????? 一直以来对哈希表的印象仅在于的书本上，即老师提到的所谓考试重点。那时初学数据结构，被C语言中那些令人头痛的指针搞得晕头转向，初见哈希表，脑中蹦出的一句话是“哇塞！这题目超简单！”当时还是把这些当做考试题目来看待的，试卷上的习题，无异于“取模”、“放入格子里”、“解决冲突”这几个问题。以至于到后来，总觉着哈希表就那么一回事。它和二叉树、链表一样，不过只是书本上的理论罢了。直到后面自己慢慢试着用代码来实现这些结构时，才重新将他们认识了一遍。
?? ?? 早之前有抄过C的哈希表的代码，只觉着自己几乎完全不能把填格子和这一串英文字联系起来。后来看到Java中的HashTable和HashMap时，一直都想不明白。“这里有两个值，咋整啊？”
????? 没办法只能硬着头皮看源码了，同时去网上搜索了一些资料，才慢慢有了一点理解。对于KEY和VALUE，文档中的解释是“将键映射到相应的值”。映射这个词，数学上就是x->f(x)(还是f(x)->x？悲剧了……)而在这里，则是把value当做key的一个附属，即它仅仅是一个属性，而hash方法的重点则在于KEY。而哈希结构就是实现了“键——值”之间的快速存取，通过对KEY的哈希运算快速得到对应的VALUE，而省去了遍历的时间。源码中，通过连续的两步先对键值自带的hashcode做哈希运算，之后通过indexFor的方法得到索引。这里是hashmap的源代码：

int hash = hash(k); int i = indexFor(hash, table.length); 　　static int hash(int h) {        h ^= (h >>> 20) ^ (h >>> 12);        return h ^ (h >>> 7) ^ (h >>> 4);    } static int indexFor(int h, int length) {        return h & (length-1);    }

?

?

??????前者是源码中定义的哈希算法，后者则是将其转化成相应索引值。简单的两步便得到了对应的索引值，但又运用得恰到好处。接下来要说的是Entry这个内部类。要实现哈希结构，Entry占了很重要的地位。源码中的Entry继承了Map.Entry，它包含key,value,next,hash四个属性，分别代表了键、值、指向下个Entry的指针、和hash值（看了好几遍，源码中这个里面的hash值没有在这个内部类中用到，不知道它的用处在哪里……求解）。里面有几个方法，这里要说到的是setValue方法 。

?

public final V setValue(V newValue) {    V oldValue = value;            value = newValue;            return oldValue;        }

?

???? 当新的值被放入时，则会覆盖旧值，并把旧值返回。这样正符合哈希表“键——值”一一对应的特性。
由于时间关系，在这里只分析了put和get方法。看了源代码，发现put方法原来是有返回值的，返回的对象是当key存在时的旧value值。顺带看了下面的putForNullKey方法，这是当key为null时，得到hashcode的方法。这也是hashmap和hashtable的一大区别，即hashmap中允许键或值为空。
????? 由于不同的key值hashcode有可能相同，这就导致算出来的索引值也是相同的，于是把拥有相同索引的Entry链接在前一个之后，也即是next属性所指向的。当然如果这个链表过长的话，就使搜索的时间变得更长，也就失去了哈希表的意义了。于是当超过了一定对象时，就会重新构造存取表。get的方法和put是一个道理，这里就不赘述了。于是，根据这些原理，自己写了一个简单的哈希表，仅仅实现了get和put方法，rehash也没有写，代码如下：

/** * 哈希表  * @author Administrator * @param <K> * @param <V> */public class MyHashTable<K, V> {private int length = 10000;MyEntry[] table = new MyEntry[length];/** * 添加元素 */public void put(K key, V value) {// 通过哈希算法的到hash值及索引值int code = hash(key.hashCode());int i = indexfor(code);// 当该索引位置有值时if (table[i] != null) {MyEntry<K, V> e1 = table[i];// 比较key值是否相同if (e1.getKey().equals(key)) {// 相同则覆盖valueV oldvalue = (V) e1.setValue(value);table[i] = e1;} else {// 若不同，则链接到最后面MyEntry<K, V> e2 = new MyEntry<K, V>(code, key, value, null);while (e1.getNext() != null) {e1 = e1.getNext();}e1.setNext(e2);table[i] = e1;}} else {MyEntry<K, V> e = new MyEntry<K, V>(code, key, value, null);table[i] = e;}}/** * 取得元素 *  * @param key */public V get(K key) {V values = null;// 得到索引值int code = hash(key.hashCode());int i = indexfor(code);if (table[i] == null) {System.err.println("找不到对应键值！！");return null;} else {MyEntry<K, V> e = table[i];while (true) {if (e.getKey().equals(key)) {values = e.getValue();break;}e = e.getNext();if (e == null) {break;}}return values;}}public int hash(int code) {// System.out.println(">>>>>"+code);code = code % 9737;return code;}public int indexfor(int code) {code = code & (length - 1);return code;}}

?

接下来是Entry类：

package hash20120308;/** *  * @author Administrator *  */public class MyEntry<K, V> {// 四个键值private K key;V value;int hash;MyEntry<K, V> next;// 通过next创建链表解决冲突// 构造方法public MyEntry(int h, K k, V v, MyEntry<K, V> n) {this.hash = h;this.key = k;this.value = v;this.next = n;}public K getKey() {return key;}public V getValue() {return value;}// 用新的value值来覆盖旧值public V setValue(V newvalue) {V oldvalue = this.value;this.value = newvalue;return oldvalue;}public int getHash() {return hash;}public MyEntry<K, V> getNext() {return next;}public void setNext(MyEntry<K, V> next) {this.next = next;System.out.println(">>>>>接了一个");}}

?

最后来测试一下：package hash20120308;

import java.util.Random;public class Test { public static void main(String args[]) {  Random rd = new Random();  long s1 = System.currentTimeMillis();  MyHashTable<Integer, Integer> mm = new MyHashTable<Integer, Integer>();  int c = 0;  // while (c < 100000) {  // int t = rd.nextInt(10000);  // System.out.println("d>>>" + t);  // int r = rd.nextInt(10000);  // mm.put(t, r);  // c++;  // }  mm.put(345, 251);  mm.put(345, 4535);  mm.put(346, 532);  // long s2 = System.currentTimeMillis();  // System.out.println(s2 - s1);  int das = mm.get(345);  int dasw = mm.get(346);  long s3 = System.currentTimeMillis();  System.out.println("345对应的是" + das);  System.out.println("346对应的是" + dasw);  System.out.println(s3 - s1); }}

?

?

结果：
>>>>替换了一个
345对应的是4535
346对应的是532
3

?

这个哈希表还很不完善，但总算对它有一定的了解了。