Please enable JavaScript.

Coggle requires JavaScript to display documents.

M6 (hashing, Space and Time Trade-Offs, Set, Open hashing, Closed Hashing,…

- - - - 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.
  - - - every hashing scheme
        must have a collision resolution mechanism
- - - - There is one more algorithm design technique related to the space-for-time
        trade-off idea: dynamic programming. This strategy is 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. We discuss this well-developed
        technique separately, in the next chapter of the book.
- - - - There is a commom way for represent a set using a bit vector, called bitset representation. Ex: {1,2,3} and the subset {1,3}, we can represent this subset as a binary string 101.
        
        a set cannot contain identical elements;
        
        The second and more common way to represent a set for computing purposes
        is to use the list structure to indicate the set’s elements.
        
        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
- - - - In general, the efficiency of searching depends on the lengths of the linked
        lists, which, in turn, depend on the dictionary and table sizes, as well as the quality
        of the hash function.
- - - - To search for a given key K, we start by computing h(K) where h is the hash
        function used in the table construction. If the cell h(K) is empty, the search is
        unsuccessful. If the cell is not empty, we must compare K with the cell’s occupant:
        if they are equal, we have found a matching key; if they are not, we compare K
        with a key in the next cell and continue in this manner until we encounter either
        a matching key (a successful search) or an empty cell (unsuccessful search).
        
        Still, as the hash table gets closer to being full, the performance of linear probing
        deteriorates because of a phenomenon called clustering. A cluster in linear
        probing is a sequence of contiguously occupied cells
- - - - Since its discovery in the 1950s by IBM researchers, hashing has found many
        important applications. In particular, it has become a standard technique for storing
        a symbol table—a table of a computer program’s symbols generated during
        compilation