• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

算法(五)查找

极客笔记 Geekerstar 1年前 (2018-04-11) 298次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

符号表是一种存储键值对的数据结构,主要支持两种操作:插入一个新的键值对、根据给定键得到值。

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

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

二分查找实现有序符号表

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

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

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

public class BinarySearchST, Value> {
    private Key[] keys;
    private Value[] values;
    private int N;

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

    public int size() {
        return N;
    }

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

    public int rank(Key key) {
        int lo = 0, hi = N - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp == 0) return mid;
            else if (cmp < 0) hi = mid - 1;
            else lo = mid + 1;
        }
        return lo;
    }

    public void put(Key key, Value value) {
        int i = rank(key);
        if (i < N && keys[i].compareTo(key) == 0) { values[i] = value; return; } for (int j = N; j > i; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[i] = key;
        values[i] = value;
        N++;
    }

    public Key ceiling(Key key){
        int i = rank(key);
        return keys[i];
    }
}

二叉查找树

二叉树 是一个空链接,或者是一个有左右两个链接的节点,每个链接都指向一颗子二叉树。

**二叉查找树** (BST)是一颗二叉树,并且每个节点的值都大于等于其左子树中的所有节点的值而小于等于右子树的所有节点的值。

BST 有一个重要性质,就是它的中序遍历结果递增排序。

基本数据结构:

public class BST, Value> {
    private Node root;

    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        // 以该节点为根的子树中节点总数
        private int N;

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

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) return 0;
        return x.N;
    }
}

(为了方便绘图,二叉树的空链接不画出来。)

1. get()

– 如果树是空的,则查找未命中;
– 如果被查找的键和根节点的键相等,查找命中;
– 否则递归地在子树中查找:如果被查找的键较小就在左子树中查找,较大就在右子树中查找。

public Value get(Key key) {
    return get(root, key);
}
private Value get(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x.val;
    else if (cmp < 0) return get(x.left, key);
    else return get(x.right, key);
}

2. put()

当插入的键不存在于树中,需要创建一个新节点,并且更新上层节点的链接使得该节点正确链接到树中。

public void put(Key key, Value val) {
    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(x.key);
    if (cmp == 0) x.val = val;
    else if (cmp < 0) x.left = put(x.left, key, val);
    else x.right = put(x.right, key, val);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

3. 分析

二叉查找树的算法运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。最好的情况下树是完全平衡的,每条空链接和根节点的距离都为 logN。

在最坏的情况下,树的高度为 N。

4. floor()

floor(key):小于等于键的最大键

– 如果键小于根节点的键,那么 floor(key) 一定在左子树中;
– 如果键大于根节点的键,需要先判断右子树中是否存在 floor(key),如果存在就找到,否则根节点就是 floor(key)。

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) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) {
        return t;
    } else {
        return x;
    }
}

5. rank()

rank(key) 返回 key 的排名。

– 如果键和根节点的键相等,返回左子树的节点数;
– 如果小于,递归计算在左子树中的排名;
– 如果大于,递归计算在右子树中的排名,并加上左子树的节点数,再加上 1(根节点)。

public int rank(Key key) {
    return rank(key, root);
}
private int rank(Key key, Node x) {
    if (x == null) return 0;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return size(x.left);
    else if (cmp < 0) return rank(key, x.left);
    else return 1 + size(x.left) + rank(key, x.right);
}

6. min()

private Node min(Node x) {
    if (x == null) return null;
    if (x.left == null) return x;
    return min(x.left);
}

7. deleteMin()

令指向最小节点的链接指向最小节点的右子树。

public void deleteMin() {
    root = deleteMin(root);
}
public 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;
}

8. delete()

– 如果待删除的节点只有一个子树,那么只需要让指向待删除节点的链接指向唯一的子树即可;
– 否则,让右子树的最小节点替换该节点。

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.left = delete(x.left, key); else if (cmp > 0) x.right = delete(x.right, 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;
}

9. keys()

