普里姆算法

普里姆算法（Prim’s algorithm）是图中的一种算法，可在加权连通图中搜索最小生成树。

该算法的作用就是根据图中权值找到连接所有顶点的最短路径，也就是连接所有顶点的最小权值之和，也是这个加权图中的最小生成树。

普里姆算法步骤

1.选取权值最小边的其中一个顶点作为起始点。
2.找到离当前顶点权值最小的边，并记录该顶点为已选择。
3.重复第二步，直到找到所有顶点，就找到了图的最小生成树。

普里姆算法时间复杂度

假如我们有 V 表示图中的顶点个数，E 表示图中的边个数。

通过邻接矩阵图表示的简易实现中，找到所有最小权边共需 O(V^{2}) 的运行时间。

使用简单的二叉堆和邻接表来表示的话，普里姆算法的运行时间则可缩减为 O(E log V )。

如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为 O(E+V log V)，这在连通图足够密集时，可较显著地提高运行速度。

普里姆算法示例

根据上面加权连通图找到最小生成树。

首先选择顶点 A 作为起点。顶点 D、F、B 与 A 相连，且 AD 之间的权值最小，因此选择这条边。此时 A、D 为已选择顶点，E、F、B 为待选择顶点，H、G 为未选择顶点。

下一个顶点应选择离 A、D 权值最小的顶点，因此选择 AB 这条边。此时 A、D、B 为已选择顶点，E、F、G 为待选择顶点，H 为未选择顶点。

下一个顶点应选择离 A、D、B 权值最小的顶点，因此选择 DE 这条边。此时 A、D、B、E 为已选择顶点，F、G、H 为待选择顶点，没有未选择顶点。

下一个顶点应选择离 A、D、B、E 权值最小的顶点，因此选择 EH 这条边。此时 A、D、B、E、H 为已选择顶点，F、G 为待选择顶点，没有未选择顶点。

下一个顶点应选择离 A、D、B、E、H 权值最小的顶点，因此选择 FH 这条边。此时 A、D、B、E、H、F 为已选择顶点，G 为待选择顶点，没有未选择顶点。

最后，只剩下一个顶点 G，到顶点 G 的权值最小的是 HG。现在图中所有顶点都连接了，红色连接的边就是最小生成树，最小生成树的权值之和为 42。

总结

普里姆算法就是通过一个顶点扩散开找权值最小的边，所经过的顶点和边就是这个图的最小生成树。通过不用的数据结构存储图会导致时间复杂度不一致，用邻接矩阵的时间复杂度是 O(V^{2})，二叉堆和邻接表的时间复杂度是 O(E log V )。

图

图 是由顶点的有穷非空集合和顶点之间边的集合组成。

图 是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

线性表中我们把数据元素叫元素，树中将数据元素节点，在图中数据元素，我们则称之为顶点。

线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的节点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

若顶点到顶点之间的边没有方向，则称这条边为 无向边。
若顶点到顶点之间的边有方向，则称这条边为 有向边，也称为 弧。

如果图中任意两个顶点之间的边都是有向边，则称该图为 有向图。
如果图中任意两个顶点之间的边都是无向边，则称该图为 无向图。

在无向图中，如果任意两个顶点之间都存在边，则称该图为 无向完全图。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为 有向完全图。

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为 简单图。

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做 权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为 网。

与该顶点相关联的总边数称为 度。在有向图中，顶点的度还可分为出度和入度。以该顶点为起点的边称为 出度，以该顶点为终点的边称为 入度。

从一个顶点到另一个顶点之间的边序列叫做 路径，路径上的边或弧的数目称为 路径的长度。

第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

无向图中连通且 n 个顶点 n-1 条边叫 生成树。有向图中一顶点入度为 0 其余顶点入度为 1 的叫 有向树。一个有向图由若干棵有向树构成 生成森林。

图的存储

1.邻接矩阵

用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。

在无向图中，顶点到顶点之间有边，就把二维数组里对应的值设为 1，否则设为 0。如果需要知道某个顶点的度，就是邻接矩阵某行元素之和。实际上，无向图的边数组是一个对称矩阵。

从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的称为 对称矩阵。

在有向图中，边是有方向的，根据方向分 入度 和 出度。因此，一个顶点到另一个顶点之间有边时二维数组对应的值设为 1，否则为 0。出度为某行之和，入度为某列之和。

