散列表

啥叫散列表？根据你提供的key值，通过设计的hash函数求得一值，找到对应的数组位置，将其存储在该位置。这里遇到hash冲突时我们采用两种方法：拉链法和线性探测法

拉链法

所谓拉链法就是当hash值相同时，我们采用链式存储，像拉链一样，新节点放在链表首位。该怎么用代码实现？SequentSearchST类型数组，通过它来插入删除节点。

//拉链法
public class SeparateChainingHash<Key, Value> {
    
    private static final int INIT_CAPACITY = 4;
    
    private int n; //节点总数
    private int m; //数组长度
    private SequentSearchST<Key, Value>[] st;  //SequentSearchST类型数组
    
    public SeparateChainingHash() {
        this(INIT_CAPACITY);
    }

    @SuppressWarnings("unchecked")
    public SeparateChainingHash(int m) {
        this.m = m;
//不能直接new一个泛型数组，通过插入一个强制转换来解决
        st = (SequentSearchST<Key, Value>[]) new SequentSearchST[m];  
        for (int i = 0; i < m; i++) {
            st[i] = new SequentSearchST<>();
        }
    }
    
    public void resize(int newCapacity) {
        SeparateChainingHash<Key, Value> temp = new SeparateChainingHash<>(newCapacity);
        for (int i = 0; i < n; 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;
    }
    
    public int size() {
        return n;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    //保证是个正数所以取后31位
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) & m;
    }
    
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }
    
    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to get() is null");
        int hash = hash(key);
        return st[hash].get(key);
    }
    
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        if (value == null) {
            delete(key);
            return;
        }
        if (n > 10*m) resize(2*m);
        int hash = hash(key);
        if (!st[hash].contains(key)) n++;
        st[hash].put(key, value);
    }
    
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        
        int hash = hash(key);
        if (st[hash].contains(key)) n--;
        st[hash].delete(key);
        
        if (m > INIT_CAPACITY && n <= 2*m) resize(m/2);
    }
    

}


//用来创建删除节点等操作
public class SequentSearchST<Key, Value> {
    
    private int n;
    private Node first;

    public SequentSearchST() {
        // TODO Auto-generated constructor stub
    }
    
    private class Node{
        private Key key;
        private Value value;
        private Node next;
        
        public Node(Key key, Value value, Node next) {
            this.next = next;
            this.value = value;
            this.key = key;
        }
    }
    
    public int size() {
        return n;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != null;
    }
    
    public Value get(Key key) {
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                return x.value;
            }
        }
        return null;
    }
    
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("first argument in put() is null");
        if (value == null) {
            delete(key);
            return;
        }
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.value = value;
                return;
            }
        }
        first = new Node(key, value, first);
        n++;
    }
    
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument in delete() is null");
        first = delete(first, key);
    }
    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;
    }
    
    public Iterable<Key> keys() {
        MyQueue<Key> queue = new MyQueue<>();
        for (Node x = first; x != null; x = x.next) {
            queue.enqueue(x.key);
        }
        return queue;
    }
}


//自己实现的Queue
public class MyQueue<Item> implements Iterable<Item> {
    private Node<Item> first;
    private Node<Item> last;
    private int n;

    public MyQueue() {
        first = null;
        last = null;
        n = 0;
    }
    
    public boolean isEmpty() {
        return first == null;
    }
    public int size() {
        return n;
    }
    
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }
    
    public void enqueue(Item item) {
        Node<Item> oldLast = last;
        last = new Node<>();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else oldLast.next = last;
        n++;
    }
    
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("call dequeue() with empty queue");
        Item item = first.item;
        first = first.next;
        n--;
        if (isEmpty()) last = null;
        return item;
    }
    
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("call peek() with empty queue");
        return first.item;
    }
    
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (Item item: this) {
            builder.append(item);
            builder.append(" ");
        }
        return builder.toString();
    }

    @Override
    public Iterator<Item> iterator() {
        return new QueueIterator<Item>(first);
    }
    private class QueueIterator<Item> implements Iterator<Item> {
        private Node<Item> current;
        
        public QueueIterator(Node<Item> first) {
            current = first;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }
        
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
        
    }

}

线性探测法

与上面的拉链法不同之处就在于对hash碰撞的处理。线性探测法就如它的名字一样，当通过计算所得到的hash值找到对应数组位置不为空时，我们就从这开始往后寻找，直到找到第一个空位，将值插入到这。

public class LinearProbingHash<Key, Value> {

    private static final int INIT_CAPACITY = 4;
    
    private int m; //数组大小
    private int n; //元素个数
    private Key[] keys;
    private Value[] values;
    
    public LinearProbingHash() {
        this(INIT_CAPACITY);
    }

    public LinearProbingHash(int capacity) {
        m = capacity;
        n = 0;
        keys = (Key[]) new Object[m];
        values = (Value[]) new Object[m];
    }
    
    public int size() {
        return n;
    }
    
    public boolean isEmpty() {
        return size() == 0;
    }
    
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % m;
    }
    
    private void resize(int capacity) {
        LinearProbingHash<Key, Value> temp = new LinearProbingHash<>(capacity);
        for (int i = 0; i < m; i++) {
            if (keys[i] != null) {
                temp.put(keys[i], values[i]);;
            }
        }
        this.keys = temp.keys;
        this.values = temp.values;
        this.m = temp.m;
    }
    
    public boolean contains(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to contains() is null");
        return get(key) != 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 (key.equals(keys[i])) {
                return values[i];
            }
        }
        return null;
    }
    
    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("argument to put() is null");
        if (value == null) {
            delete(key);
            return;
        }
        if (n >= m/2) resize(2*m);
        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
             if (key.equals(keys[i])) {
                 values[i] = value;
                 return;
             }
        }
        keys[i] = key;
        values[i] = value;
        n++;
    }
//找到并删除key，将其之后所有连续不中断的重新插入。    
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        if (!contains(key)) return;
        int i = hash(key);
        while (!key.equals(keys[i])) {
            i = (i + 1) % m;
        }
        keys[i] = null;
        values[i] = null;
        i = (i + 1) % m;
        while(keys[i] != null) {
            Key oldKey = keys[i];
            Value oldValue = values[i];
            keys[i] = null;
            values[i] = null;
            n--;
            put(oldKey, oldValue);
            i = (i + 1) % m;
        }
        n--;
        if (n > 0 && n <= m/8) resize(m/2);  //注意数组大小的调整
        assert check();
    }
    
    private boolean check() {
        if (m < 2*n) {
            System.err.println("实际元素个数： " + n + "; 数组大小 " + m);
            return false;
        }
        
        for (int i = 0; i < m; i++) {
            if (keys[i] == null) continue;
            else if(get(keys[i]) != values[i]) {
                System.err.println("get[" + keys[i] + "] = " + get(keys[i]) + "; vals[i] = " + values[i]);
                return false;
            }
        }
        return true;
    }

}

线性探测法的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫做族簇。n/m值越大说明存在的族簇越长越多，我们让比值保持在1/8~1/2之间。