package ADT;import java.util.LinkedList;/** * 自己实现的屌丝版的MySeperateChainingHashTable， *  * @author jd * * @param <K> * @param <V> */public class MySeperateChainingHashTable<K, V> {    private static int M = 10;    private LinkedList<Entry<K, V>>[] items;    public MySeperateChainingHashTable() {        items = (LinkedList<Entry<K, V>>[]) (new LinkedList[M]);        for (int i = 0; i < M; i++) {            items[i] = new LinkedList<Entry<K, V>>();        }    }    public void put(K key, V value) {        int idx = hash(key);        LinkedList<Entry<K, V>> list = items[idx];        for (Entry<K, V> each : list) {            if (each.key.equals(key)) {                each.value = value;                return;            }        }        list.add(new Entry<K,V>(key, value));    }    public V get(K key) {        int idx = hash(key);        LinkedList<Entry<K, V>> list = items[idx];        for (Entry<K, V> each : list) {            if (each.key.equals(key)) {                return each.value;            }        }        return null;    }    private int hash(K key) {        int res = key.hashCode();        if (res < 0)            res += M;        return res % M;    }    private static class Entry<K, V> {        public K key;        public V value;        public Entry(K key, V value) {            this.key = key;            this.value =http://www.mamicode.com/ value;        }    }    public static void main(String[] args) {        MySeperateChainingHashTable<Integer, String> hashtable = new MySeperateChainingHashTable<Integer, String>();        for (int i = 0; i < 100; i++) {            hashtable.put(i, i + "" + i);        }        for (int i = 0; i < 100; i++) {            System.out.println(hashtable.get(i));        }    }}

package ADT;import java.util.LinkedList;import java.util.List;// SeparateChaining Hash table class//// CONSTRUCTION: an approximate initial size or default of 101//// ******************PUBLIC OPERATIONS*********************// void insert( x )       --> Insert x// void remove( x )       --> Remove x// boolean contains( x )  --> Return true if x is present// void makeEmpty( )      --> Remove all items/** * Separate chaining table implementation of hash tables. Note that all * "matching" is based on the equals method. *  * @author Mark Allen Weiss */public class SeparateChainingHashTable<T> {    /**     * Construct the hash table.     */    public SeparateChainingHashTable() {        this(DEFAULT_TABLE_SIZE);    }    /**     * Construct the hash table.     *      * @param size     *            approximate table size.     */    public SeparateChainingHashTable(int size) {        theLists = new LinkedList[nextPrime(size)];        for (int i = 0; i < theLists.length; i++)            theLists[i] = new LinkedList<>();    }    /**     * Insert into the hash table. If the item is already present, then do     * nothing.     *      * @param x     *            the item to insert.     */    public void insert(T x) {        List<T> whichList = theLists[myhash(x)];        if (!whichList.contains(x)) {            whichList.add(x);            // Rehash; see Section 5.5            if (++currentSize > theLists.length)                rehash();        }    }    /**     * Remove from the hash table.     *      * @param x     *            the item to remove.     */    public void remove(T x) {        List<T> whichList = theLists[myhash(x)];        if (whichList.contains(x)) {            whichList.remove(x);            currentSize--;        }    }    /**     * Find an item in the hash table.     *      * @param x     *            the item to search for.     * @return true if x isnot found.     */    public boolean contains(T x) {        List<T> whichList = theLists[myhash(x)];        return whichList.contains(x);    }    /**     * Make the hash table logically empty.     */    public void makeEmpty() {        for (int i = 0; i < theLists.length; i++)            theLists[i].clear();        currentSize = 0;    }    /**     * A hash routine for String objects.     *      * @param key     *            the String to hash.     * @param tableSize     *            the size of the hash table.     * @return the hash value.     */    public static int hash(String key, int tableSize) {        int hashVal = 0;        for (int i = 0; i < key.length(); i++)            hashVal = 37 * hashVal + key.charAt(i);        hashVal %= tableSize;        if (hashVal < 0)            hashVal += tableSize;        return hashVal;    }    private void rehash() {        List<T>[] oldLists = theLists;        // Create new double-sized, empty table        theLists = new List[nextPrime(2 * theLists.length)];        for (int j = 0; j < theLists.length; j++)            theLists[j] = new LinkedList<>();        // Copy table over        currentSize = 0;        for (List<T> list : oldLists)            for (T item : list)                insert(item);    }    private int myhash(T x) {        int hashVal = x.hashCode();        hashVal %= theLists.length;        if (hashVal < 0)            hashVal += theLists.length;        return hashVal;    }    private static final int DEFAULT_TABLE_SIZE = 101;    /** The array of Lists. */    private List<T>[] theLists;    private int currentSize;    /**     * Internal method to find a prime number at least as large as n.     *      * @param n     *            the starting number (must be positive).     * @return a prime number larger than or equal to n.     */    private static int nextPrime(int n) {        if (n % 2 == 0)            n++;        for (; !isPrime(n); n += 2)            ;        return n;    }    /**     * Internal method to test if a number is prime. Not an efficient algorithm.     *      * @param n     *            the number to test.     * @return the result of the test.     */    private static boolean isPrime(int n) {        if (n == 2 || n == 3)            return true;        if (n == 1 || n % 2 == 0)            return false;        for (int i = 3; i * i <= n; i += 2)            if (n % i == 0)                return false;        return true;    }    // Simple main    public static void main(String[] args) {        SeparateChainingHashTable<Integer> H = new SeparateChainingHashTable<>();        long startTime = System.currentTimeMillis();        final int NUMS = 2000000;        final int GAP = 37;        System.out.println("Checking... (no more output means success)");        for (int i = GAP; i != 0; i = (i + GAP) % NUMS)            H.insert(i);        for (int i = 1; i < NUMS; i += 2)            H.remove(i);        for (int i = 2; i < NUMS; i += 2)            if (!H.contains(i))                System.out.println("Find fails " + i);        for (int i = 1; i < NUMS; i += 2) {            if (H.contains(i))                System.out.println("OOPS!!! " + i);        }        long endTime = System.currentTimeMillis();        System.out.println("Elapsed time: " + (endTime - startTime));    }}

package ADT;import java.util.LinkedList;import java.util.Queue;/************************************************************************* * Compilation: javac LinearProbingHashST.java Execution: java * LinearProbingHashST *  * Symbol table implementation with linear probing hash table. *  * % java LinearProbingHashST 128.112.136.11 208.216.181.15 null *  *  *************************************************************************/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    // create an empty hash table - use 16 as default size    public LinearProbingHashST() {        this(INIT_CAPACITY);    }    // create linear proving hash table of given capacity    public LinearProbingHashST(int capacity) {        M = capacity;        keys = (Key[]) new Object[M];        vals = (Value[]) new Object[M];    }    // return the number of key-value pairs in the symbol table    public int size() {        return N;    }    // is the symbol table empty?    public boolean isEmpty() {        return size() == 0;    }    // does a key-value pair with the given key exist in the symbol table?    public boolean contains(Key key) {        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;    }    // resize 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;    }    // insert the key-value pair into the symbol table    public void put(Key key, Value val) {        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++;    }    // return the value associated with the given key, null if no such value    public Value get(Key key) {        for (int i = hash(key); keys[i] != null; i = (i + 1) % M)            if (keys[i].equals(key))                return vals[i];        return null;    }    // delete the key (and associated value) from the symbol table    public void delete(Key key) {        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;        // 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();    }    // return all of the keys as in Iterable    public Iterable<Key> keys() {        Queue<Key> queue = new LinkedList<Key>();        for (int i = 0; i < M; i++)            if (keys[i] != null)                queue.add(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 test client.     ***********************************************************************/    public static void main(String[] args) {        LinearProbingHashST<String, Integer> st = new LinearProbingHashST<String, Integer>();    }}

package ADT;// QuadraticProbing Hash table class//// CONSTRUCTION: an approximate initial size or default of 101//// ******************PUBLIC OPERATIONS*********************// bool insert( x )       --> Insert x// bool remove( x )       --> Remove x// bool contains( x )     --> Return true if x is present// void makeEmpty( )      --> Remove all items/** * Probing table implementation of hash tables. Note that all "matching" is * based on the equals method. *  * @author Mark Allen Weiss */public class QuadraticProbingHashTable<T> {    /**     * Construct the hash table.     */    public QuadraticProbingHashTable() {        this(DEFAULT_TABLE_SIZE);    }    /**     * Construct the hash table.     *      * @param size     *            the approximate initial size.     */    public QuadraticProbingHashTable(int size) {        allocateArray(size);        doClear();    }    /**     * Insert into the hash table. If the item is already present, do nothing.     *      * @param x     *            the item to insert.     */    public boolean insert(T x) {        // Insert x as active        int currentPos = findPos(x);        if (isActive(currentPos))            return false;        array[currentPos] = new HashEntry<>(x, true);        theSize++;        // Rehash; see Section 5.5        if (++occupied > array.length / 2)            rehash();        return true;    }    /**     * Expand the hash table.     */    private void rehash() {        HashEntry<T>[] oldArray = array;        // Create a new double-sized, empty table        allocateArray(2 * oldArray.length);        occupied = 0;        theSize = 0;        // Copy table over        for (HashEntry<T> entry : oldArray)            if (entry != null && entry.isActive)                insert(entry.element);    }    /**     * Method that performs quadratic probing resolution.     *      * @param x     *            the item to search for.     * @return the position where the search terminates.     */    private int findPos(T x) {        int offset = 1;        int currentPos = myhash(x);        while (array[currentPos] != null && !array[currentPos].element.equals(x)) {            currentPos += offset; // Compute ith probe            offset += 2;            if (currentPos >= array.length)                currentPos -= array.length;        }        return currentPos;    }    /**     * Remove from the hash table.     *      * @param x     *            the item to remove.     * @return true if item removed     */    public boolean remove(T x) {        int currentPos = findPos(x);        if (isActive(currentPos)) {            array[currentPos].isActive = false;            theSize--;            return true;        } else            return false;    }    /**     * Get current size.     *      * @return the size.     */    public int size() {        return theSize;    }    /**     * Get length of internal table.     *      * @return the size.     */    public int capacity() {        return array.length;    }    /**     * Find an item in the hash table.     *      * @param x     *            the item to search for.     * @return the matching item.     */    public boolean contains(T x) {        int currentPos = findPos(x);        return isActive(currentPos);    }    /**     * Return true if currentPos exists and is active.     *      * @param currentPos     *            the result of a call to findPos.     * @return true if currentPos is active.     */    private boolean isActive(int currentPos) {        return array[currentPos] != null && array[currentPos].isActive;    }    /**     * Make the hash table logically empty.     */    public void makeEmpty() {        doClear();    }    private void doClear() {        occupied = 0;        for (int i = 0; i < array.length; i++)            array[i] = null;    }    private int myhash(T x) {        int hashVal = x.hashCode();        hashVal %= array.length;        if (hashVal < 0)            hashVal += array.length;        return hashVal;    }    private static class HashEntry<T> {        public T element; // the element        public boolean isActive; // false if marked deleted        public HashEntry(T e) {            this(e, true);        }        public HashEntry(T e, boolean i) {            element = e;            isActive = i;        }    }    private static final int DEFAULT_TABLE_SIZE = 101;    private HashEntry<T>[] array; // The array of elements    private int occupied; // The number of occupied cells    private int theSize; // Current size    /**     * Internal method to allocate array.     *      * @param arraySize     *            the size of the array.     */    private void allocateArray(int arraySize) {        array = new HashEntry[nextPrime(arraySize)];    }    /**     * Internal method to find a prime number at least as large as n.     *      * @param n     *            the starting number (must be positive).     * @return a prime number larger than or equal to n.     */    private static int nextPrime(int n) {        if (n % 2 == 0)            n++;        for (; !isPrime(n); n += 2)            ;        return n;    }    /**     * Internal method to test if a number is prime. Not an efficient algorithm.     *      * @param n     *            the number to test.     * @return the result of the test.     */    private static boolean isPrime(int n) {        if (n == 2 || n == 3)            return true;        if (n == 1 || n % 2 == 0)            return false;        for (int i = 3; i * i <= n; i += 2)            if (n % i == 0)                return false;        return true;    }    // Simple main    public static void main(String[] args) {        QuadraticProbingHashTable<String> H = new QuadraticProbingHashTable<>();        long startTime = System.currentTimeMillis();        final int NUMS = 2000000;        final int GAP = 37;        System.out.println("Checking... (no more output means success)");        for (int i = GAP; i != 0; i = (i + GAP) % NUMS)            H.insert("" + i);        for (int i = GAP; i != 0; i = (i + GAP) % NUMS)            if (H.insert("" + i))                System.out.println("OOPS!!! " + i);        for (int i = 1; i < NUMS; i += 2)            H.remove("" + i);        for (int i = 2; i < NUMS; i += 2)            if (!H.contains("" + i))                System.out.println("Find fails " + i);        for (int i = 1; i < NUMS; i += 2) {            if (H.contains("" + i))                System.out.println("OOPS!!! " + i);        }        long endTime = System.currentTimeMillis();        System.out.println("Elapsed time: " + (endTime - startTime));        System.out.println("H size is: " + H.size());        System.out.println("Array size is: " + H.capacity());    }}