如果在图中每条边带权时，称为 网。比如计算最短路径时，需要用到这个权值，因此需要把对应的权值存储下来。上面二维数组中用 1 和 0 来区分顶点之间是否有边，我们可以把真实的权值存储到对应的二维数组中去，这样就解决来存储权值的问题。

2.邻接表

上面的邻接矩阵看起来是一个存储图不错的方案，但是，当边树比较少的图中，会浪费大量的存储空间。这个时候就可以变二维数组为 一维数组 + 链表 来存储对应的图了，称为邻接表。

图中顶点用一个一维数组存储，每个顶点的所有邻接点在对应一维数组后构成一个线性表，在无向图中称为顶点的边表，在有向图中称为顶点作为弧尾的出边表。

这样用 一维数组 + 链表 来存储图的方式叫做邻接表。

3.十字链表

上面的存储看似很完美，但有向图有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点都建立一个链接顶点为弧头的表。

把邻接表与逆邻接表结合起来的一种存储方法称为 十字链表。

新的顶点表节点结构，分别是 data、firstin、firstout。

data 表示顶点的信息。
firstin 表示入边表头指针，指向该顶点的入边表中第一个节点。
firstout 表示出边表头指针，指向该顶点的出边表中的第一个节点。

新的边表节点结构，分别是 tailvex、headvex、headlink、taillink。

tailvex 是指弧起点在顶点表的下标。
headvex 是指弧终点在顶点表中的下标。
headlink 是指入边表指针域，指向终点相同的下一条边。
taillink 是指边表指针域，指向起点相同的下一条边。
如果是网，还可以再增加一个 weight 域来存储权值。

十字链表的好处就是容易求得顶点的出度和入度。

4.邻接多重表

十字链表是对有向图的优化，可以很容易的求得顶点的出度和入度。
在无向图中，邻接表主要是关注的顶点，如果是要标记或者删除一条边的时候，邻接表的操作就比较麻烦了，这时候就可以参考有向图的优化十字链表了。

新的顶点表节点结构，分别是 data、firstedge。

data 表示顶点的信息。
firstin 表示第一个边表指针，指向该顶点的边表中第一个节点。

新的边表节点结构，分别是 ivex、ilink、jvex、jvex。

ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标。
ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。

这样的结构称为 邻接多重表。邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个节点表示，而在邻接多重表中只有一个节点。

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案：它们是 深度优先遍历 和 广度优先遍历。

1.深度优先遍历

深度优先遍历（Depth First Search），也有称为深度优先搜索，简称为 DFS。

沿着顶点，尽可能深的遍历的分支。当顶点的所在边都己被探寻过，遍历将回溯到发现顶点的那条边的起始顶点。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点并重复以上过程，整个进程反复进行直到所有顶点都被访问为止。

深度优先遍历 就像是树的前序遍历。

2.广度优先遍历

广度优先遍历（Breadth First Search），又称为广度优先搜索，简称BFS。

图的广度优先遍历就类似于树的层序遍历，就是从最上面的顶点，一层一层向下遍历，直到遍历所有的顶点。

总结

图 分为 无向图 和 有向图，与该顶点相关联的总边数称为 度，有向图中又分为 出度 和 入度。

从一个顶点到另一个顶点之间的边序列叫做 路径，路径上的边或弧的数目称为 路径的长度。

存储图的结构主要有 邻接矩阵、邻接表、十字链表 和 邻接多重表。

图的遍历分别为 深度优先遍历 和 广度优先遍历。

1.使用静态工厂方法替代构造方法

静态工厂方法的优点：
不像构造方法，它是有名字的。
它不需要每次调用时都创建一个新对象。
它可以返回 其返回类型的任何子类型的对象。
返回对象的类可以根据输入参数的不同而不同。
在编写包含该方法的类时，返回的对象的类不需要存在。

2.当构造方法参数过多时请使用 builder 模式

当一个对象中，属性过多时，使用构造方法时，参数过多导致难以维护，并且很难读懂每个参数的含义是什么。

使用 构造方法 来构建必传参数，而用 setter 的方式来传可选参数呢？这看似参数少，创建实例也很容易，并且所生成的代码也易于阅读。但由于 JavaBeans 模式本身有严重的缺陷，由于构造方法在多次调用中被分割，导致 JavaBeans 可能处于不一致的状态，并且还需要额外增加工作以确保线程安全。

最好处理参数过多的方法是使用 builder 模式，它结合了可伸缩构造方法模式的安全性和 JavaBeans 模式的可读性，然后在调用 builder 对象的 setter 相似方法来设置每个可选参数。

