Please enable JavaScript.

Coggle requires JavaScript to display documents.

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

- - - - Very time efficient, but potentially large space needed
    - - Can, unlike sets, contain repeated elements
      - Most of the time won't technically need to be ordered
        
        Solution: multisets/bags
- - - - A has 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
      - A hash function needs to distribute keys among the cells of the has table as evenly as possible
      - Has to be easy to computer
    - - n keys are stored in linked lists attached to m cells of a hash table.
        
        Each list contains all the keys hashed to its cell.
      - To add an element to a hash table, the hash function is used to determine the position the element will be attached to.
      - To find an element in a hash table, the same procedure that was used for creating the table is applied to a search key.
      - The efficiency 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.
        
        Being α = n/m (called the load factor) and considering that the hash function used is distributing elements evenly throughout the hash table:
        
        Ideal: load factor of about 1
        
        The average number of pointers (chain links) inspected in successful searches is:
        S ≈ 1 + α/2
        
        And for unsuccessful searches:
        U = α
        
        With α ≈ 1, the efficiency of insertion, deletion and insertion are all Θ(1) in the average case.
    - - Doesn't use linked lists
      - Linear probing: checks the cell following the one where the collision occurs until there's one free. If the end is reached, the hash table is treated as a circular array.
      - Clustering: when there are more filled spots on the hash table, the performance of linear probing deteriorates.
      - Double hashing: implement a second function to be used if there's a collision.
        
        Hard mathematical analysis
        
        Performance also deteriorates when the table starts getting full
      - Rehashing: reallocate the keys to a bigger table if the first one starts getting full
    - - Time efficiency:
        
        Hashing takes Θ(1) on the average, but Θ(n) in the very unlikely worst case
        
        Balanced search trees take Θ(log n) for average and worst cases
      - Hashing, unlike balanced search trees, does not preserve the order of keys.