红黑树实现过于复杂，当不需要符号表中的键值有序时可以使用哈希表来实现符号表 哈希表同红黑树一样高效，但是实现简单 哈希表使用数组存储键值对，通过一个hash函数把key转成数组的索引,然后把value存储在数组中该索引的位置 如果不同的key通过hash函数转换的索引i相同,则把i位置的不同key-value值通过链表链接起来 查找的时候先通过hash找到索引位置，再遍历链表找到与key相同的key-value值 public class SeparateChainingHashST<Key, Value> { private static final int INIT_CAPACITY = 4;
private int n; // number of key-value pairs private int m; // hash table size private SequentialSearchST<Key, Value>[] st; // array of linked-list symbol tables /** * Initializes an empty symbol table. */ public SeparateChainingHashST() { this(INIT_CAPACITY); }
/** * Initializes an empty symbol table with {@code m} chains. * @param m the initial number of chains */ public SeparateChainingHashST(int m) { this.m = m; st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[m]; for(int i = 0; i < m; i++) { st[i] = new SequentialSearchST<Key, Value>(); } } // resize the hash table to have the given number of chains, // rehashing all of the keys private void resize(int chains) { SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains); for (int i = 0; i < m; i++) { for (Key key : st[i].keys()) { temp.put(key, st[i].get(key)); } } this.m = temp.m; this.n = temp.n; this.st = temp.st; } // hash value between 0 and m-1 //hash函数一般实现是把key转换成32为无符号整数，然后与数组长度m取余就可以得到一个0到m-1的索引值 //hash函数的设计很重要，不均匀的hash值会导致同一索引位置的链表很长，查询就比较慢了 //java为基本的Integer,Long,Double,String都实现了hash函数hashcode, 查找时先根据key的hashCode找到数组索引， //然后遍历链表通过equal()判断key是否相同 //我们在设计自定义类型的hashCode函数时可以参考java库里面的实现，比如把每个成员的hashCode相加 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % m; } /** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; }
/** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; }
/** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; } /** * Returns the value associated with the specified key in this symbol table. * * @param key the key * @return the value associated with {@code key} in the symbol table; * {@code null} if no such value * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); return st[hash(key)].get(key); } /** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null"); if (val == null) { delete(key); return; } // double table size if average length of list >= 10 if (n >= 10*m) resize(2*m); int i = hash(key); if (!st[i].contains(key)) n++; st[i].put(key, val); } /** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { if (key == null) throw new IllegalArgumentException("argument to delete() is null");
int i = hash(key); if (st[i].contains(key)) n--; st[i].delete(key);
// halve table size if average length of list <= 2 if (m > INIT_CAPACITY && n <= 2*m) resize(m/2); }
// return keys in symbol table as an Iterable public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < m; i++) { for (Key key : st[i].keys()) queue.enqueue(key); } return queue; }
}
//链表实现的符号表
package chapter3_4;
import StdLib.StdIn; import StdLib.StdOut; import chapter1_3.Queue;
/************************************************************************* * Compilation: javac SequentialSearchST.java * Execution: java SequentialSearchST * Dependencies: StdIn.java StdOut.java * Data files: http://algs4.cs.princeton.edu/31elementary/tinyST.txt * * Symbol table implementation with sequential search in an * unordered linked list of key-value pairs. * * % more tinyST.txt * S E A R C H E X A M P L E * * % java SequentialSearchST < tiny.txt * L 11 * P 10 * M 9 * X 7 * H 5 * C 4 * R 3 * A 8 * E 12 * S 0 * *************************************************************************/
public class SequentialSearchST<Key, Value> { private int N; // number of key-value pairs private Node first; // the linked list of key-value pairs
// a helper linked list data type private class Node { private Key key; private Value val; private Node next;
public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } }
// return number of key-value pairs public int size() { return N; }
// is the symbol table empty? public boolean isEmpty() { return size() == 0; }
// does this symbol table contain the given key? public boolean contains(Key key) { return get(key) != null; }
// return the value associated with the key, or null if the key is not present public Value get(Key key) { for (Node x = first; x != null; x = x.next) { if (key.equals(x.key)) return x.val; } return null; }
// add a key-value pair, replacing old key-value pair if key is already present public void put(Key key, Value val) { if (val == null) { delete(key); return; } for (Node x = first; x != null; x = x.next) if (key.equals(x.key)) { x.val = val; return; } first = new Node(key, val, first); N++; } public void delete(Key key) { if (isEmpty()) return; if (key.equals(first.key)) { first = first.next; N--; return; } for (Node x = first.next, p = first; x != null; p = x,x = x.next) { if (key.equals(x.key)) { p.next = x.next; N--; return; } } }
// remove key-value pair with given key (if it's in the table) // public void delete(Key key) { // first = delete(first, key); // }
// delete key in linked list beginning at Node x // warning: function call stack too large if table is large private Node delete(Node x, Key key) { if (x == null) return null; if (key.equals(x.key)) { N--; return x.next; } x.next = delete(x.next, key); return x; }
// return all keys as an Iterable public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (Node x = first; x != null; x = x.next) queue.enqueue(x.key); return queue; }
/*********************************************************************** * Test client **********************************************************************/ public static void main(String[] args) { SequentialSearchST<String, Integer> st = new SequentialSearchST<String, Integer>(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); } for (String s : st.keys()) StdOut.println(s + " " + st.get(s)); } }
package chapter3_4;
import StdLib.StdIn; import StdLib.StdOut; import chapter1_3.Queue;
//上面实现的哈希表当Key hash的索引位置相同时，会把相同索引位置的k-v通过链表连接起来，这种方式叫做拉链法 //还有一种哈希表的实现方式,当Key hash的索引位置相同时不通过链表连接，而是从此索引的位置开始从数组中找一个空位插入进去 //这种方式叫做线性探测法，比较好理解，代码如下 public class LinearProbingHashST<Key, Value> { private static final int INIT_CAPACITY = 4;
private int n; // number of key-value pairs in the symbol table private int m; // size of linear probing table private Key[] keys; // the keys private Value[] vals; // the values
/** * Initializes an empty symbol table. */ public LinearProbingHashST() { this(INIT_CAPACITY); }
/** * Initializes an empty symbol table with the specified initial capacity. * * @param capacity the initial capacity */ public LinearProbingHashST(int capacity) { m = capacity; n = 0; keys = (Key[]) new Object[m]; vals = (Value[]) new Object[m]; }
/** * Returns the number of key-value pairs in this symbol table. * * @return the number of key-value pairs in this symbol table */ public int size() { return n; }
/** * Returns true if this symbol table is empty. * * @return {@code true} if this symbol table is empty; * {@code false} otherwise */ public boolean isEmpty() { return size() == 0; }
/** * Returns true if this symbol table contains the specified key. * * @param key the key * @return {@code true} if this symbol table contains {@code key}; * {@code false} otherwise * @throws IllegalArgumentException if {@code key} is {@code null} */ public boolean contains(Key key) { if (key == null) throw new IllegalArgumentException("argument to contains() is null"); return get(key) != null; }
// hash function for keys - returns value between 0 and M-1 private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % m; }
// resizes the hash table to the given capacity by re-hashing all of the keys private void resize(int capacity) { LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<Key, Value>(capacity); for (int i = 0; i < m; i++) { if (keys[i] != null) { temp.put(keys[i], vals[i]); } } keys = temp.keys; vals = temp.vals; m = temp.m; }
/** * Inserts the specified key-value pair into the symbol table, overwriting the old * value with the new value if the symbol table already contains the specified key. * Deletes the specified key (and its associated value) from this symbol table * if the specified value is {@code null}. * * @param key the key * @param val the value * @throws IllegalArgumentException if {@code key} is {@code null} */ public void put(Key key, Value val) { if (key == null) throw new IllegalArgumentException("first argument to put() is null");
if (val == null) { delete(key); return; }
// double table size if 50% full if (n >= m/2) resize(2*m);
int i; for (i = hash(key); keys[i] != null; i = (i + 1) % m) { if (keys[i].equals(key)) { vals[i] = val; return; } } keys[i] = key; vals[i] = val; n++; }
/** * Returns the value associated with the specified key. * @param key the key * @return the value associated with {@code key}; * {@code null} if no such value * @throws IllegalArgumentException if {@code key} is {@code null} */ public Value get(Key key) { if (key == null) throw new IllegalArgumentException("argument to get() is null"); for (int i = hash(key); keys[i] != null; i = (i + 1) % m) if (keys[i].equals(key)) return vals[i]; return null; }
/** * Removes the specified key and its associated value from this symbol table * (if the key is in this symbol table). * * @param key the key * @throws IllegalArgumentException if {@code key} is {@code null} */ public void delete(Key key) { if (key == null) throw new IllegalArgumentException("argument to delete() is null"); if (!contains(key)) return;
// find position i of key int i = hash(key); while (!key.equals(keys[i])) { i = (i + 1) % m; }
// delete key and associated value keys[i] = null; vals[i] = null;
//从i+1到keys[i] ＝= null的这些键，可能hash的位置是i,当删除i位置的键后，在查找这些键就找不到了，所以需要把这些键重新插入进去 //因为数组大小没有改变，所以这些键重新插入的位置是按顺序从i到keys[i] ＝= null // rehash all keys in same cluster i = (i + 1) % m; while (keys[i] != null) { // delete keys[i] an vals[i] and reinsert Key keyToRehash = keys[i]; Value valToRehash = vals[i]; keys[i] = null; vals[i] = null; n--; put(keyToRehash, valToRehash); i = (i + 1) % m; }
n--;
// halves size of array if it's 12.5% full or less if (n > 0 && n <= m/8) resize(m/2);
assert check(); }
/** * Returns all keys in this symbol table as an {@code Iterable}. * To iterate over all of the keys in the symbol table named {@code st}, * use the foreach notation: {@code for (Key key : st.keys())}. * * @return all keys in this symbol table */ public Iterable<Key> keys() { Queue<Key> queue = new Queue<Key>(); for (int i = 0; i < m; i++) if (keys[i] != null) queue.enqueue(keys[i]); return queue; }
// integrity check - don't check after each put() because // integrity not maintained during a delete() private boolean check() {
// check that hash table is at most 50% full if (m < 2*n) { System.err.println("Hash table size m = " + m + "; array size n = " + n); return false; }
// check that each key in table can be found by get() for (int i = 0; i < m; i++) { if (keys[i] == null) continue; else if (get(keys[i]) != vals[i]) { System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + vals[i]); return false; } } return true; }
/** * Unit tests the {@code LinearProbingHashST} data type. * * @param args the command-line arguments */ public static void main(String[] args) { LinearProbingHashST<String, Integer> st = new LinearProbingHashST<String, Integer>(); for (int i = 0; !StdIn.isEmpty(); i++) { String key = StdIn.readString(); st.put(key, i); }
// print keys for (String s : st.keys()) StdOut.println(s + " " + st.get(s)); } }
