自定义哈希表的性能评测

feiyang10086

自定义哈希表的性能评测

作为一个程序员或一个软件工程师，hash(散列)必然是熟解的。


对于百万级，甚至更多的数据的数据，我们如何实现存储并不太难，可我们要实现快速的增添查找删，显然普通的数组和链表是满足不了的。数组可以满足快速的查找，链表可以实现随意的删除，我们由此不难得到一种数据结构：数组挂链表的结构，称挂链式。


以一般的数据结构实现哈希过程，在实际中会遇到比较大的问题，我们在此选择使用挂链式，作为解决hash冲突的一种解决策略。当有不同的key在hash()后得到想的hashcode的时候，我们选择在哈希表结点上悬挂链表。而当我们的数据虽时间变化的时候，显然，冲突越来越严重，我们需要解决这个问题。在冲突达到一定程度时，我们队哈希表进行扩张，对原哈希表的数据进行rehash（）。


不难想象到，rehash()是一个浪费时间与空间的过程，可这是没有办法的事，因为两全其美的事不存在，我们只能根据实际情况，取舍。


自定义哈希表的结构
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{
   
}




性能对比（见附件）：






代码实现如下：
Java代码  
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;   
            while (node != null) {   
                index = hash((K) node.getItem().getK()) % len;   
                temp[index] = node;   
                node = node.getNext();   
            }   
        }   
        list = temp; // 复制数据   
    }   
  
}  

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
         *            ：
         *

1. @return
   
2.          */
   
3.         public void put(K key, V value) {
   
4.                 if (count >= 1.25 * len) { // 冲突的严重性
   
5.                         rehash();
   
6.                 }
   
7.                 int index = hash(key) % len;
   
8.                 Item<K, V> it = new Item(key, value);
   
9.                 Node node = new Node(it);
   
10.                 if (list[index] != null) { // 判断是否为空结点
    
11.                         // 添加到链表头
    
12.                         Node temp = list[index];
    
13.                         node.setNext(temp);
    
14.                 }
    
15.                 list[index] = node;
    
16.                 count++;
    
17.         }
    
18. 
    
19.         public V get(K k) {
    
20.                 int index = hash(k) % len;
    
21.                 Node temp = list[index];
    
22.                 while (temp != null) { // 判断此数组索引是否为空
    
23.                         if (temp.getItem().getK().equals(k))
    
24.                                 return (V) temp.getItem().getV();
    
25.                         temp = temp.getNext();
    
26.                 }
    
27.                 return null;
    
28.         }
    
29. 
    
30.         /**
    
31.          * 根据键移除hash表中的数据
    
32.          *
    
33.          * @param k
    
34.          * @return 若存在则返回true
    
35.          */
    
36.         public boolean remove(K k) {
    
37.                 if (count == 0) {
    
38.                         throw new RuntimeException("哈希表中无元素，删除操作拒绝！");
    
39.                 }
    
40.                 int index = hash(k) % len;
    
41.                 Node temp = list[index];
    
42.                 while (temp != null) { // 判断此数组索引是否为空
    
43.                         if (temp.getItem().getK().equals(k)) {
    
44.                                 list[index] = temp.getNext();
    
45.                                 count--;
    
46.                                 return true;
    
47.                         }
    
48.                         temp = temp.getNext();
    
49.                 }
    
50.                 return false;
    
51.         }
    
52. 
    
53.         /**

复制代码

* 得到哈希表中元素的个数
         *
         * @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转换为二进制）
        }

        /**
         * 再散列方法

1. */
   
2.         private void rehash() {
   
3.                 len = len * 15; // 表长扩大的倍数
   
4.                 Node[] temp = new Node[len]; // 存放rehash后数据的数组
   
5.                 Node node;
   
6.                 int index;
   
7.                 for (int i = 0; i < list.length; i++) {
   
8.                         node = list[i];
   
9.                         while (node != null) {
   
10.                                 index = hash((K) node.getItem().getK()) % len;
    
11.                                 temp[index] = node;
    
12.                                 node = node.getNext();
    
13.                         }
    
14.                 }
    
15.                 list = temp; // 复制数据
    
16.         }
    
17. 
    
18. }
    
19. 
    
20. 
    
21. 
    
22. Java代码  
    
23. package hash实现;   
    
24. /**  
    
25. * 链表结点类,存放键值对  
    
26. * @author lenovo  
    
27. *  
    
28. */  
    
29. public class Node {   
    
30.       
    
31.     private Node next;   
    
32.     private Item item;   
    
33.       
    
34.     public Node(Item item){   
    
35.         this.item=item;   
    
36.         next=null;   
    
37.     }   
    
38.   
    
39.     public Item getItem() {   
    
40.         return item;   
    
41.     }   
    
42.   
    
43.     public void setItem(Item item) {   
    
44.         this.item = item;   
    
45.     }   
    
46.   
    
47.     public Node getNext() {   
    
48.         return next;   
    
49.     }   
    
50.   
    
51.     public void setNext(Node next) {   
    
52.         this.next = next;   
    
53.     }   
    
54.       
    
55. }  
    
56. 
    
57. package hash实现;
    
58. /**
    
59. * 链表结点类,存放键值对
    
60. * @author lenovo
    
61. *
    
62. */
    
63. public class Node {
    
64.        
    
65.         private Node next;
    
66.         private Item item;
    
67.        
    
68.         public Node(Item item){
    
69.                 this.item=item;
    
70.                 next=null;
    
71.         }
    
72. 
    
73.         public Item getItem() {
    
74.                 return item;
    
75.         }
    
76. 
    
77.         public void setItem(Item item) {
    
78.                 this.item = item;
    
79.         }
    
80. 
    
81.         public Node getNext() {
    
82.                 return next;
    
83.         }
    
84. 
    
85.         public void setNext(Node next) {
    
86.                 this.next = next;
    
87.         }
    
88.        
    
89. }

复制代码

Java代码

1. package hash实现;   
   
2. /**  
   
3. * 键值对  
   
4. * @author lenovo  
   
5. *  
   
6. */  
   
7. public class Item<K,V> {   
   
8.   
   
9.     private K k;   
   
10.     private V v;   
    
11.       
    
12.     public Item(K k,V v){   
    
13.         this.k=k;   
    
14.         this.v=v;   
    
15.     }   
    
16.       
    
17.     public K getK() {   
    
18.         return k;   
    
19.     }   
    
20.     public void setK(K k) {   
    
21.         this.k = k;   
    
22.     }   
    
23.     public V getV() {   
    
24.         return v;   
    
25.     }   
    
26.     public void setV(V v) {   
    
27.         this.v = v;   
    
28.     }   
    
29.       
    
30.       
    
31. }  

复制代码

冰释一片天

谢谢分享