散列表总结（散列函数，拉链法，线性探测法）

散列表类似于数组，可以把散列表的散列值看成数组的索引值，访问散列表和访问数组元素一样快速，他可以在常数时间内实现查找和插入操作。

由于无法通过散列值知道键的大小，因此散列表无法实现有序性操作。

散列函数

对于一个大小为M的散列表，散列函数能够把任意的数转换成【0，M-1】内的正整数，该正整数即为hash值。

散列表存在冲突，也就是两个不同的键可能有相同的hash值。

散列函数应该满足三个条件：

一致性：相等的键应当有相等的hash值，两个键相等表示调用equals返回的值相等

高效性：计算应当简便，有必要的话可以把hash值缓存起来，在调用hash函数时直接返回。

均匀性：所有键的hash值应当均匀地分布在【0，m-1】之间，如果不能满足这个条件，有可能产生很多冲突，从而导致散列表的性能下降。

除留余数法将整数散列到 [0, M-1] 之间，例如一个正整数 k，计算 k%M 既可得到一个 [0, M-1] 之间的 hash 值。注意 M 最好是一个素数，否则无法利用键包含的所有信息。例如 M 为 10k，那么只能利用键的后 k 位。

对于其它数，可以将其转换成整数的形式，然后利用除留余数法。例如对于浮点数，可以将其的二进制形式转换成整数。

对于多部分组合的类型，每个部分都需要计算 hash 值，这些 hash 值都具有同等重要的地位。为了达到这个目的，可以将该类型看成 R 进制的整数，每个部分都具有不同的权值。

例如，字符串的散列函数实现如下：

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;Copy to clipboardErrorCopied

再比如，拥有多个成员的自定义类的哈希函数如下：

int hash = (((day * R + month) % M) * R + year) % M;Copy to clipboardErrorCopied

R 通常取 31。

java中的hashcode（），实现了哈希函数，但是默认使用对象内存地址值，在使用hashCode（）时，使用除留余数法，因为内存地址32，符号位一位，只需要31即可。

int hash = (x.hashCode() & 0x7fffffff) % M;

使用 Java 的 HashMap 等自带的哈希表实现时，只需要去实现 Key 类型的 hashCode() 函数即可。Java 规定 hashCode() 能够将键均匀分布于所有的 32 位整数，Java 中的 String、Integer 等对象的 hashCode() 都能实现这一点。以下展示了自定义类型如何实现 hashCode()：

public class Transaction {

    private final String who;
    private final Date when;
    private final double amount;

    public Transaction(String who, Date when, double amount) {
        this.who = who;
        this.when = when;
        this.amount = amount;
    }

    public int hashCode() {
        int hash = 17;
        int R = 31;
        hash = R * hash + who.hashCode();
        hash = R * hash + when.hashCode();
        hash = R * hash + ((Double) amount).hashCode();
        return hash;
    }
}

 拉链法：

拉链法使用链表来存储hash值相同的键，从而解决冲突。

查找需要分两步：

首先查找Key所在的链表，然后在链表中顺序查找。

对于N个键，M条链表（N>M）如果哈希函数能够满足均匀性的条件，每条链表的大小趋向于 N/M，因此未命中的查找和插入操作所需要的比较次数为 ~N/M。

线性探测法：

使用空位来解决冲突，当冲突发生时，向前探测一个空位来存储冲突的键。

使用线性探测法，数组的大小M应当大于N。

public class LinearProbingHashST<Key,Value> implements UnorderedST<Key,Value> {

    private int N=0;
    private int M=16;
    private Key[] keys;
    private Value[] values;
    public LinearProbingHashST(){
        init();
    }
    public LinearProbingHashST(int M){
        this.M=M;
        init();
    }

    private void init() {
        keys=(Key[]) new Object[M];
        values=(Value[]) new Object[M];
    }
    private int hash(Key key){
        return (key.hashCode()&0x7fffffff)%M;
    }
    @Override
    public int size() {
        return N;
    }

    @Override
    public Value get(Key key) {
        for(int i=hash(key);keys[i]!=null;i=(i+1)%M){
            if(keys[i].equals(key)){
                return values[i];
            }
        }
        return null;
    }

    @Override
    public void put(Key key, Value value) {
        resize();
        putInternal(key,value);
    }

    private void resize() {
            //调整数组大小
        if(N>=M/2){
            resize(2*M);
        }else if(N<=M/8){
            resize(M/2);
        }
    }

    private void resize(int ix) {
        LinearProbingHashST<Key,Value> t=new LinearProbingHashST<>(ix);
        for(int i=0;i<M;i++){
            if(keys[i]!=null){
                t.putInternal(keys[i],values[i]);
            }
        }
        keys=t.keys;
        values=t.values;
        M=t.M;
    }

    private void putInternal(Key key, Value value) {
        int i;
        for( i=hash(key);keys[i]!=null;i=(i+1)%M){
            if(keys[i].equals(key)){
                 values[i]=value;
                 return;
            }
            keys[i]=key;
            values[i]=value;
            N++;

        }
    }

    @Override
    public void delete(Key key) {
        int i=hash(key);
        while (keys[i]!=null&&!key.equals(keys[i])){
            i=(i+1)%M;
        }
        if(keys[i]==null){
            return;
        }
        keys[i]=null;
        values[i]=null;

        //将之后相连的键值对重新插入
        i=(i+1)%M;
        while(keys[i]!=null){
            Key key1=keys[i];
            Value value1=values[i];
            keys[i]=null;
            values[i]=null;
            N--;
            putInternal(key1,value1);
            i=(i+1)%M;
        }
        N--;
        resize();
    }
}

1. 符号表算法比较

应当优先考虑散列表，当需要有序性操作时使用红黑树。

Java符号表的实现

java.util.TreeMap:红黑树

java.util.HashMap ：拉链法散列表

稀疏向量乘法

当向量为稀疏向量时，可以使用符号表来存储向量中的非0索引和值，使得乘法运算只需要对哪些非0元素进行即可。

public class SparseVector {
    private HashMap<Integer, Double> hashMap;

    public SparseVector(double[] vector) {
        hashMap = new HashMap<>();
        for (int i = 0; i < vector.length; i++)
            if (vector[i] != 0)
                hashMap.put(i, vector[i]);
    }

    public double get(int i) {
        return hashMap.getOrDefault(i, 0.0);
    }

    public double dot(SparseVector other) {
        double sum = 0;
        for (int i : hashMap.keySet())
            sum += this.get(i) * other.get(i);
        return sum;
    }
}