Sets

list of elements

the elements or their property

implemented by a list

cannot contain identical elements

is an ordered collection

Space and Time trade-offs

Methods of Sorting

Input enchancement

Prestructuring

deals w/ access structuring

Hashing

indexing w/ b-trees

Dictionary

A hash table’s size should not be excessively large compared to the number of keys

A hash function needs to distribute keys among the cells of the hash table as evenly as possible.

A hash function has to be easy to compute.

Open Hashng

Closed Hashing

keys in linked lists attached to hash table

all the keys directely linked in the hash table

pre process to wisely store data

counting methods for sorting

boyer-moore algorithm