3.1 SYMBOL TABLES - Princeton University
[Pages:26]Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
Algorithms FOURTH EDITION
ROBERT SEDGEWICK | KEVIN WAYNE
3.1 SYMBOL TABLES
API elementary implementations ordered operations
Algorithms
ROBERT SEDGEWICK | KEVIN WAYNE
3.1 SYMBOL TABLES
API elementary implementations ordered operations
Symbol tables
Key-value pair abstraction.
Insert a value with specified key. Given a key, search for the corresponding value.
Ex. DNS lookup.
Insert domain name with specified IP address. Given domain name, find corresponding IP address.
domain name cs.princeton.edu
princeton.edu yale.edu
harvard.edu
IP address 128.112.136.11 128.112.128.15 130.132.143.21 128.103.060.55 209.052.165.60
key
value
3
Symbol table applications
application
purpose of search
key
value
dictionary book index file share financial account web search
compiler routing table
DNS reverse DNS
genomics file system
find definition find relevant pages find song to download process transactions find relevant web pages find properties of variables route Internet packets
find IP address find domain name
find markers find file on disk
word term name of song account number keyword variable name destination domain name IP address DNA string filename
definition list of page numbers
computer ID transaction details list of page names
type and value best route IP address
domain name known positions location on disk
4
Symbol tables: context
Also known as: maps, dictionaries, associative arrays.
Generalizes arrays. Keys need not be between 0 and N ? 1.
Language support.
External libraries: C, VisualBasic, Standard ML, bash, ... Built-in libraries: Java, C#, C++, Scala, ... Built-in to language: Awk, Perl, PHP, Tcl, JavaScript, Python, Ruby, Lua.
every array is an associative array
every object is an associative array
table is the only primitive data structure
hasNiceSyntaxForAssociativeArrays["Python"] = true hasNiceSyntaxForAssociativeArrays["Java"] = false
legal Python code
5
Basic symbol table API
Associative array abstraction. Associate one value with each key.
public class ST
ST()
create an empty symbol table
void put(Key key, Value val)
put key-value pair into the table
Value get(Key key)
value paired with key
boolean contains(Key key)
is there a value paired with key?
void delete(Key key)
remove key (and its value) from table
boolean isEmpty()
is the table empty?
int size()
number of key-value pairs in the table
Iterable keys()
all the keys in the table
a[key] = val; a[key]
6
Conventions
Values are not null.
Java allows null value
Method get() returns null if key not present.
Method put() overwrites old value with new value.
Intended consequences.
Easy to implement contains().
public boolean contains(Key key) { return get(key) != null; }
Can implement lazy version of delete().
public void delete(Key key) { put(key, null); }
7
Keys and values
Value type. Any generic type.
specify Comparable in API.
Key type: several natural assumptions.
Assume keys are Comparable, use compareTo(). Assume keys are any generic type, use equals() to test equality. Assume keys are any generic type, use equals() to test equality;
use hashCode() to scramble key.
built-in to Java (stay tuned)
Best practices. Use immutable types for symbol table keys.
Immutable in Java: Integer, Double, String, java.io.File, ... Mutable in Java: StringBuilder, .URL, arrays, ...
8
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- recipe 1 1 creating a custom symbol
- symbol table generator
- drafting symbols g w learning
- 3 1 symbol tables princeton university
- pcb artist library creation tutorial
- pi world 2020 lab microsoft
- 3 creating and editing symbols miami dade county
- virtuoso schematic composer tutorial department of
- system programming lab kct college of engineering
- abstract syntax trees and symbol tables wellesley college