算法红皮书第四版读书笔记（三）查找

布满荆棘的人生 2023-07-13 15:10 14阅读 0赞

>  现代计算机和网络使我们能够访问海量的信息。高效检索这些信息的能力是处理它们的重要前提。本章描述的都是数十年来在广泛应用中经过实践检验的***经典查找算法***。

***符号表：*** 我们会使用 符号表 这个词来描述一张***抽象的表格***，我们会将信息（ 值）存储在其中，然后按照指定的 键 来搜索并获取这些信息。

***符号表*** 有时被称为 ***字典*** ，类似于那本将单词的释义按照字母顺序排列起来的历史悠久的参考书。 在英语字典里，键就是单词，值就是单词对应的定义、发音和词源。 ***符号表*** 有时又叫做 ***索引*** ，即书本最后将术语按照字母顺序列出以方便查找的那部分

### 一、符号表 ###

1、符号表最主要的目的就是将一个 键 和一个 值 联系起来

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70][]

> 我们的所有实现都遵循以下规则： 
> 
> 每个键只对应着一个值（表中不允许存在重复的键）； 
> 
> 当用例代码向表中存入的键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值。
> 
>

2、空键

不允许有空键

3、空（null）值

规定不允许有空值。

> 第一，我们可以用 get() 方法是否返回空来测试给定的***键是否存在***于符号表中；
> 
> 第二，我们可以将***空值作为 put() 方法***的第二个参数存入表中来***实现删除***，
> 
>

4、删除操作

在符号表中，

> ***延时删除*** ： 也就是将键对应的值置为空，然后在某个时候删去所有值为空的键；
> 
> ***即时删除： *** 也就是立刻从表中删除指定的键。
> 
>

put(key, null)  是  delete(key)  的一种简单的（ ***延时型*** ）实现。

而实现（即时型）delete() 就是为了替代这种默认的方案。在我们的符号表实现中不会使用默认的方案，而在本书的网站上

put() 实现的开头有这样一句防御性代码：

> ***if (val == null) \{ delete(key); return; \}*** 
> 
>

这保证了符号表中任何键的值都不为空。为了节省版面我们没有在本书中附上这段代码（我们也不会在调用  put()  时使用  null ）。

5、**无序链表中**的顺序查找

> 符号表中使用的数据结构的一个简单选择是链表，每个节点存储一个键值对
> 
> get() 的实现即为遍历链表，用equals() 方法比较需被查找的键和每个节点中的键
> 
> 如果匹配成功我们就返回相应的值，否则我们返回null

> put() 的实现也是***遍历链表***，用equals() 方法比较需被查找的键和每个节点中的键
> 
> 如果匹配成功我们就用第二个参数指定的值更新和该键想相关的值，否则我们就用给定的键值对创建一个新的节点并将其插入到链表的开头，这种方法也被称为 ***顺序查找***

public class SequentialSearchST {
    
        //    链表首节点
        private Node first;
    
        private class Node {
            //    链表节点的定义
            Key key;
            Value val;
            Node next;
    
            public Node(Key key, Value val, Node next) {
                this.key = key;
                this.val = val;
                this.next = next;
            }
        }
    
        public Value get(Key key) {
            //    查找给定的值，返回相关联的值
            for (Node x = first; x != null; x = x.next) {
                if (key.equals(x.key)) {
                    //    命中
                    return x.val;
                }
            }
            //    未命中
            return null;
        }
    
        public void put(Key key, Value val) {
            //    查找给定的键，找到则更新其值，否则在表中新建节点
            for (Node x = first; x != null; x = x.next) {
                if (key.equals(x.key)) {
                    x.val = val;
                    return;
                }
            }
            //    未命中，新建节点
            first = new Node(key, val, first);
        }
    }

> 符号表的实现使用了一个私有内部Node类来在链表中保存键和值。
> 
> get() 的实现会顺序的搜索链表查找给定的键（找到则返回相关联的值）
> 
> put() 的实现也会顺序的搜索链表查找给定的键，如果找到则更新相关联的值，否则它会用给定的键值对创建一个新的结点并将其插入到链表的开头

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1][]

> ***随机命中：***  查找一个***已经存在的键***并不需要线性级别的时间。一种度量方法是查找表中的每个键，并将总时间除以  *N*。在查找表中的每个键的可能性都相同的情况下时，这个结果就是一次查找平均所需的比较数。我们将它称为 随机命中 。
> 
>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2][]

6、***有序数组***中的***二分查找***

> 使用的***数据结构是一堆平行的数组***，一个存储键一个存储值
> 
> 实现的***核心是rank() 方法***，发挥表中小于给定键的键的数量。
> 
> 对于get() 方法，只要给定的键存在于表中，rank（）就能准确的告诉我们在哪里找到它（如果找不到，那就不在表中）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3][]

***对二分查找的分析***

> rank() 的递归实现还能够让我们立即得到一个结论：
> 
>  
> 
> 二分查找很快，因为递归关系可以说明算法所需比较次数的上界。
> 
>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 5][]

> 核心的问题在于我们能否找到能够同时保证 ***查找和插入操作*** 都是 ***对数级别*** 的算法和数据结构
> 
>

***单链接的链表是无法使用二分查找法的*** ，因为 ***二分查找的高效*** 来自于能够快速 ***通过索引取得任何子数组的中间元素*** （但得到一条链表的中间元素的唯一方法只能是沿链表遍历）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 6][]

> [总结：][Link 1]
> 
> [1）数组便于查询和修改（顺序线性），但是不方便新增和删除][Link 1]
> 
> [2）链表适合新增和删除（指针），但是不适合查询，根据业务情况使用合适的数据结构和算法是在大数据量和高并发时必须要考虑的问题][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70]: /images/20230529/746c662cfe42449ebe4db97a2f976d68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1]: /images/20230529/355c2772203e4b58bff81673161d60e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2]: /images/20230529/2bce6cdf61c049218004830674f82f53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3]: /images/20230529/addae0f6b23d4cd0a27c277cdea54a62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4]: /images/20230529/2e7eeb824c084e3490c4f2a9deab4a17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 5]: /images/20230529/5512e07debca40ec80447d8de201395b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 6]: /images/20230529/3667b2b16d50443180da8ed98ee938d8.png
[Link 1]: https://blog.csdn.net/qq_35275233/article/details/104850883