自定义哈希表的性能评测
作为一个程序员或一个软件工程师，hash(散列)必然是熟解的。
对于百万级，甚至更多的数据的数据，我们如何实现存储并不太难，可我们要实现快速的增添查找删，显然普通的数组和链表是满足不了的。数组可以满足快速的查找，链表可以实现随意的删除，我们由此不难得到一种数据结构：数组挂链表的结构，称挂链式。
以一般的数据结构实现哈希过程，在实际中会遇到比较大的问题，我们在此选择使用挂链式，作为解决hash冲突的一种解决策略。当有不同的key在hash()后得到想的hashcode的时候，我们选择在哈希表结点上悬挂链表。而当我们的数据虽时间变化的时候，显然，冲突越来越严重，我们需要解决这个问题。在冲突达到一定程度时，我们队哈希表进行扩张，对原哈希表的数据进行rehash（）。
不难想象到，rehash()是一个浪费时间与空间的过程，可这是没有办法的事，因为两全其美的事不存在，我们只能根据实际情况，取舍。
自定义哈希表的结构
①hash（）：哈希表实现快速增删查的根本，通过hash（）对每一个key 得到唯一的一个索引，而这个索引就如身份证号，查找删除数据时只需知道与此数据相匹配的索引；
②解决冲突的方法：冲突指的是当不同的数据的key通过hash（）得到相同的索引位置而提供的解决方法，此处此方法为挂链式；
③rehash（）：当哈希表中的数据达到一定的值时，成为阀值，因为此刻由于数据的增多，索引的速度必然受到影响，而解决的方法就是对数组拓展，重新的hash（）.
class HuHash{
? private Node<Item> [] list=new Node<Item> [len];
? public boolean put(K k,V v){? ? ?if(冲突严重){? ? ? ? ?rehash()? ? ?}? ? ?int index=hash(k)%len;? ? ?Node<Item> node=new Node<Item>(k,v); ?? ? ?if(list[index]==null){? ? ? ??? ? ?}? ? ?? }
? public boolean get(K k){??? }?? public boolean hash(K k){??? }??? public boolean rehash(){??? }
}
class Node<Item>{? private Node parent;? private Node next;}
class Item{? ?}
性能对比（见附件）：
代码实现如下：
package hash实现;/** * 哈希的实现类 * * @author lenovo * */public class MyHash<K, V> {private int len;private Node[] list;private int count; // 计数器public MyHash(int len) {this.len = len;list = new Node[len];count = 0;}/** * 添加元素的方法 * * @param key * ：键 * @param value * ： * @return */public void put(K key, V value) {if (count >= 1.25 * len) { // 冲突的严重性rehash();}int index = hash(key) % len;Item<K, V> it = new Item(key, value);Node node = new Node(it);if (list[index] != null) { // 判断是否为空结点// 添加到链表头Node temp = list[index];node.setNext(temp);}list[index] = node;count++;}public V get(K k) {int index = hash(k) % len;Node temp = list[index];while (temp != null) { // 判断此数组索引是否为空if (temp.getItem().getK().equals(k))return (V) temp.getItem().getV();temp = temp.getNext();}return null;}/** * 根据键移除hash表中的数据 * * @param k * @return 若存在则返回true */public boolean remove(K k) {if (count == 0) {throw new RuntimeException("哈希表中无元素，删除操作拒绝！");}int index = hash(k) % len;Node temp = list[index];while (temp != null) { // 判断此数组索引是否为空if (temp.getItem().getK().equals(k)) {list[index] = temp.getNext();count--;return true;}temp = temp.getNext();}return false;}/** * 得到哈希表中元素的个数 * * @return */public int size() {return count;}/** * SDBM散列方法 * * @param k * ：键 * @return 哈希值 */private int hash(K k) {String str = (String) k;int hash = 0;char[] chars = str.trim().toCharArray();int num = 0;while (num < chars.length) {hash = (int) chars[num] + (hash << 6) + (hash << 16) - hash; // 进行移位运算num++;}return (hash & 0x7FFFFFFF); // 按位与（hash和0x7ffffff转换为二进制）}/** * 再散列方法 */private void rehash() {len = len * 15; // 表长扩大的倍数Node[] temp = new Node[len]; // 存放rehash后数据的数组Node node;int index;for (int i = 0; i < list.length; i++) {node = list[i];while (node != null) {index = hash((K) node.getItem().getK()) % len;temp[index] = node;node = node.getNext();}}list = temp; // 复制数据}}?package hash实现;/** * 链表结点类,存放键值对 * @author lenovo * */public class Node {private Node next;private Item item;public Node(Item item){this.item=item;next=null;} public Item getItem() {return item;}public void setItem(Item item) {this.item = item;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}}?package hash实现;/** * 键值对 * @author lenovo * */public class Item<K,V> {private K k;private V v;public Item(K k,V v){this.k=k;this.v=v;}public K getK() {return k;}public void setK(K k) {this.k = k;}public V getV() {return v;}public void setV(V v) {this.v = v;}}?其他参考的hash函数：/** * 一位接一位的hash函数 * * @param k * @return */private int oneByOneHash(K k) {String str = (String) k;int hash = 0;for (int i = 0; i < str.length(); ++i) {hash += str.charAt(i);hash += (hash << 10);hash ^= (hash >> 6);}hash += (hash << 3);hash ^= (hash >> 11);hash += (hash << 15);return hash;}?/** * FNVHash 函数 * * @param k * @return */private int FNVHash(K k) {String str = (String) k;final int p = 16777619;int hash = (int) 2166136261L;for (int i = 0; i < str.length(); i++)hash = (hash ^ str.charAt(i)) * p;hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;return hash;}?