Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sets and Dictionaries, Hashing, Space and time trade-offs - Coggle Diagram
Sets and Dictionaries
Sets
A set can be described as an unordered collection (possibly empty) of distinct items called elements of the set
A specific set is defined either by an explicit listing of its elements (e.g., S = {2, 3, 5, 7}) or by specifying a property that all the set’s elements and only they must satisfy (e.g., S = {n: n is a prime number smaller than 10})
The most important set operations are: checking membership of a given item in a given set; finding the union of two sets, which comprises all the elements in either or both of them; and finding the intersection of two sets, which comprises all the common elements in the sets.
-
-
Dictionary
A data structure that implements the operations of search for a given item, add a new item and delete an item from the collection
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
-
-
-
-