3.使用依赖注入的方式注入资源

依赖注入的实践将极大地增强类的灵活性、可重用性和可测试性。

4.不要创建不必要的对象

如果对象是不可变的，它总是可以被重用的，比如 String 类是 final 的，不可变的，最好不要用 new String(“test”)， 因为它每次都会创建一个新的对象。在性能有严格要求的情况下，优先使用基本类型而不是装箱的基本类型，也要注意无意识的自动装箱，因为它们会影响性能。

5.消除过期的对象引用

这个也就是常说的内存泄露。当一个类自己管理内存时，应该警惕内存泄漏问题。 每当一个元素被释放时，元素中包含的任何对象引用都应该被清除。

另一个常见的内存泄漏来源是缓存。一旦将对象引用放入缓存中，很容易忘记它的存在，可以用 WeakHashMap 来表示缓存。

6.避免使用 Finalizer 和 Cleaner 机制，请使用 try-with-resources 语句

用于 Finalizer 和 Cleaner 机制的不确定性，我们不知道它到底何时会执行。例如，依赖于 Finalizer 和 Cleaner 机制来关闭文件是严重的错误，因为打开的文件描述符是有限的资源。 如果由于系统迟迟没有运行 Finalizer 和 Cleaner 机制而导致许多文件被打开，程序可能会失败，因为它不能再打开文件了。可以用 try-with-resources 语句 或 try-finally 语句，当打开多个文件时，try-finally 语句的可读性就不如 try-with-resources 语句，因此推荐使用 try-with-resources 语句。

7.重写 equals 方法时同时也要重写 hashcode 方法

重写 equals 方法时，需要满足以下特性。
自反性：一个对象必须与自身相等。
对称性：任何非空引用 x 和 y，如果且仅当 y.equals(x) 返回 true 时 x.equals(y) 必须返回 true。
传递性：如果第一个对象等于第二个对象，第二个对象等于第三个对象，那么第一个对象必须等于第三个对象。
一致性：如果两个对象是相等的，除非一个（或两个）对象被修改了， 那么它们必须始终保持相等。
非空性：对于任何非空引用 x，x.equals(null) 必须返回 false。

每次重写 equals 方法时都必须重写 hashCode 方法，否则程序将无法正常运行。 hashCode 方法必须遵从 Object 类指定的常规约定，将不同的哈希码分配给不同的实例对象。

8.始终重写 toString 方法

Object 类提供了 toString 方法的实现是包名+类名+@+哈希码的无符号十六进制。toString 的通用约定要求，返回的字符串应该是“一个简洁但内容丰富的表示，对人们来说是很容易阅读的”。就需要 toString 方法，方便可读性。

9.考虑实现 Comparable 接口

在需要可比较的场景中，最好实现 Comparable 接口，以便在基于比较的集合中轻松对其实例进行排序，搜索和使用。 比较 compareTo 方法的实现中的字段值时，请避免使用”<”和”>”运算符。 最好使用包装类中的静态 compare 方法或 Comparator 接口中的构建方法。

10.使类和成员的可访问性最小化

一个优秀设计的组件隐藏了它的所有实现细节，干净地将它的 API 与它的实现分离开来。然后，组件只通过它们的 API 进行通信，并且对彼此的内部工作一无所知。称为信息隐藏或封装，是软件设计的基本原则。

Java中的四种访问级别：
private——只能自己访问。
package-private——默认级别，同包中的任意类访问。
protected——子类和自己可以访问。
public —— 任何类都可访问。

11.在公共类中使用访问方法而不是直接访问属性

这种设计不是优秀的设计方式。如果属性直接暴露出去，如果需要修改返回值，那基本是不可能的，因为调用方散布在很多地方。如果是提供的访问方法，我们只需要改方法本身即可。

12.最小化可变性，能用不可变对象最好用不可变对象

不可变对象的优点：
不可变对象是线程安全的。
不可变对象可以被自由地共享。
不可变对象也可以共享内部属性。
不可变对象可以被重复使用。
不可变对象提供了免费的原子失败机制。

13.该选择接口还是抽象类

在 Java 中，通过 接口 和 抽象类 来允许多个实现。在 Java 8 中也引入了接口的默认方法实现，所以这两种机制都允许为某些实例方法提供实现。由于 Java 中只允许单一继承，常用的方式是接口定义了类型，可能提供了一些默认的方法，抽象类去实现多个接口并实现通用接口方法，具体的实现类去继承抽象类并实现抽象类中的抽象方法。

