SeparateChainingHashST

简书 賈小強
转载请注明原创出处，谢谢！

package com.lab1.test3;

import java.util.LinkedList;
import java.util.Queue;

public class SeparateChainingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;
    private int n;
    private int m;
    private SequentailSearchST<Key, Value>[] st;

    public SeparateChainingHashST() {
        this(INIT_CAPACITY);
    }

    public SeparateChainingHashST(int m) {
        this.m = m;
        st = new SequentailSearchST[m];
        for (int i = 0; i < m; i++) {
            st[i] = new SequentailSearchST<>();
        }
    }

    private void resize(int capacity) {
        SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<>(capacity);
        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.st = temp.st;
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % m;
    }

    private void delete(Key key) {
        int i = hash(key);
        if (st[i].contains(key)) {
            n--;
        }
        st[i].delete(key);
        if (n <= m * 2) {
            resize(m / 2);
        }
    }

    private Iterable<Key> keys() {
        Queue<Key> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (Key key : st[i].keys()) {
                queue.add(key);
            }
        }
        return queue;
    }

    private Value get(Key key) {
        int i = hash(key);
        return st[i].get(key);
    }

    private boolean contains(Key key) {
        return get(key) != null;
    }

    private boolean isEmpty() {
        return n == 0;
    }

    private int size() {
        return n;
    }

    private void put(Key key, Value value) {
        if (n >= m * 10) {
            resize(m * 2);
        }
        int i = hash(key);
        if (!st[i].contains(key)) {
            n++;
        }
        st[i].put(key, value);
    }

    public static void main(String[] args) {
        SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<>();
        String test = "S E A R C H E X A M P L E";
        String[] keys = test.split(" ");
        for (int i = 0; i < keys.length; i++) {
            st.put(keys[i], i);
        }
        System.out.println("size         = " + st.size());
        System.out.println("isEmpty      = " + st.isEmpty());
        System.out.println("contains     = " + st.contains("S"));
        st.delete("S");
        System.out.println("contains     = " + st.contains("S"));
        for (String key : st.keys()) {
            System.out.println(key + " " + st.get(key));
        }
    }
}

输出

size         = 10
isEmpty      = false
contains     = true
contains     = false
L 11
P 10
X 7
H 5
M 9
A 8
E 12
R 3
C 4

Happy learning !!