查找算法之——符号表（引入篇）

来源：cnblogs　　作者：脑热　　时间：2018/10/22 16:11:18　　对本文有异议

符号表的主要目的是用来存储键值对，也就是将一个键和一个值关联起来，它的主要操作为插入和查找。

这篇只是为下一篇文章作为抛砖引玉，为不熟悉符号表的朋友做了一个大体的介绍，在文章的结尾列出了符号表的基本操作，有一定了解的朋友可以跳的下一篇文章（二叉查找树）。

首先我们必须讨论几个基本问题，这在之后的思想中将会一直用到：

1、重复的键

符号表不允许出现重复的键，当向表中插入的键值对的键已经出现在标中，当前加入的键值对会覆盖原有的键值对，也就是进行了更新。

2、空键或空值

键不能为空，这在java机制中会产生异常。我们还规定，值也不能为空。（get（）方法能通过查找键返回其关联的值，当键不存在时get（）方法会返回null）

这个规定有两个作用：

第一、我们能判断一个键值对是否存在符号表中。

第二、我们可以将null作为put（）的第二个参数来实现删除操作，

3、删除操作

删除操作的实现有两种思路：即时删除和延时删除，延时删除就是上面提到的，先将其值置位为空，然后在某个时刻删除所有值为空的键。即时删除也就是立即从表中删除指定的键。（本文中将使用即时删除）

4、键的等价性

键可以是任意类型（我们将其设置为泛型），可以是integer，double和string等等，java已经为他们实现了equals（）方法来判断相等，如果是自定义的键，则需要重写equals（）方法。

下面我们进入正题：

一、无序链表中的顺序查找