14.该选择组合还是继承

继承是实现代码重用的有效方式，但并不总是最好的工具。与方法调用不同，继承打破了封装，一个子类依赖于其父类的实现细节来保证其正确的功能。如果父类发生了变化，即使子类并没有做任何的改动也会导致子类被破坏。

不要继承一个现有的类，而应该给你的新类增加一个私有属性，该属性是现有类的实例引用，这种设计被称为组合。现在不依赖于现有类的实现细节，即使将新的方法添加到现有的类中，也不会对新类产生影响。

继承是强大的，也可以最大化代码重用，只有在子类和父类之间存在真正的子类型关系时才适用。 如果子类与父类不在同一个包中，并且父类不是为继承而设计的，那就可以使用组合来代替继承。

15.接口最好只用来定义类型

接口不包含任何方法，它只包含静态 final 属性，每个输出一个常量，这样的接口叫常量接口，这是对接口的糟糕使用方式。

如果常量跟类的关系密切，那么我们可以把常量定义在类中。假如是公共的常量，我们应该用枚举类型来定义它们。

接口只能用于定义类型，它们不应该仅用于定义常量。

16.优先考虑使用泛型

一个集合对象中数据类型应该是一致的，如果不规定数据的具体类型，在编译期是没有任何问题的。但到程序运行时，如果类型不一致，就与可能抛出 ClassCastException 异常。因此，我们需要使用泛型强制约束数据的类型，让问题暴露在编译期，而不是在运行期。

17.使用限定通配符来增加 API 的灵活性

我们用泛型强制规定了参数的类型，因此它非常的不灵活，使用场景非常少。相对于提供的不可变的类型，有时需要比此更多的灵活性我们就需要使用通配符类型。

所以将类型从 List 更改为 List<? extends T>。在 API 中使用通配符类型，虽然棘手，但使得 API 更加灵活。 如果编写一个将被广泛使用的类库，请使用通配符类型来最大化该 API 的灵活性。

18.小心泛型和可变参数的结合使用

因为可变参数和泛型不能很友好的限制，泛型可变参数不是类型安全的，但它们是合法的。如果选择使用泛型可变参数编写方法，请首先确保该方法类型一致，然后使用 @SafeVarargs 注解对其进行标注，以免造成使用不愉快。

19.不要为类打标签，而应使用类层次结构

一个类用 枚举声明，标签属性和 switch 语句来判断类型，会使代码可读性更差，容易出错的，而且效率低下。因此，带标签的类很应少最好别用。当遇到一个带有标签属性的现有类时，可以考虑将其重构为一个类层次中。

20.注意消除非检查警告

未经检查的警告是重要的，不要忽视他们。因为每个未经检查的警告代表在运行时出现 ClassCastException 异常的可能性，尽量消除这些警告。如果无法消除未经检查的警告，并且可以证明引发该警告的代码是安全类型的，则可以在尽可能小的范围内使用 @SuppressWarnings(“unchecked”) 注解来禁止警告。 并注释为什么是安全的。

21.该选择列表还是数组

数组和泛型具有非常不同的类型规则。 数组是协变和具体化的， 泛型是不变和类型擦除的。

因此，数组能保证运行时类型的安全性，但不保证编译时类型的安全性，反之亦然。

一般来说，数组和泛型不能很好地混合工作。如果你发现把它们混合在一起，得到编译时错误或者警告，首先应该使用列表来替换数组。

22.使用枚举类型替代整型常量

枚举的优点：
提供了编译时类型的安全性，可以使用 == 运算符来比较不同枚举类型的值。
具有相同名称常量的枚举类型可以和平共存，因为每种类型都有其自己的名称空间。
还允许添加任意方法和属性并实现任意接口，功能更强大。

枚举更具可读性，更安全，更强大。

23.始终使用 Override 注解

此注解只能在方法声明上使用，它表明带此注解的方法声明重写了父类的声明。如果始终使用这个注解，它将避免产生大量的恶意 bug。

如果在每个方法声明中使用 Override 注解，并且认为要重写父类声明，那么编译器可以保护免受很多错误的影响。

24.优先使用标准的函数式接口

java.util.function 包提供了大量标准函数式接口供你使用。 如果其中一个标准函数式接口完成这项工作，则通常应该优先使用它，而不是专门构建的函数式接口。 这将使你的 API 更容易学习，通过减少其不必要概念，并将提供重要的互操作性好处，因为许多标准函数式接口提供了有用的默认方法。

