3-5-小结与应用.md

小结

1. 符号表算法比较

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

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

2. Java 的符号表实现

• java.util.TreeMap：红黑树
• java.util.HashMap：拉链法的散列表

3. 稀疏向量乘法

当向量为稀疏向量时，可以使用符号表来存储向量中的非 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;
    }
}