顾名思义，无序链表就是通常意义上的链表，只是链表的节点被定义为了键值对的形式，无序链表每次插入操作会在头部插入一个新节点，而查找操作是从链表的头部开始一个个地遍历符号表并使用equals（）方法来进行匹配。这种方法的效率是非常低的（它的查找操作是线性级别的），查找第一个键需要1次比较，第二个键需要2次比较...因此平均比较次数为（1+2+...+n）/n =(n+1)/2~n/2。它无法适用于大型符号表。

 1 public class SequentialSearchST<Key, Value> {// 基于无序链表 2     private int n;// number of key-value pairs 3     private Node first; 4  5     private class Node {// 链表节点的定义 6         Key key; 7         Value val; 8         Node next; 9 10         public Node(Key key, Value val, Node next) {11             this.key = key;12             this.val = val;13             this.next = next;14         }15     }16 17     public Value get(Key key) {// 查找给定的键，返回关联的值18         for (Node x = first; x != null; x = x.next) {19             if (key.equals(x.key)) {20                 return x.val;21             }22         }23         return null;24     }25 26     public void put(Key key, Value val) {// 查找给定的键，找到就更新其值，没找到将其插入最前27         // **********************28         if (key == null) {29             throw new IllegalArgumentException("first argument to put() is null");30         }31         if (val == null) {32             delete(key);33             return;34         }35         // *********************防御性代码，这保证了任何键的值都不为空36         for (Node x = first; x != null; x = x.next) {37             if (key.equals(x.key)) {38                 x.val = val;39                 return;40             }41         }42         first = new Node(key, val, first);// 插入最前43         n++;44     }45 }

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

如果能用上二分查找的思想，我们就能把查找的效率提升到对数级别（当然前提是数组有序）

这时插入和查找算法都发生了改变，为了让数组前提有序，插入时我们会用rank（）方法来确定键的位置，再将此位置后的键后移一位，最后插入键。rank（）返回的是键在符号表中排名。在这里如果键存在rank（）将返回键在有序数组中的下标。

在这里我们用两个数组分别存储键值对的键和值，同一键值对在数组中的下标是一样的。

  1 public class BinarySearchST<Key extends Comparable<Key>, Value> {// 有序查找表（基于有序数组）  2     private Key[] keys;  3     private Value[] vals;  4     private int n = 0;// 用于记录符号表中键值对的个数  5   6     public BinarySearchST(int capacity) {// 动态调整大小  7         keys = (Key[]) new Comparable[capacity];  8         vals = (Value[]) new Object[capacity];  9     } 10  11     public boolean contains(Key key) { 12         if (key == null) { 13             throw new IllegalArgumentException("argument to contains is null"); 14         } 15         return get(key) != null; 16     } 17  18     public int size() { 19         return n; 20     } 21  22     public int size(Key lo, Key hi) { 23         if (lo == null) { 24             throw new IllegalArgumentException("first argument to size() is null"); 25         } 26         if (hi == null) { 27             throw new IllegalArgumentException("second argument to size() is null"); 28         } 29         if (lo.compareTo(hi) > 0) { 30             return 0; 31         } 32         if (contains(hi)) { 33             return rank(hi) - rank(lo) + 1; 34         } else { 35             return rank(hi) - rank(lo); 36         } 37     } 38  39     public Key min() { 40         if (isEmpty()) { 41             throw new NoSuchElementException("called min with empty symbol table"); 42         } 43         return keys[0]; 44     } 45  46     public Key max() { 47         if (isEmpty()) { 48             throw new NoSuchElementException("called max with empty symbol table"); 49         } 50         return keys[n - 1]; 51     } 52  53     public Value get(Key key) { 54         if (key == null) { 55             throw new IllegalArgumentException("argument to get is null"); 56         } 57         if (isEmpty()) { 58             return null; 59         } 60         int i = rank(key); 61         if (i < n && keys[i].compareTo(key) == 0) { 62             return vals[i]; 63         } 64         return null; 65     } 66  67     private int rank(Key key) {// 基于有序数组的二分查找（迭代） 68         if (key == null) { 69             throw new IllegalArgumentException("argument to rank is null"); 70         } 71         int lo = 0, hi = n - 1; 72         while (lo <= hi) { 73             int mid = lo + (hi - lo) / 2; 74             int cmp = key.compareTo(keys[mid]); 75             if (cmp > 0) { 76                 lo = mid + 1; 77             } else if (cmp < 0) { 78                 hi = mid - 1; 79             } else { 80                 return mid; 81             } 82         } 83         return lo;// 找不到的情况 84     } 85  86     public Iterable<Key> keys() { 87         return keys(min(), max()); 88     } 89  90     private Iterable<Key> keys(Key lo, Key hi) { 91         if (lo == null) { 92             throw new IllegalArgumentException("first argument to keys() is null"); 93         } 94         if (hi == null) { 95             throw new IllegalArgumentException("second argument to keys() is null"); 96         } 97         Queue<Key> queue = new Queue<Key>(); 98         if (lo.compareTo(hi) > 0) { 99             return queue;100         }101         for (int i = rank(lo); i < rank(hi); i++) {102             queue.enqueue(keys[i]);103         }104         if (contains(hi)) {105             queue.enqueue(keys[rank(hi)]);106             //queue.enqueue(hi);107         }108         return queue;109     }110 111     private boolean isEmpty() {112         // TODO Auto-generated method stub113         return n == 0;114     }115 116     public void put(Key key, Value val) {117         if (key == null) {118             throw new IllegalArgumentException("first argument to put is null");119         }120         if (val == null) {121             delete(key);122             return;123         }124         int i = rank(key);125         if (i < n && key.compareTo(keys[i]) == 0) {//已有元素进行更新126             vals[i] = val;127             return;128         }129         for (int j = n; j > i; j--)  {//键值对后移130             keys[j] = keys[j-1];131             vals[j] = vals[j-1];132         }133         keys[i] = key;134         vals[i] = val;135         n++;136     }137 138     public void delete(Key key) {139         if (key == null) {// 避免空指针错误140             throw new IllegalArgumentException("argument to delete is null");141         }142         if (isEmpty()) {143             return;144         }145         int i = rank(key);146         if (i == n || key.compareTo(keys[i]) != 0) {147             return;148         }149         for (int j = i; j < n - 1; j++) {//元素前移150             keys[j] = keys[j + 1];151             vals[j] = vals[j + 1];152         }153         n--;154         keys[n] = null;155         vals[n] = null;156     }157 }

我们默认使用的二分查找是迭代进行，下面给出递归的形式：

 1     public int rank(Key key,int lo,int hi) { 2         if(hi<lo) { 3             return lo; 4         } 5         int mid=lo+(hi-lo)/2; 6         int cmp=key.compareTo(keys[mid]); 7         if(cmp<0) { 8             return rank(key,lo,mid-1); 9         }else  if(cmp>0) {10             return rank(key,mid+1,hi);11         }else {12             return mid;13         }14     }

如果理解了迭代的形式，就能很容易改写出递归了。

用对象的数组代替两个平行数组（求指点）：

定义一个以键和值为属性的对象，用对象数组来代替两个平行数组，由于本人学术不精，未能完成，主要问题是不知如何创建不同类型属性的泛型数组（key继承了comparable而value继承了object）。在此提出问题，希望高人指点！

 1 public class BSST<Key extends Comparable<Key>, Value> { 2     class Item{//内部类 3         Key key; 4         Value val; 5     } 6     private Item[] item; 7     private int n = 0; 8     public BSST(int capacity) {// 动态调整大小 9         item = (Item[]) new Object[capacity];//出现类型转换错误
10　　　　　//item = (Item[]) new Comparable[capacity];//出现类型转换错误
1112     }13 }