（三）查找

符号表

符号表最主要目的就是将一个键和一个值联系起来。用例能将一个键值对插入符号表并之后能从符号表的所有键值对中按键直接找到对应的值。

符号表是一种存储键值对的数据结构，支持两种操作：插入（put），即将一组新的键值对存入表中；查找（get），即根据给定的键得到对应的值。

API

public class ST<Key, Value>
                    ST()
            void    put(Key key,Value val)  //将键值对存入表中（若值为空则将键 key 从表中删除）
            Value   get(Key key)            //获取键 key 对应的值
             void   delete(Key key)         //从表中删去键 key （及其对应的值）
          boolean   contains(Key key)       //键 key 在表中是否有对应的值
          boolean   isEmpty()               //表是否为空
              int   size()                  //表中的键值对数量
    Iterable<Key>   keys()                  //表中的所有键的集合

默认实现：

   void   delete(Key key)        put(key, null)
boolean   contains(key)          return get(key) != null;
boolean   isEmpty()              return size() == 0

设计决策

• 泛型
• 不含重复的键
• 键不能为空（null）
• 值不能为空
• 删除操作：延时删除（put(key, null)是 delete(key) 的一种简单的延时型实现）或即时删除
• 迭代：在 API 第一行加上 implements Iterable<Key> 这句话，强制所有实现都必须包含 iterator() 方法来返回一个实现了 hasNext() 和 next() 方法的迭代器。定义一个 keys() 方法来返回一个 Iterable<Key> 对象以便遍历所有的键。
• 键的等价性

有序符号表

public class ST<Key extends Comparable<Key>, Value>
                    ST()                    //创建一张有序符号表
            void    put(Key key,Value val)  //将键值对存入表中（若值为空则将键 key 从表中删除）
            Value   get(Key key)            //获取键 key 对应的值
             void   delete(Key key)         //从表中删去键 key （及其对应的值）
          boolean   contains(Key key)       //键 key 在表中是否有对应的值
          boolean   isEmpty()               //表是否为空
              int   size()                  //表中的键值对数量
              Key   min()                   //最小的键
              Key   max()                   //最大的键
              Key   floor(Key key)          //小于等于key的最大键
              Key   ceiling(Key key)        //大于等于key的最小键
              int   rank(Key key)           //小于key的键的数量
              Key   select(int k)           //排名为k的键
             void   deleteMin()             //删除最小的键
             void   deleteMax()             //删除最大的键
             int    size(Key lo, Key hi)    //[lo...hi]之间键的数量
    Iterable<Key>   keys(Key lo, Key hi)    //[lo...hi]之间的所有键，已排序
    Iterable<Key>   keys()                  //表中的所有键的集合

默认实现：

void deleteMin()            delete(min())
void deleteMax()            delete(max())
int size(Key lo, Key hi)    if(hi.compareTo(lo) < 0)
                                return 0;
                            else if(contains(hi))
                                return rank(hi) - rank(lo) + 1;
                            else
                                return rank(hi) - rank(lo);
Iterable<Key> keys()        return keys(min(), max());

• 键的等价性：Java 的一条最佳实践就是维护所有的 Comparable 类型中的 compareTo() 方法和 equals() 方法的一致性。即任何一种 Comparable 类型的两个值 a 和 b 都要保证（a.compareTo(b) == 0 和 a.equals(b) 的返回值相同）。

二叉查找树

二叉查找树（BST）是一棵二叉树，其中每个节点都含有一个 Comparable 的键（以及相关联的值）且每个节点的键都大于其左子树中任意节点的键而小于右子树的任意节点的键。

数据表示

和链表一样，嵌套定义一个私有类来表示二叉查找树的节点。每个节点包含键、值、左节点、右节点和以该节点为根的子树的节点总数。

递归：递归调用沿着树向下走，递归调用返回沿着树向上爬。对于put方法，意味重置搜索路径上每个父节点指向子节点的链接，并增加路径上每个节点中的计数器的值。

分析

假设键分布均匀（随机），二叉查找树和快排类似，查找命中平均所需比较次数为logN.

有序性相关的方法与删除操作

二叉查找树广泛应用的一个重要原因是它能够保持键的有序性，可以用来实现有序符号表。

• 向上取整和向下取整
  若给定的键key小于二叉查找树根节点的键，则小于等于key的最大键（floor）一定在根节点的左子树中；
  若给定键key大于二叉查找树的根节点，则只有当根节点右子树中存在小于等于key的节点，小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键。
• 删除最大/最小键
  删除最小键deleteMin()只要不断深入根节点左子树直到遇到一个空链接，然后将指向该节点的链接指向该节点的右子树（递归调用返回其右链接）。