利用二叉查找树中序遍历的结果为递增的特点。

public Iterable keys(Key lo, Key hi) {
    Queue queue = new LinkedList<>();
    keys(root, queue, lo, hi);
    return queue;
}
private void keys(Node x, Queue queue, Key lo, Key hi) {
    if (x == null) return;
    int cmpLo = lo.compareTo(x.key);
    int cmpHi = hi.compareTo(x.key);
    if (cmpLo < 0) keys(x.left, queue, lo, hi);
    if (cmpLo <= 0 && cmpHi >= 0) queue.add(x.key);
    if (cmpHi > 0) keys(x.right, queue, lo, hi);
}

10. 性能分析

复杂度:二叉查找树所有操作在最坏的情况下所需要的时间都和树的高度成正比。

2-3 查找树

2-3 查找树引入了 2- 节点和 3- 节点,目的是为了让树平衡。一颗完美平衡的 2-3 查找树的所有空链接到根节点的距离应该是相同的。

1. 插入操作

插入操作和 BST 的插入操作有很大区别,BST 的插入操作是先进行一次未命中的查找,然后再将节点插入到对应的空链接上。但是 2-3 查找树如果也这么做的话,那么就会破坏了平衡性。它是将新节点插入到叶子节点上。

根据叶子节点的类型不同,有不同的处理方式。

插入到 2- 节点上,那么直接将新节点和原来的节点组成 3- 节点即可。

如果是插入到 3- 节点上,就会产生一个临时 4- 节点时,需要将 4- 节点分裂成 3 个 2- 节点,并将中间的 2- 节点移到上层节点中。如果上移操作继续产生临时 4- 节点则一直进行分裂上移,直到不存在临时 4- 节点。

2. 性质

2-3 查找树插入操作的变换都是局部的,除了相关的节点和链接之外不必修改或者检查树的其它部分,而这些局部变换不会影响树的全局有序性和平衡性。

2-3 查找树的查找和插入操作复杂度和插入顺序无关,在最坏的情况下查找和插入操作访问的节点必然不超过 logN 个,含有 10 亿个节点的 2-3 查找树最多只需要访问 30 个节点就能进行任意的查找和插入操作。

红黑二叉查找树

2-3 查找树需要用到 2- 节点和 3- 节点,红黑树使用红链接来实现 3- 节点。指向一个节点的链接颜色如果为红色,那么这个节点和上层节点表示的是一个 3- 节点,而黑色则是普通链接。

红黑树具有以下性质:

1. 红链接都为左链接;
2. 完美黑色平衡,即任意空链接到根节点的路径上的黑链接数量相同。

画红黑树时可以将红链接画平。

public class RedBlackBST, Value> {
    private Node root;
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        Key key;
        Value val;
        Node left, right;
        int N;
        boolean color;

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

    private boolean isRed(Node x) {
        if (x == null) return false;
        return x.color == RED;
    }
}

1. 左旋转

因为合法的红链接都为左链接,如果出现右链接为红链接,那么就需要进行左旋转操作。

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

2. 右旋转

进行右旋转是为了转换两个连续的左红链接,这会在之后的插入过程中探讨。

public Node rotateRight(Node h) {
    Node x = h.left;
    h.left = x.right;
    x.color = h.color;
    h.color = RED;
    x.N = h.N;
    h.N = 1 + size(h.left) + size(h.right);
    return x;
}

3. 颜色转换

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

void flipColors(Node h){
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

4. 插入

先将一个节点按二叉查找树的方法插入到正确位置,然后再进行如下颜色操作:

– 如果右子节点是红色的而左子节点是黑色的,进行左旋转;
– 如果左子节点是红色的,而且左子节点的左子节点也是红色的,进行右旋转;
– 如果左右子节点均为红色的,进行颜色转换。

public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
}

