程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 算法6-2:解決哈系沖突之獨立鏈表

算法6-2:解決哈系沖突之獨立鏈表

編輯:C++入門知識

獨立鏈表是解決哈希沖突的一種辦法。它的基本思想就是將哈希值相互沖突的幾個對象放到一個鏈表中。


代碼

public class HashST {
    private static class Node {
        Object key; // 由於無法創建泛型數組,只能將對象設置為Object類
        Object value;
        Node next;
 
        public Node(Object key, Object value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
 
    private Node[] map;
    private static final int M = 97;
 
    public HashST() {
        map = new Node[M];
    }
 
    public Value get(Key key) {
        int hash = hash(key);
        Node node = map[hash];
        while(node != null) {
            if(key.equals(node.key)) {
                return (Value) node.value;
            }
            node = node.next;
        }
 
        // 沒有找到
        return null;
    }
 
    public void put(Key key, Value value) {
        int hash = hash(key);
        Node node = map[hash];
        while(node != null) {
            if(key.equals(node.key)) {
                node.value = value;
                return;
            }
        }
        map[hash] = new Node(key, value, node);
    }
 
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
}


性能

性能和M有關,M就是鏈表的數量。如果M過大,那麼內存中就會有很多空的鏈表,如果M太小,那麼每條鏈表就會很長,造成性能變差。所以,M一般取N/5,N就是關鍵字的數量。


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved