符号表

发表于   |   分类于

关于符号表

基本功能

Insert a value with specified key.
Given a key, search for the corresponding value.

应用

DNS lookup

  • Insert domain name with specified IP address.
  • Given domain name, find corresponding IP address

API

Associative array abstraction. Associate one value with each key.

约定

  • Values are not null.
  • Method get() returns null if key not present.
  • Method put() overwrites old value with new value.

Easy to implement contains().

1
2
3
 public boolean contains(Key key) {
    return get(key) != null;
}

Can implement lazy version of delete().

1
2
3
public void delete(Key key) {
    put(key, null);
}

Keys and values

Value type

Any generic type.

Key type

符合以下条件：

最佳实践：Use immutable types for symbol table keys.

  • Immutable in Java: Integer, Double, String, java.io.File, …
  • Mutable in Java: StringBuilder, java.net.URL, arrays, …

Java 中自定义 equals 方法

完整实现：

ST test client for traces

ST test client for analysis

Frequency counter 实现：

基本实现

无序链表方式

数据结构：Maintain an (unordered) linked list of key-value pairs.
搜索：Scan through all keys until find a match.
插入：Scan through all keys until find a match; if no match add to front.

分析

二分搜索

数据结构：Maintain an ordered array of key-value pairs.
Rank helper function：How many keys < k ?

二分搜索 Java 实现

问题：To insert, need to shift all greater keys over.

分析

有序符号表

有序符号表的应用

有序符号表API

分析：