• 删除操作
  1. 将指向即将被删除的节点链接保存为t
  2. 将x指向它的后继节点min(t.right)
  3. 将x右链接指向deleteMin(t.right)
  4. 将x的左链接（本为空）设为t.left
• 范围查找
  返回给定范围内键的keys()的方法

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node {
        Key key;
        Value val;
        Node left, right;
        /**
         * 以该节点为根节点的子树中节点个数
         */
        int N;

        public Node(Key key, Value val, int n) {
            this.key = key;
            this.val = val;
            N = n;
        }
    }

    public int size() {
        return size(root);
    }
    private int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }
    public Value get(Key key) {
        return get(root, key);
    }
    private Value get(Node x, Key key) {
        //在以x为根节点的子树中查找并返回key所对应的值
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        }
        return x.val;
    }
    public void put(Key key, Value val) {
        //查找key，找到则更新它的值，否则为它创建一个新节点
        root = put(root, key, val);
    }
    private Node put(Node x, Key key, Value val) {
        if (x == null) {
            return new Node(key, val, 1);
        }
        int cmp = key.compareTo(key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }
        x.N = size(x.left) + size(x.right) + 1;
        System.out.println(x.key);
        return x;
    }
    public Key min() {
        return min(root).key;
    }
    private Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }
    public Key floor(Key key) {
        Node x = floor(root, key);
        if (x == null) {
            return null;
        }
        return x.key;
    }
    private Node floor(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            Node tmp = floor(x.right, key);
            if (tmp != null) {
                return tmp;
            } else {
                return x;
            }
        } else if (cmp < 0) {
            return floor(x.left, key);
        }
        return x;
    }
    public Key select(int k) {
        return select(root, k).key;
    }
    public Node select(Node x, int k) {
        if (x == null) {
            return null;
        } else {
            if (size(x.left) > k) {
                return select(x.left, k);
            } else if (size(x.left) + 1 == k) {
                return x;
            } else {
                return select(x.right, k - 1 - size(x.left));
            }
        }
    }
    public int rank(Key key) {
        return rank(root, key);
    }
    private int rank(Node x, Key key) {
        //返回以x为根节点的子树中小于x.key的键的数量
        if (x == null) {
            return 0;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            return size(x.left) + 1 + rank(x.right, key);
        } else if (cmp < 0) {
            return rank(x.left, key);
        } else {
            return size(x.left);
        }
    }
    public void deleteMin() {
        root = deleteMin(root);
    }
    private Node deleteMin(Node x) {
        if (x.left == null) {
            return x.right;
        }
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public void delete(Key key) {
        root = delete(root, key);
    }
    private Node delete(Node x, Key key) {
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
    public Iterable<Key> keys() {
        return keys(min(), max());
    }
    private Iterable<Key> keys(Key lo, Key hi) {
        Queue<Key> queue = new LinkedBlockingQueue<>();
        keys(root, queue, lo, hi);
        return queue;
    }
    //类似中序遍历
    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) {
            return;
        }
        int cmplo = lo.compareTo(x.key);
        int cmphi = lo.compareTo(x.key);
        //如果下界小于当前节点key，则先在左子树中进行范围查找合适节点
        if (cmplo < 0) {
            keys(x.left, queue, lo, hi);
        }
        //如果当前节点在范围内，则加入队列
        if (cmplo <= 0 && cmphi >= 0) {
            queue.add(x.key);
        }
        //如果上界大于当前节点key，则在右子树中进行范围查找合适节点
        if (cmphi > 0){
            keys(x.right,queue,lo,hi);
        }
    }
    public Key max() {
        return null;
    }
}

性能分析

在一棵二叉查找树中，所有操作最坏情况下所需时间都和树的高度（树中任意节点最大深度）成正比。
基本的二叉查找树的实现常常是非递归的。

平衡查找树

无论怎样构造，运行时间都是对数级别的。。。。。。。。。。。。。。。。。。。。。。。。。。。。

2-3查找树

标准二叉树中的结点称为2-结点（含有一个键和两条链接），引入3-结点，含有两个键和三条链接，2-结点和3-结点的每条链接都对应着保存键所分割产生的一个区间。

• 定义：一棵2-3查找树或为一棵空树，或由以下结点组成：
  • 2-结点，含有一个键（及其对应的值）和两条链接，左链接指向的2-3树的键都小于该节点，右链接指向的2-3树中的键都大于该节点。
  • 3-节点，含有两个键（及其对应的值）和三条链接，左链接指向的2-3树的键都小于该节点，中链接指向的2-3树中的键都位于该节点两个键之间，右链接指向的2-3树中的键都大于该节点。

