符号表
简介
符号表是一个将键和值联系起来的数据结构。符号表能将一个键值对插入符号根据键查找到相应的值
API
public class ST<Key, Value>
{
ST() // 创建一个符号表
void put(Key key, Value val) // 将键值对加入符号表中
Value get(Key key) // 获取键对应的值
void delete(Key key) // 从表中删除键key
boolean contains(Key key) // 键key时候在表中有对应的值
boolean isEmpty() // 符号表是否为空
int size() // 符号表中的元素数量
Iterable<Key> keys() // 表中所有键的集合
}
特性
- 每个键都对应着一个值（表中不存在重复的键）
- 向表中存入的键值对和已有的键冲突时，新的值会替代旧的值
- 键不能为null
有序符号表
简介
在符号表的基础上，如果键都是Comparable对象，可以保持键的有序性，从而扩展其API
API
public class ST<Key extends Comparable<key>, Value> {
ST() 创建一张符号表
void put(Key key,Value val) 将键值对存入表中（若值为空则将键key从表中删除）
Value get(Key key) 获取键key对应的值（若键key不存在则返回null）
void delete(Key key) 从表中删去键key（及其对应的值）
boolean contains(Key key) 键key在表中是否有对应的值
boolean isEmpty() 表是否为空
int size() 表中的键值对数量
Iterable<Key> keys() 表中的所有键的集合
// 有序符号表额外的api
Key min() 最小的键
Key max() 最大的键
Key floor(Key key) 小于等于key的键的数量
Key ceiling(Key key) 大于等于key的键的数量
int rank(Key key) 等于key的键的数量
Key select(int i) 排位为i的键
void deleteMin() 删除最小的键
void deleteMax() 删除最大的键
int size(Key lo,Key hi) [lo,hi]之间键的数量
Iterable<Key > keys(Key lo,Key hi) [lo,hi]之间所有的键，已排序
Iterable<Key > keys() 有序表中所有的键，已排序
}
符号表的实现
1. 基于无序链表的实现
实现方法
每个节点存储一个键值对，通过遍历链表，使用equals方法对键进行比较。
get方法：如果被查找的键和当前键相同，则返回当前键对应的值。如果链表中的所有键都匹配失败，则返回null。
put方法：如果被查找的键和当前键相同，则用值替换当前键所对应的值，并将原来的值返回。如果链表中的所有键都匹配失败，则创建一个新节点，并插入到链表的开头
基于链表的符号表的索引用例轨迹
代码实现
package edu.princeton.cs.algs4.chapter3;
/**
* 使用无序链表实现的符号表
* 一次查询和插入的平均时间复杂度都是N
* Created by tianxianhu on 2017/3/6.
*/
public class SequentialSearchST<Key, Value> {
private int N;
private Node first;
public SequentialSearchST() {
}
private class Node{
Key key;
Value value;
Node next;
public Node(Key key, Value value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public Value get(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to get() is null");
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
return x.value; // 命中
}
}
return null; // 未命中
}
public void put(Key key, Value value) {
if (key == null)
throw new IllegalArgumentException("first argument to put() is null");
if (value == null) {
delete(key);
return;
}
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) {
x.value = value; // 命中，替换
}
}
first = new Node(key, value, first);// 未命中，新建节点
N++;
}
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
first = delete(first, key);
}
private Node delete(Node x, Key key) {
if (x == null) return null;
if (key.equals(x.key)) {
N--;
return x.next;
}
x.next = delete(x.next, key);
return x;
}
public int size() {
return N;
}
public boolean isEmpty() {
return size() == 0;
}
}
2. 基于有序数组的实现
实现方法
使用一对平行数组，一个存储键，一个存储值
该实现的核心是rank方法，它返回表中小于给定键的键的数量
get方法：如果键存在于表中，使用rank方法返回其在数组中的索引。如果不存在，则返回null。
put方法：使用rank方法查找到该键值所在的数组索引，如果该位置的键就是要插入的键，则更新它的值。如果该位置的值不是要插入的值，则将该值后面所有的值向后移动，然后将此键值对插入到数组当中。
使用基于有序数组的符号表实现的索引用例轨迹
rank方法的实现（二分查找）
// 递归的二分查找
public int rank(Key key, int lo, int hi) {
if (hi < lo)
return lo;
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0)
return rank(key, lo, mid - 1);
else if (cmp > 0)
return rank(key, mid + 1, hi);
else
return mid;
}
// 非递归的二分查找
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)
hi = mid - 1;
else if (cmp > 0)
lo = mid + 1;
else
return mid;
}
return lo;
}
代码实现
package edu.princeton.cs.algs4.chapter3;
/**
* 基于有序数组的符号表
* Created by tianxianhu on 2017/3/6.
*/
public class BinarySearchST <Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Comparable[capacity];
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
public Value get(Key key) {
if (null == key)
throw new IllegalArgumentException("argument to get() is null");
if (isEmpty())
return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0)
return vals[i];
else
return null;
}
private int rank(Key key) {
int lo = 0, hi = N - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0)
hi = mid - 1;
else if (cmp > 0) {
lo = mid + 1;
} else {
return mid;
}
}
return lo;
}
public void put(Key key, Value val) {
if (null == key)
throw new IllegalArgumentException("argument to get() is null");
if (null == val) {
delete(key);
return;
}
int k = rank(key);
// 如果已经存在,进行更新
if (k < N && keys[k].compareTo(key) == 0) {
vals[k] = val;
return;
}
// 不存在，先挪动数组，然后插入
for (int i = N; i > k; i--) {
keys[i] = keys[i - 1];
vals[i] = vals[i - 1];
}
keys[k] = key;
vals[k] = val;
N++;
}
public void delete(Key key) {
if (key == null) throw new IllegalArgumentException("argument to delete() is null");
if (isEmpty()) return;
// compute rank
int i = rank(key);
// key not in table
if (i == N || keys[i].compareTo(key) != 0) {
return;
}
for (int j = i; j < N-1; j++) {
keys[j] = keys[j+1];
vals[j] = vals[j+1];
}
N--;
keys[N] = null; // to avoid loitering
vals[N] = null;
// resize if 1/4 full
if (N > 0 && N == keys.length/4) resize(keys.length/2);
assert check();
}
private boolean check() {
return isSorted() && rankCheck();
}
// are the items in the array in ascending order?
private boolean isSorted() {
for (int i = 1; i < size(); i++)
if (keys[i].compareTo(keys[i-1]) < 0) return false;
return true;
}
// check that rank(select(i)) = i
private boolean rankCheck() {
for (int i = 0; i < size(); i++)
if (i != rank(select(i))) return false;
for (int i = 0; i < size(); i++)
if (keys[i].compareTo(select(rank(keys[i]))) != 0) return false;
return true;
}
public Key select(int k) {
if (k < 0 || k >= size()) {
throw new IllegalArgumentException("called select() with invalid argument: " + k);
}
return keys[k];
}
// resize the underlying arrays
private void resize(int capacity) {
assert capacity >= N;
Key[] tempk = (Key[]) new Comparable[capacity];
Value[] tempv = (Value[]) new Object[capacity];
for (int i = 0; i < N; i++) {
tempk[i] = keys[i];
tempv[i] = vals[i];
}
vals = tempv;
keys = tempk;
}
}
两种符号表实现的比较
简单符号表实现的成本比较
