獨立鏈表是解決哈希沖突的一種辦法。它的基本思想就是將哈希值相互沖突的幾個對象放到一個鏈表中。
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就是關鍵字的數量。