Please enable JavaScript.

Coggle requires JavaScript to display documents.

Hashing - Coggle Diagram

- - - - Ex: Student’s ID, name, date of birth, sex,
        home address...
- - - - A hash function needs to distribute keys among the cells of the hash table as evenly as possible
      - A hash function has to be easy to compute
      - 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 effifciency
- - - - 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
      - closed hashing
        
        all keys are stored in the hash table itself without the use
        of linked lists
        
        linear probing
        
        A cluster in linear probing is a sequence of contiguously occupied cells
      - double hashing
      - Asymptotic time efficiency
        
        With hashing, searching, insertion, and deletion can be implemented to take BigTheta(1) time on the average but BigTheta(n) in the worst case.
        
        For balanced search trees, the average time efficiencies are BigTheta(log n) for both average and worst cases