Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets & Dictionaries / Space and Time Trade-Offs - Coggle Diagram
Sets & Dictionaries / Space and Time Trade-Offs
Sets & Dictionaries
Sets
unordered
distinct elements
operations
check membership of item
find union of sets
find intersection of sets
implementations
bit vector
list
Dictionaries
key-value pair
searching, adding and removing
implementations
arrays
hashing
balanced trees
Hash Tables
Distribute keys in a array
H[0...m-1]
proccess
key (K)
hash function
h(K)
hash address
[0...m-1]
Hash table
H
should have size close to n. of keys
Open Hashing (Separate Chaining)
linked-lists
attached to
each hash table cell
avrg efficy for a succesful and unsuccesful search
handles collisions with node linked with collided element at hash cell
load factor
α = n/m
Closed Hashing (Open Adressing)
elements
stored in the table itself
without using linked-lists
handling collisions
linear probing
double hashing
