Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sets A set can be described as an unordered collection (possibly empty)…

- - - - Dictionary
        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.
        
        Hashing
        
        Hashing: a very efficient way to implement dictionaries. 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. 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
        
        Hash Function:
        -A hash table’s size should not be excessively large compared to the number of keys, but it should be sufficient to not jeopardize the implementation’s time efficiency (see below).
        -A hash function needs to distribute keys among the cells of the hash table as evenly as possible. (This requirement makes it desirable, for most applications, to have a hash function dependent on all bits of a key, not just some of them.)
        -A hash function has to be easy to compute.
        
        Collisions—a phenomenon of two (or more) keys being hashed into the same cell of the hash table
        
        Open Hashing and Close Hashing
        
        Open Hashing: 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.
        
        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. If the hash function distributes n keys among m cells of the hash table about evenly, each list will be about n/m keys long. The ratio α = n/m, called the load factor of the hash table, plays a crucial role in the efficiency of hashing.
        
        Closed Hashing:In closed hashing, 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 occupied, the availability of that cell’s immediate successor is checked, and so on
        
        1 more item...
        
        Double hashing:
        In double hashing, there are two hash functions. The second hash function is used to provide an offset value in case the first function causes a collision.
        With good hashing functions—both primary and secondary—double hashing is superior to linear probing. But its performance also deteriorates when the table gets close to being full. A natural solution in such a situation is rehashing: the current table is scanned, and all its keys are relocated into a larger table.