符號(hào)表
簡介
符號(hào)表是一個(gè)將鍵和值聯(lián)系起來的數(shù)據(jù)結(jié)構(gòu)逐抑。符號(hào)表能將一個(gè)鍵值對插入符號(hào)根據(jù)鍵查找到相應(yīng)的值
API
public class ST<Key, Value>
{
ST() // 創(chuàng)建一個(gè)符號(hào)表
void put(Key key, Value val) // 將鍵值對加入符號(hào)表中
Value get(Key key) // 獲取鍵對應(yīng)的值
void delete(Key key) // 從表中刪除鍵key
boolean contains(Key key) // 鍵key時(shí)候在表中有對應(yīng)的值
boolean isEmpty() // 符號(hào)表是否為空
int size() // 符號(hào)表中的元素?cái)?shù)量
Iterable<Key> keys() // 表中所有鍵的集合
}
特性
- 每個(gè)鍵都對應(yīng)著一個(gè)值（表中不存在重復(fù)的鍵）
- 向表中存入的鍵值對和已有的鍵沖突時(shí)枪向，新的值會(huì)替代舊的值
- 鍵不能為null
有序符號(hào)表
簡介
在符號(hào)表的基礎(chǔ)上卿泽，如果鍵都是Comparable對象伊约，可以保持鍵的有序性，從而擴(kuò)展其API
API
public class ST<Key extends Comparable<key>, Value> {
ST() 創(chuàng)建一張符號(hào)表
void put(Key key,Value val) 將鍵值對存入表中（若值為空則將鍵key從表中刪除）
Value get(Key key) 獲取鍵key對應(yīng)的值（若鍵key不存在則返回null）
void delete(Key key) 從表中刪去鍵key（及其對應(yīng)的值）
boolean contains(Key key) 鍵key在表中是否有對應(yīng)的值
boolean isEmpty() 表是否為空
int size() 表中的鍵值對數(shù)量
Iterable<Key> keys() 表中的所有鍵的集合
// 有序符號(hào)表額外的api
Key min() 最小的鍵
Key max() 最大的鍵
Key floor(Key key) 小于等于key的鍵的數(shù)量
Key ceiling(Key key) 大于等于key的鍵的數(shù)量
int rank(Key key) 等于key的鍵的數(shù)量
Key select(int i) 排位為i的鍵
void deleteMin() 刪除最小的鍵
void deleteMax() 刪除最大的鍵
int size(Key lo,Key hi) [lo,hi]之間鍵的數(shù)量
Iterable<Key > keys(Key lo,Key hi) [lo,hi]之間所有的鍵彻消，已排序
Iterable<Key > keys() 有序表中所有的鍵涤浇，已排序
}
符號(hào)表的實(shí)現(xiàn)
1. 基于無序鏈表的實(shí)現(xiàn)
實(shí)現(xiàn)方法
每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)鍵值對，通過遍歷鏈表例朱，使用equals方法對鍵進(jìn)行比較孝情。
get方法：如果被查找的鍵和當(dāng)前鍵相同鱼蝉，則返回當(dāng)前鍵對應(yīng)的值。如果鏈表中的所有鍵都匹配失敗箫荡，則返回null魁亦。
put方法：如果被查找的鍵和當(dāng)前鍵相同，則用值替換當(dāng)前鍵所對應(yīng)的值菲茬，并將原來的值返回吉挣。如果鏈表中的所有鍵都匹配失敗，則創(chuàng)建一個(gè)新節(jié)點(diǎn)婉弹，并插入到鏈表的開頭
基于鏈表的符號(hào)表的索引用例軌跡
代碼實(shí)現(xiàn)
package edu.princeton.cs.algs4.chapter3;
/**
* 使用無序鏈表實(shí)現(xiàn)的符號(hào)表
* 一次查詢和插入的平均時(shí)間復(fù)雜度都是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);// 未命中，新建節(jié)點(diǎn)
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. 基于有序數(shù)組的實(shí)現(xiàn)
實(shí)現(xiàn)方法
使用一對平行數(shù)組镀赌，一個(gè)存儲(chǔ)鍵氯哮，一個(gè)存儲(chǔ)值
該實(shí)現(xiàn)的核心是rank方法，它返回表中小于給定鍵的鍵的數(shù)量
get方法：如果鍵存在于表中商佛，使用rank方法返回其在數(shù)組中的索引喉钢。如果不存在，則返回null良姆。
put方法：使用rank方法查找到該鍵值所在的數(shù)組索引肠虽，如果該位置的鍵就是要插入的鍵，則更新它的值玛追。如果該位置的值不是要插入的值税课，則將該值后面所有的值向后移動(dòng)，然后將此鍵值對插入到數(shù)組當(dāng)中痊剖。
使用基于有序數(shù)組的符號(hào)表實(shí)現(xiàn)的索引用例軌跡
rank方法的實(shí)現(xiàn)（二分查找）
// 遞歸的二分查找
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;
}
代碼實(shí)現(xiàn)
package edu.princeton.cs.algs4.chapter3;
/**
* 基于有序數(shù)組的符號(hào)表
* 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);
// 如果已經(jīng)存在,進(jìn)行更新
if (k < N && keys[k].compareTo(key) == 0) {
vals[k] = val;
return;
}
// 不存在韩玩，先挪動(dòng)數(shù)組，然后插入
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;
}
}
兩種符號(hào)表實(shí)現(xiàn)的比較
簡單符號(hào)表實(shí)現(xiàn)的成本比較
