Symbol Table Flashcards Preview

Algorithms and Data Structures > Symbol Table > Flashcards

Flashcards in Symbol Table Deck (18)
Loading flashcards...
1
Q

what is the pair of things that a symbol table is made up of

A

key

value

2
Q

why can keys not be allowed to be null

A

because get() will return null if the key isn’t present

3
Q

should keys be changed once they’ve entered the abstract data type

A

no

4
Q

basic methods that should be included in a basic symbol table APi

A
void put(key key, value val)
value get(key key)
boolean contains(key key)
void delete(key key)
boolean isEmpty()
int size()
5
Q

what types can keys and values be

A

any generic type so long as they are comparable

6
Q

what three requirements make up equivalence relation

A

reflexive
symmetric
transistive

7
Q

what does it mean if two objects are reflexive

A

x.equals(x) is true

8
Q

what does it mean if two objects are symmetric

A

x.equals(y) iff y.equals(x)

9
Q

what does iff mean

A

if and only if

10
Q

what does it mean if two objects are transistive

A

if x.equals(y) and y.equals(z) then x.equals(z)

11
Q

what does it mean for an object to be non null

A

x.equals(null) is false

12
Q

default equality test in java

A

x == y

13
Q

why is the deafault equality test not the optimal way to compare

A

compares references to objects, returns true if both variables point to the same object, otherwise false

This may not always be what we are seeking

14
Q

How to speed up big compares

A

compare fields most likely to differ first

eg in dates, compare days before years

15
Q

standard recipe for user-defined compare methods

A

reference equality?
check against null?
check that they are of the same type and cast?

16
Q

additional methods that can be found in an ordered symbol table

A
min
max
floor(key)
ceiling(key)
rank(key)
select(key)
deleteMin()
deleteMax()
17
Q

what does ceiling return

A

smallest key greater than or equal to the passed key

18
Q

what does floor return

A

the largest key less than or equal to the key passed