一棵完美平衡的2-3查找树中的所有空连接到根节点的距离都应该是相同的

查找

向2-结点插入新键

要在2-3树中插入结点，可以和二叉查找树一样先进行一次未命中查找，但新节点直接挂在树底部不能保持树的平衡，但使用2-3树目的就是为了保持平衡，当未命中查找结束于一个2-结点的解决办法是——把这个2结点替换为一个3-结点；若结束于3-结点则稍麻烦。

向只含一个3-结点树中插入新键

先临时将新键存入该节点，使之成为4-结点，再将其转换为一棵由3个2-结点组成的2-3树。插入前树的高度为0，插入后树的高度为1。

向父结点为2-结点的3-结点中插入新键

转换可看成将指向3-结点的的一条链接替换为父结点中的原中键左右两边的两条链接，并分别指向两个新的2-结点。

向父结点为3-结点的3-结点中插入新键

分解根节点

若从插入结点到根节点的路径上都是3-结点，则将根节点变成一个临时4-结点，变换根节点，将其分解为3个2-结点，使得树高加1。

局部变换

将4-结点分解为一棵2-3树有6种可能：

2-3树插入算法根本在于这些变换都是局部的：除了相关结点和链接外不必修改或检查树其它部分。

全局性质

局部变换不会影响树的全局有序性和平衡性：任意空链接到根结点的路径的长度都相等。

• 标准二叉树是由上向下生长，2-3树是由下向上生长
• 在一棵大小为N的2-3树中，查找和插入操作访问结点不超过lgN个。

红黑二叉查找树

接下来利用红黑二叉查找树的简单数据结构来表达并实现上文2-3树。

替换3-结点

红黑二叉查找树基本思想是用标准二叉查找树（完全由2-结点构成）和一些额外信息（替换3-结点）来表示2-3树。

2-3查找树需要用到2-结点和3-结点，红黑树使用红链接来实现3-结点。指向一个节点的链接颜色如果为红色，那么这个节点和上层节点表示的是一个3-结点，而黑色则是普通链接。这样无须修改就可直接使用标准二叉查找树的get()方法。

红黑树等价定义

红黑树另一种定义是含有红黑链接且满足下列条件的二叉查找树：

• 红链接均为左链接
• 没有任何一个结点同时和两条红链接相连
• 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同

满足这样定义的红黑树和相应的2-3树一一对应。

一一对应

• 若将红黑树中红链接画平，那么所有空链接到根节点距离都相同
• 红黑树既是二叉查找树也是2-3树

若能在保持一一对应基础上实现2-3树的插入算法，就能将两个算法有点结合起来：

• 二叉查找树简洁高效的查找方法
• 2-3树中高效的平衡插入算法

颜色表示

每个结点都有一条指向自己的链接，若此链接为红，则令变量color为true，黑色则为false。约定空链接为黑色。代码见实现。

旋转

合法的红链接都为左链接，如果出现右链接为红链接，那么就需要进行左旋转操作。实际只是将两个键中较小者作为根结点 变为 将较大者作为根结点。代码见实现。

旋转后重置父节点链接

旋转后可能会导致连续两条红色链接，进行右旋转就是为了转换两个连续的左红链接。代码见实现。

在插入新键时可以通过旋转保证2-3树和红黑树一一对应和红黑树的重要性质：有序性和完美平衡性。

向2-结点插入新键

左插和右插两种情况结果均为一棵和单个3-结点等价的红黑树，其中含有两个键，一条红链接，树的黑链接高度为1。

向树底部2-结点插入新键

向红黑树插入一个新键会在树底部新增一个结点，但总是用红链接将新结点和它的父节点相连。

向一棵双键树（即3-结点）插入新键

3种情况（通过0次，1次和2次旋转）：

• 新键大于原树两个键
  • 将两条连接较大和较小结点的红链接都变黑即可
• 新键小于原树两个键
  • 产生两条连续左红链接，只需将上层红链接右旋转即可得到第一种情况
• 新键介于原树两键之间
  • 会产生两条连续红链接（一条左红链接连接一条右红链接），此时只需将下层红链接右旋即可得到第二种情况

颜色变换

一个 4-节点在红黑树中表现为一个节点的左右子节点都是红色的。分裂 4- 节点除了需要将子节点的颜色由红变黑之外，同时需要将父节点的颜色由黑变红，从 2-3 树的角度看就是将中间节点移到上层节点。

根结点总是黑色

每次插入后都将根结点设为黑色，每当根结点由红变黑时树的黑链接高度加1。

将红链接在树中向上传递

