Map

Map代表一种映射关系，其指这个key与它的value存在某种相关的联系。

当这个Key与一个概念存在某种抽象的联系时，就需要使用Map。

前言

符号表（Symbol Table）是一种存储键值对的数据结构，可以支持快速查找操作。

符号表分为有序和无序两种，有序符号表主要指支持min()、max()等根据键的大小关系来实现的操作。

有序符号表的键需要实现Comparable接口。

public interface UnorderedST<Key, Value> {

    int size();

    Value get(Key key);

    void put(Key key, Value value);

    void delete(Key key);
}Copy to clipboardErrorCopied
public interface OrderedST<Key extends Comparable<Key>, Value> {

    int size();

    void put(Key key, Value value);

    Value get(Key key);

    Key min();

    Key max();

    int rank(Key key);

    List<Key> keys(Key l, Key h);
}

初级实现

链表实现无序符号表

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

    private Node first;

    private class Node {
        Key key;
        Value value;
        Node next;

        Node(Key key, Value value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    @Override
    public int size() {
        int cnt = 0;
        Node cur = first;
        while (cur != null) {
            cnt++;
            cur = cur.next;
        }
        return cnt;
    }

    @Override
    public void put(Key key, Value value) {
        Node cur = first;
        // 如果在链表中找到节点的键等于 key 就更新这个节点的值为 value
        while (cur != null) {
            if (cur.key.equals(key)) {
                cur.value = value;
                return;
            }
            cur = cur.next;
        }
        // 否则使用头插法插入一个新节点
        first = new Node(key, value, first);
    }

    @Override
    public void delete(Key key) {
        if (first == null){
            return;
        }
        if (first.key.equals(key)){
            first = first.next;
        }
        Node pre = first, cur = first.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                pre.next = cur.next;
                return;
            }
            pre = pre.next;
            cur = cur.next;
        }
    }

    @Override
    public Value get(Key key) {
        Node cur = first;
        while (cur != null) {
            if (cur.key.equals(key)){
                return cur.value;
            }
            cur = cur.next;
        }
        return null;
    }
}

二分查找实现有序符号表

使用一对平行数组，一个存储键一个存储值。

二分查找的rank()方法至关重要，当键在表中时，它能够知道该键的位置；当键不在表中时，它也能知道在何处插入新键。

二分查找最多需要logN + 1次比较，使用二分查找实现的符号表的查找操作所需要的时间最多是对数级别的。但是插入操作需要移动数组元素，是线性级别的。

public class BinarySearchOrderedST<Key extends Comparable<Key>, Value> implements OrderedST<Key, Value> {

    private Key[] keys;
    private Value[] values;
    private int N = 0;

    public BinarySearchOrderedST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Object[capacity];
    }

    @Override
    public int size() {
        return N;
    }

    @Override
    public int rank(Key key) {
        int l = 0, h = N - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            int cmp = key.compareTo(keys[m]);
            if (cmp == 0){
                return m;
            }
            else if (cmp < 0){
                h = m - 1;
            }
            else{
                l = m + 1;
            }
        }
        return l;
    }

    @Override
    public List<Key> keys(Key l, Key h) {
        int index = rank(l);
        List<Key> list = new ArrayList<>();
        while (keys[index].compareTo(h) <= 0) {
            list.add(keys[index]);
            index++;
        }
        return list;
    }

    @Override
    public void put(Key key, Value value) {
        int index = rank(key);
        // 如果找到已经存在的节点键为 key，就更新这个节点的值为 value
        if (index < N && keys[index].compareTo(key) == 0) {
            values[index] = value;
            return;
        }
        // 否则在数组中插入新的节点，需要先将插入位置之后的元素都向后移动一个位置
        for (int j = N; j > index; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[index] = key;
        values[index] = value;
        N++;
    }

    @Override
    public Value get(Key key) {
        int index = rank(key);
        if (index < N && keys[index].compareTo(key) == 0){
            return values[index];
        }
        return null;
    }

    @Override
    public Key min() {
        return keys[0];
    }

    @Override
    public Key max() {
        return keys[N - 1];
    }
}

HashMap

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

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

散列函数

对于一个大小为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 进制的整数，每个部分都具有不同的权值。

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

1
2
3

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

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

1	int hash = (((day * R + month) % M) * R + year) % M;

R通常取31。

Java 中的hashCode()实现了哈希函数，但是默认使用对象的内存地址值。在使用hashCode()时，应当结合除留余数法来使用。因为内存地址是32位整数，我们只需要31位的非负整数，因此应当屏蔽符号位之后再使用除留余数法。

1	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;
    }
}

hashCode

Java的hashCode是int类型的，即拥有符号。

哈希冲突

拉链法

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

查找需要分两步，首先查找Key所在的链表，然后在链表中顺序查找。

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

线性探测法

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

使用线性探测法，数组的大小 M 应当大于键的个数 N（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;
    }
}

查找

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;
}

插入

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

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++;
}

删除

删除操作应当将右侧所有相邻的键值对重新插入散列表中。

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 keyToRedo = keys[i];
        Value valToRedo = values[i];
        keys[i] = null;
        values[i] = null;
        N--;
        putInternal(keyToRedo, valToRedo);
        i = (i + 1) % M;
    }
    N--;
    resize();
}

调整数组大小

线性探测法的成本取决于连续条目的长度，连续条目也叫聚簇。当聚簇很长时，在查找和插入时也需要进行很多次探测。例如下图中 2~5 位置就是一个聚簇。

α = N/M，把α称为使用率。理论证明，当α小于1/2时探测的预计次数只在1.5到2.5之间。为了保证散列表的性能，应当调整数组的大小，使得α在[1/4, 1/2]之间。

private void resize() {
    if (N >= M / 2){
        resize(2 * M);
    }
    else if (N <= M / 8){
        resize(M / 2);
    }
}

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

再哈希法

当一个哈希函数产生了哈希冲突后，再用另外一个哈希方法再次进行哈希索引。

小结

符号表算法比较

算法	插入	查找	是否有序
链表实现的无序符号表	N	N	yes
二分查找实现的有序符号表	N	logN	yes
二叉查找树	logN	logN	yes
2-3 查找树	logN	logN	yes
拉链法实现的散列表	N/M	N/M	no
线性探测法实现的散列表	1	1	no

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

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;
    }
}

参考

Cyc2018