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.

Google Online Preview   Download