红黑树中实现2-3树插入算法关键：在3-结点下插入新键，先创建一个临时4-结点，将其分解并将红链接由中间键传递给它的父结点，重复该过程直到遇到一个2-结点或根节点。

1. 若右子结点是红色而左子结点是黑色，进行左旋转
2. 若左子结点是红色且它的左子结点也是红色，进行右旋转
3. 若左右子结点均红色，进行颜色变换

实现

public class RedBlackBST<Key extends Comparable<Key>, Value> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private Node root;
    private class Node {
        Key key;
        Value value;
        Node left, right;
        //这课子树中结点总数
        int N;
        //由其父节点指向它的链接的颜色
        boolean color;
        public Node(Key key, Value value, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
        }
    }
    //结点和其父节点之间链接的颜色
    private boolean isRed(Node x) {
        if (x == null) {
            return false;
        }
        return x.color == RED;
    }
    int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.N;
        }
    }
    //左旋转
    Node rotateLeft(Node h) {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }
    Node rotateRight(Node h) {
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }
    private void flipColors(Node x) {
        x.left.color = x.right.color = BLACK;
        x.color = RED;
    }
    public Node put(Key key, Value val) {
        root = put(root, key, val);
        root.color = BLACK;
    }
    private Node put(Node root, Key key, Value val) {
        //标准插入，和父节点用红链接相连
        if (root == null) {
            return new Node(key, val, 1, RED);
        }
        int cmp = key.compareTo(root.key);
        if (cmp < 0) {
            root.left = put(root.left, key, val);
        } else if (cmp > 0) {
            root.right = put(root.right, key, val);
        } else {
            root.value = val;
        }
        //左黑右红，左旋
        if (isRed(root.right) && !isRed(root.left)) {
            root = rotateLeft(root);
        }
        if (isRed(root.left) && isRed(root.left.left)) {
            root = rotateRight(root);
        }
        if (isRed(root.left) && isRed(root.right)) {
            flipColors(root);
        }
        root.N = 1 + size(root.left) + size(root.right);
        return root;
    }
}

插入操作和二叉查找树的插入操作一致，只是在最后加入了旋转和颜色变换操作即可。
根节点一定为黑色，因为根节点没有上层节点，也就没有上层节点的左链接指向根节点。flipColors() 有可能会使得根节点的颜色变为红色，每当根节点由红色变成黑色时树的黑链接高度加 1.

删除最小键

如果最小键在一个 2- 节点中，那么删除该键会留下一个空链接，就破坏了平衡性，因此要确保最小键不在 2-节点中。为保证不会删除一个2-结点，沿着左链接向下变换，确保当前结点不是2-结点（可能是3-结点，也可能是4-结点）。

将 2- 节点转换成 3- 节点或者 4- 节点有两种方法，一种是向上层节点拿一个 key，一种是向兄弟节点拿一个 key。如果上层节点是 2- 节点，那么就没办法从上层节点拿 key 了，因此要保证删除路径上的所有节点都不是 2- 节点。在向下删除的过程中，保证以下情况之一发生：

• 如果当前节点的左子节点不是 2- 节点，完成；
• 如果当前节点的左子节点是 2- 节点而它的兄弟节点不是 2- 节点，向兄弟节点拿一个 key 过来；
• 如果当前节点的左子节点和它的兄弟节点都是 2- 节点，将左子节点、父节点中的最小键和最近的兄弟节点合并为一个 4- 节点

最后得到一个含有最小键的 3-节点或者 4-节点，直接从中删除。然后再从头分解所有临时的 4-节点。

红黑树性质

• 一颗大小为 N 的红黑树的高度不会超过 2logN。最坏的情况下是它所对应的 2-3 树中构成最左边的路径节点全部都是 3- 节点而其余都是 2- 节点。
• 红黑树大多数的操作所需要的时间都是对数级别的。
• 一棵大小为N的红黑树中，根结点到任意结点的平均路径长度为 logN

参考：
技术面试需要掌握的基础知识整理

散列表

散列函数

对于一个大小为 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;

再比如，拥有多个成员的自定义类的哈希函数如下，R 的值不是很重要，通常取 31。

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

hashCode() 和 equals()

每种数据类型都需要相应散列函数，Java令所有数据类型都继承了一个能返回32位整数的hashCode()方法。每种数据类型hashCode()方法都必须和equals()一致。

等价的（调用equals返回true）对象必须产生相同的散列码。不等价的对象，不要求产生的散列码不相同。

将hashCode()返回值转化为一个数组索引

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

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

自定义hashCode()方法

