Please enable JavaScript.
Coggle requires JavaScript to display documents.
Space and Time Trade-Offs, Hashing, Sets and Dictionaries, can be…
Space and Time Trade-Offs
Input enhancement
prestructing
dynamic programming
Hashing
Key
Requirements
Open Hashing
Closed Hashing
Sets and Dictionaries
Sets
Universal set
-->
bit vector
List structure to indicate the set's elements
Dictionary
can be described as an unordered collection (possibly empty) of distinct items called
elements
of the set
can be defined either by an explicit listing of its elements or by specifying a property that all the set's and only they mus satisfy
main operations:
.check membership
.find the union of two sets
.find the intersection of two sets
U = {1,2,3,4,5}
S = {2, 3, 5}
bit vector
= {0, 1, 1, 0, 1}
potentially using a large amount of storage
multiset
or
bag
is an unordered collection of items that allow multiple instances for each of its elements.
can be described as a data structure that implements
searching
,
adding
and
deleting
elements from a
set
or a
multiset
Array
Hashing
Balanced search trees
Set union problem
ADT
to preprocess the problem's input, in whole or in part, and store the additional information obtained to accelerate solving the problema after ward
to use extra space to facilitate faster and/or more flexible access to the data
is a strategy based on recording solutions to overlapping subproblems of a given problem in a table from which a solution to the problem in question is then obtained
data compression
record field that is used for identifying entities represented by the records
is based on the idea of distributing keys among a one-dimensional array called
hash table
hash address
hash function
can't be to large compared to the number of keys, but needs to be sufficient to not jeopardize the time efficiency
It needs to distribute keys among the cell of the
hash table
evenly
It has to be easy to compute
keys are stored in linked lists attached to cells of a hash table
Ratio
α = n/m
is called
load factor
At average case:
searching
,
removing
and
inserting
∈ Θ(1)
all keys are stored in the hash table itself without the use of linked lists
linear probing
: checks the cell following the one where the collision occurs, if that cell is empty, the new key is installed there, if the next cell is already ocupied, it keeps going until it finds an empty cell
cluster
is a sequence of contiguously occupied cells
double hashing
: a strategy to alleviate
clustering
extendible hashing
rehashing
: is an alternative for when the table gets close to being full: the current table is scanned, and all its keys are relocated into a larger table
Hugo de Almeida Medeiros
ham4@cin.ufpe.br