对于查找,往常来说,我们面对的数据并没有如此巨大,但是我们需要经常混合的使用插入和查找的操作
本章将见识到三种经典的数据类型来实现的符号表
二叉查找树 红黑树 散列树
对应各种优缺点如表
本章用于配合查找使用的数据结构为
符号表:
将一个键和一个值联系起来
我们将符号表实现为高级的抽象数据结构,
基本上是Map的抽象
API为
对于这个ST的实现,有如下的要求
对于重复的键,是不允许存在重复的键的
但如果存入的键值对和已有的冲突时,那么新的值代替旧的值
但是不能存在空键
也不能存在空值,一旦为空值,就会删除对应键
删除操作:实现方式两种 延迟删除: 将键对应的值设置为空.然后在某一时间一口气删除所有为空的键
或者即时删除.put(key,null)就是一种延迟删除,
delete也是一种即时删除,
if(val ==null){
delete(key);
return;
}
对应的实现方式中,实现
如果使用有序的数组来进行实现,那么可以提供更多的功能,删除最大的键,最小的键
还有如下的API
如果使用无序链表的实现
则是每次get都需要遍历整个链表,并且equals的方法也是通过遍历实现的
这种方式被我们称为顺序查找,但是基于链表的实现以及顺序查找是很
| public class SequentialSearchST<Key,Value> {
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);//未命中,新建站点 } public int size() { int count=0; for (Node x = first; x!=null;x=x.next) { count++; } return count; } public void delete(Key key) { for (Node x = first; x!=null;x=x.next) { if (x.next.key.equals(key)) {//如果他下面的等于 x.next = x.next.next;//直接删除,jvm自动回收 } } } } |
仓库地址在