private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val, 1, RED);
    int cmp = key.compareTo(x.key);
    if (cmp == 0) x.val = val;
    else if (cmp < 0) x.left = put(x.left, key, val);
    else x.right = put(x.right, key, val);

    if (isRed(x.right) && !isRed(x.left)) x = rotateLeft(x);
    if (isRed(x.left) && isRed(x.left.left)) x = rotateRight(x);
    if (isRed(x.left) && isRed(x.right)) flipColors(x);

    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

可以看到该插入操作和二叉查找树的插入操作类似,只是在最后加入了旋转和颜色变换操作即可。

根节点一定为黑色,因为根节点没有上层节点,也就没有上层节点的左链接指向根节点。flipColors() 有可能会使得根节点的颜色变为红色,每当根节点由红色变成黑色时树的黑链接高度加 1.

5. 分析

一颗大小为 N 的红黑树的高度不会超过 2logN。最坏的情况下是它所对应的 2-3 树,构成最左边的路径节点全部都是 3- 节点而其余都是 2- 节点。

红黑树大多数的操作所需要的时间都是对数级别的。

散列表

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

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

1. 散列函数

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

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

散列函数应该满足以下三个条件:

1. 一致性:相等的键应当有相等的 hash 值,两个键相等表示调用 equals() 返回的值相等。
2. 高效性:计算应当简便,有必要的话可以把 hash 值缓存起来,在调用 hash 函数时直接返回。
3. 均匀性:所有键的 hash 值应当均匀地分布到 [0, M-1] 之间,这个条件至关重要,直接影响到散列表的性能。

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

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

对于有多部分组合的键,每部分都需要计算 hash 值,并且最后合并时需要让每部分 hash 值都具有同等重要的地位。可以将该键看成 R 进制的整数,键中每部分都具有不同的权值。

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

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

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

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

R 通常取 31。

Java 中的 hashCode() 实现了 hash 函数,但是默认使用对象的内存地址值。在使用 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 int hashCode(){
        int hash = 17;
        hash = 31 * hash + who.hashCode();
        hash = 31 * hash + when.hashCode();
        hash = 31 * hash + ((Double) amount).hashCode();
        return hash;
    }
}

2. 基于拉链法的散列表

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

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

3. 基于线性探测法的散列表

线性探测法使用空位来解决冲突,当冲突发生时,向前探测一个空位来存储冲突的键。使用线程探测法,数组的大小 M 应当大于键的个数 N(M>N)。

public class LinearProbingHashST<Key, Value> {
    private int N;
    private int M = 16;
    private Key[] keys;
    private Value[] vals;

    public LinearProbingHashST() {
        init();
    }

    public LinearProbingHashST(int M) {
        this.M = M;
        init();
    }

    private void init() {
        keys = (Key[]) new Object[M];
        vals = (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 vals[i];
        }
    }
    return null;
}

(二)插入

public void put(Key key, Value val) {
    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++;
    resize();
}

(三)删除

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

public void delete(Key key) {
    if (!contains(key)) return;
    int i = hash(key);
    while (!key.equals(keys[i])) {
        i = (i + 1) % M;
    }
    keys[i] = null;
    vals[i] = null;
    i = (i + 1) % M;
    while (keys[i] != null) {
        Key keyToRedo = keys[i];
        Value valToRedo = vals[i];
        keys[i] = null;
        vals[i] = null;
        N--;
        put(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<>(cap);
    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;
}

应用

1. 各种符号表实现的比较

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

2. Java 的符号表实现

– java.util.TreeMap:红黑树
– java.util.HashMap:拉链法的散列表

3. 集合类型

除了符号表,集合类型也经常使用,它只有键没有值,可以用集合类型来存储一系列的键然后判断一个键是否在集合中。

4. 稀疏向量乘法

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

符号表是一种存储键值对的数据结构,主要支持两种操作:插入一个新的键值对、根据给定键得到值。

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

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

参考资料

– Sedgewick, Robert, and Kevin Wayne. _Algorithms_. Addison-Wesley Professional, 2011.


丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:算法(五)查找
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00