不要提供具有多个重载的方法，这些重载在相同的参数位置上使用不同的函数式接口，如果这样做可能会在调用方中产生歧义。

25.Stream

在 Java 8 中添加了 Stream API，以简化顺序或并行执行批量操作的任务。

流 (Stream)，表示有限或无限的数据元素序列。
流管道 (stream pipeline)，表示对这些元素的多级计算。

Stream 中的元素可以来自任何地方。常见的源包括集合，数组，文件，正则表达式模式匹配器，伪随机数生成器和其他流。

流可以很容易地做一些事情：
统一转换元素序列。
过滤元素序列。
使用单个操作组合元素序列。
将元素序列累积到一个集合中，可能通过一些公共属性将它们分组。
在元素序列中搜索满足某些条件的元素。
遍历元素序列。

Stream 类提供了很多好用又简单的方法，可以多加使用。

堆

堆 是一种特殊的完全二叉树结构，通常，它有两种类型：最小堆 和 最大堆。

最小堆（min heap）是父节点的值恒小于等于子节点的值。

最大堆（max heap）是父节点的值恒大于等于子节点的值。

二叉堆的性质

任意节点小于（或大于）它的所有子节点，最小值（或最大值）在堆的根上。
堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

二叉堆的实现

堆的存储结构

堆一般可以用数组的方式来存储，数组的顺序其实就是堆层级遍历的结果。

堆的插入

由于堆是一个完全二叉树，每次总是先填满上一层，再在下一层从左往右依次插入。

插入步骤：
1.首先将新元素增加到堆的末尾。
2.然后在新元素与其父节点的值比较，如果新元素小于父节点的值则将两者交换位置。
3.不断进行第2步操作，直到不需要交换元素，或者达到堆顶。

最后就会得到一个最小堆，上面交换元素的过程叫做上滤。

堆的删除

堆的删除和插入操作是刚刚相反的，插入是从下往上调整堆，删除是从上往下调整堆。

删除步骤：
1.首先删除堆顶元素。
2.然后在比较左右子节点，将小的元素上调。
3.不断进行步骤2，直到不需要调整或者调整到堆底了。

上面交换元素的过程叫做下滤。

总结

堆有两种类型，最大堆和最小堆，并且堆总是一颗完全树。

由于堆的 父节点的值恒小于等于子节点的值 或者 父节点的值恒大于等于子节点的值，可以作为 Top n 使用。

堆（通常是二叉堆）常用于排序。这种算法称作堆排序。

字典树

字典树，又称 前缀树 或 trie树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

字典树的性质

1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

用字典树结构存储 《JVM JAVA PHP HTML HTTP 》 字符串。

字典树的实现

字典树的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Trie {
    //26 个字母
    private int SIZE = 26;
    //字典树的根
    private TrieNode root;
    //初始化字典树
    Trie() {
        root = new TrieNode();
    }

    //字典树节点
    private class TrieNode {
        //由根至该节点组成的字符串模式出现的次数
        private int num;
        //所有的孩子节点
        private TrieNode[] children;
        //是不是最后一个节点
        private boolean isEnd;
        //节点的值
        private char val;

        TrieNode() {
            num = 1;
            children = new TrieNode[SIZE];
            isEnd = false;
        }
    }
}

字典树的插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//在字典树中插入一个单词
public void insert(String str) {
    //参数校验
    if (str == null || str.length() == 0) {
        return;
    }
    TrieNode node = root;
    char[] letters = str.toCharArray();
    //循环整个单词插入
    for (int i = 0, len = str.length(); i < len; i++) {
        int pos = letters[i] - 'a';
        //假如不存在就新建一个节点
        if (node.children[pos] == null) {
            node.children[pos] = new TrieNode();
            node.children[pos].val = letters[i];
        } else {
            //否则通过这个节点数加一
            node.children[pos].num++;
        }
        node = node.children[pos];
    }
    //最后一个节点
    node.isEnd = true;
}

字典树的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//在字典树中查找一个完全匹配的单词.
public boolean find(String str) {
    //参数校验
    if (str == null || str.length() == 0) {
        return false;
    }
    TrieNode node = root;
    char[] letters = str.toCharArray();
    //循环查找是否存在
    for (int i = 0, len = str.length(); i < len; i++) {
        int pos = letters[i] - 'a';
        if (node.children[pos] != null) {
            node = node.children[pos];
        } else {
            return false;
        }
    }
    return node.isEnd;
}

总结

字典树典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

字典树也常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。