Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets, Hashing, Space and Time Trade-Offs, (In somewhat more general terms,…
Sets
Implemetation
1º- considers only sets that are subsets of some large set U, called the universal set. If set U has n elements, then any subset S of U can be represented by a bit string of size n, called a bit vector.
-
-
-
A set can be described as
an unordered collection (possibly empty) of distinct items called elements of the set.
-
-
Hashing
-
is based on the idea of distributing keys among a one-dimensional
array H[0..m − 1] called a hash table.
The distribution is done by computing, for
each of the keys, the value of some predefined function h called the hash function.
This function assigns an integer between 0 and m − 1, called the hash address, to
a key.
-
In somewhat more general terms, the idea is to preprocess the problem’s input, in whole or in part, and store the additional information obtained to accelerate solving the problem afterward.