Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sets and Dictionaries + Space and Time Trade-Offs - Coggle Diagram

- - - - This requirement for uniqueness is sometimes circumvented by the
        introduction of a multiset, or bag, an unordered collection of items that are not
        necessarily distinct. Second, a set is an unordered collection of items; therefore,
        changing the order of its elements does not change the set. A list, defined as an
        ordered collection of items, is exactly the opposite
        
        In computing, the operations we need to perform for a set or a multiset most
        often are searching for a given item, adding a new item, and deleting an item
        from the collection. A data structure that implements these three operations is
        called the dictionary
- - - - Recall
        that a dictionary is an abstract data type, namely, a set with the operations of
        searching (lookup), insertion, and deletion defined on its elements. The elements
        of this set can be of an arbitrary nature: numbers, characters of some alphabet,
        character strings, and so on
      - Typically, records comprise several fields, each responsible for keeping a
        particular type of information about an entity the record represents. For example,
        a student record may contain fields for the student’s ID, name, date of birth, sex,
        home address, major, and so on. Among record fields there is usually at least one
        called a key that is used for identifying entities represented by the records (e.g.,
        the student’s ID).
      - 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
        
        Open Hashing (Separate Chaining)
        
        In open hashing, keys are stored in linked lists attached to cells of a hash table.
        Each list contains all the keys hashed to its cell. Consider, as an example, the
        following list of words:
        A, FOOL, AND, HIS, MONEY, ARE, SOON, PARTED.
        As a hash function, we will use the simple function for strings mentioned above,
        i.e., we will add the positions of a word’s letters in the alphabet and compute the
        sum’s remainder after division by 13.
        
        Closed Hashing (Open Addressing)
        
        all keys are stored in the hash table itself without the use
        of linked lists. (Of course, this implies that the table size m must be at least as
        large as the number of keys n.) Different strategies can be employed for collision
        resolution. The simplest one—called linear probing—checks the cell following
        the one where the collision occurs