查找（散列表）

定义

散列表通过算术操作将键转化为数组的索引来访问数组中的键值对。散列表的查找算法分两步：

1. 用散列函数将被查找的键转化为一个数组的索引
2. 处理碰撞冲突（拉链法和线性探测法）

优点：常数级别的查找和插入操作
缺点：无法进行有序性相关的操作

散列函数

正整数：将整数散列最常用的方法是除留余数法，选择大小为素数M的数组，对于任意正整数k,计算k除以M的余数

hashCode返回值：将默认的hashCode方法和除留余数法结合起来产生一个0到M-1的整数。通过符号位屏蔽，将一个32位的整数变成一个31位的非负整数。如果直接取余，结果可能是一个负数；如果取绝对值，最大整数可能会返回一个负数。

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

基于拉链法的散列表

将数组中的每个元素指向一个链表，链表中的每个结点都存储了散列值为该元素索引的键值对。发生冲突时，将冲突的元素存到链表当中。

基于拉链法的散列表示意图

代码实现

package edu.princeton.cs.algs4.chapter3;

/**
 * 基于拉链法的散列表
 * Created by tianxianhu on 2017/3/14.
 */
public class SeparateChainingHashST<Key, Value> {

    private int N; //键值对的总数
    private int M; //散列表的大小
    private SequentialSearchST<Key, Value>[] st; // 存放链表对象的数组

    public SeparateChainingHashST() { this(997); }

    public SeparateChainingHashST(int M) {
        // 创建M条链表
        this.M = M;
        st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
        // 对每一个链表初始化
        for (int i = 0; i < M; i++) {
            st[i] = new SequentialSearchST();
        }
    }

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

    public Value get(Key key) {
        return (Value) st[hash(key)].get(key);
    }

    public void put(Key key, Value value) {
        st[hash(key)].put(key,value);
    }

    public void delete(Key key) {
        st[hash(key)].delete(key);
    }
}

基于线性探测法的散列表

线性探测法是使用大小为M的数组保存N个键值对，其中M > N。当发生线性碰撞的时候，直接检查散列表中的下一个位置（将索引值加1）

代码实现

package edu.princeton.cs.algs4.chapter3;

/**
 * 基于线性探测的符号表
 * Created by tianxianhu on 2017/3/14.
 */
public class LinearProbingHashST<Key, Value> {
    private static final int INIT_CAPACITY = 4;

    private int n;          // 符号表中键值对的总数
    private int m;     // 线性探测表的大小
    private Key[] keys;     // 键
    private Value[] vals;   // 值

    public LinearProbingHashST() {
        this(INIT_CAPACITY);
    }

    public LinearProbingHashST(int capacity) {
        m = capacity;
        n = 0;
        keys = (Key[])   new Object[m];
        vals = (Value[]) new Object[m];
    }

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

    private void resize(int cap) {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(cap);
        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;
    }

    public void put (Key key, Value val) {
        // 超过一半，将数组长度翻倍
        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++;
    }

    public Value get (Key key) {
        int i;
        // 探测
        for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
            if (keys[i].equals(key)) {
                return vals[i];
            }
        }
        // 没有改键，返回空
        return null;
    }

    public boolean contains(Key key) {
        if (key == null)
            throw new IllegalArgumentException("argument to contains() is null");

        return get(key) != null;
    }

    // 删除指定键，并将簇中被删除键的右侧的所有键重新插入散列表中
    public void delete(Key key) {
        if (!contains(key))
            return;
        int i = hash(key);
        // 找到键所在的时机位置，然后删除
        while (!keys[i].equals(key)) {
            i = (i + 1) % m;
        }
        keys[i] = null;
        vals[i] = null;
        // 将该元素后面的键值对全部重新插入
        i = (i + 1) % m;
        while (keys[i] != null) {
            Key keyToRedo = keys[i];
            Value valueToRedo = vals[i];
            keys[i] = null;
            vals[i] = null;
            n--;
            put(keyToRedo, valueToRedo);
            i = (i + 1) % m;
        }
        n--;
        if (n > 0 && n == m/8)
            resize(m / 2);
    }
}

所有符号表实现的效率总结

符号表实现的时间复杂度