public class Transaction{
    private final String who;
    private final Date when;
    private final double amount;

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

软缓存

散列值计算很耗时，可以将每个键的散列值缓存起来，即在每个键中使用一个hash变量来保存它的hashCode()返回值。String 对象的 hashCode() 方法就使用了该方法。

基于拉链法的散列表

拉链法使用链表来存储 hash 值相同的键，从而解决冲突。此时查找需要分两步，首先查找 Key 所在的链表，然后在链表中顺序查找。

public class SeparateChainHashST<Key, Value> {
    //键值对总数
    private int N;
    private int M;
    private SequentialSearchST<Key, Value>[] st;
    public SeparateChainHashST() {
        this(997);
    }
    public SeparateChainHashST(int 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;
    }
    private Value get(Key key){
        return st[hash(key)].get(key);
    }
    private void put(Key key,Value val){
        st[hash(key)].put(key,val);
    }
}

基于线性探测法的散列表

用大小为M的数组保存N个键值对，其中M>N，依靠数组中的空位解决碰撞冲突，基于这种策略的所有方法统称为开放地址散列表。

线性探测法：当碰撞发生时，直接检查散列表下一个位置（将索引值加1）。

• 删除时直接置null会使此位置后的元素无法被查找，因此需要将被删除键后的所有键都重新插入。
• 开放地址类的散列表性能依赖于 a=N/M，称 a 为散列表使用率。

public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] vals;
    public LinearProbingHashST() {
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }
    public LinearProbingHashST(int M) {
        this.M = M;
        init(M);
    }
    private void init(int M) {
        keys = (Key[]) new Object[M];
        vals = (Value[]) new Object[M];
    }
    private void resize(int n) {
        LinearProbingHashST<Key, Value> t = new LinearProbingHashST<>(n);
        for (int i = 0; i < M; i++) {
            if (keys[i] != null) {
                t.put(keys[i], vals[i]);
            }
        }
        keys = t.keys;
        vals = t.vals;
        M = t.M;

    }
    private 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;
            }
        }
        keys[i] = key;
        vals[i] = val;
        N++;
    }
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    private Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i + 1) % M) {
            if (keys[i].equals(key)) {
                return vals[i];
            }
        }
        return null;
    }
    private void delete(Key key) {
        if (!contains(key)) {
            return;
        }
        int i;
        for (i = hash(key); !key.equals(keys[i]); i = (i + 1) % M) {
        }

        keys[i] = null;
        vals[i] = null;

        i = (i + 1) % M;
        while (keys[i] != null) {
            Key tmpKey = keys[i];
            Value tmpVal = vals[i];
            keys[i] = null;
            vals[i] = null;
            N--;
            put(tmpKey, tmpVal);
            i = (i + 1) % M;
        }
        N--;
        if (N >= 0 && N <= M / 8) {
            resize(M / 2);
        }
    }
    private boolean contains(Key key) {
        return true;
    }
}

两种方法性能差别主要是因为拉链法为每个键值对都分配了一小块内存而线性探测则为整张表使用了两个很大的数组。

Q&A

1. Java 的Integer/Double/Long类型的hashCode()如何实现？
   Integer 类型会直接返回该整数32位值。对于Double和Long类型，Java会返回值的机器表示的前32位和后32位的异或结果。

2. 当动态调整数组大小时，散列表大小总是2的幂，这样hash()方法就只用了hashCode()的低位。

3. 为什么不将hash(x)实现为x.hashCode() % M？
   散列值必须在0到M-1之间，而Java中取余（%）结果可能为负数。

4. 散列表查找比红黑树更快吗？
   取决于键的类型，这决定了hashCode()计算成本是否大于compareTo()比较成本。对于常见键类型以及Java的默认实现，两者成本近似，因此散列表会比红黑树快很多。

应用

• Java 的 java.util.TreeMap 和 java.util.HashMap 分别是基于红黑树和拉链法的散列表的符号表实现。

• 文件索引（倒排索引）

public class FileIndex {
    public static void main(String[] args) {
        ST<String, SET<File>> st = new ST<>();
        for (String filename : args) {
            File file = new File(filename);
            In in = new In();
            while (!in.isEmpty()) {
                String word = in.readString();
                if (!st.contains(word)) {
                    st.put(word, new SET<File>());
                }
                SET<File> set = st.get(word);
                set.add(file);
            }
        }
        while (!StdIn.isEmpty()) {
            String query = StdIn.readString();
            if (st.contains(query)) {
                for (File file : st.get(query)) {
                    System.out.println("   " + file.getName());
                }
            }
        }
    }
}

• 稀疏向量乘法

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

本篇介绍的算法的完整代码地址：
代码地址