Please enable JavaScript.

Coggle requires JavaScript to display documents.

hash table - Coggle Diagram

- - - - When we want to search for a key, the HT will use the same HF to find the corresponding bucket and search only in the specific bucket
      - When we insert a new key, the HF will decide which bucket the key should be assigned
  - - - HF
        
        Depends on the range of key values and the number of buckets
        
        Idea: try to assign the key to the bucket as uniformly as possible.
        
        A perfect HF will be a one-one mapping between the key and the bucket. However, in most cases, a HF is not perfect and it is a tradeoff between the amount of buckets and the capacity of a bucket.
      - Collision Resolution
        
        In most cases, collisions are almost inevitable
        
        A collision resolution also should solve the following questions
        
        How to organize the values in the same bucket?
        
        What if too many values are assigned to the same bucket?
        
        How to search for a target value in a specific bucket?
        
        The questions are related to the capacity of the bucket and the number of keys which might be mapped into the same bucket according to our HF.
        
        Let's assume that the bucket, which holds the maximum number of keys, has N keys.
        Typically, if N is constant and small, we can simply use an array to store keys in the same bucket. If N is variable or large, we might need to use height-balanced binary search tree instead.
  - - - Separate Chaining: for values with the same hash key, we keep them in a bucket, and each bucket is independent of each other.
      - Open Addressing: whenever there is a collision, we keep on probing on the main space with certain strategy until a free slot is found.
      - 2-Choice Hashing: we use two hash functions rather than one, and we pick the generated address with fewer collision.
  - - - Swap
        
        First swap the element we want to remove with the last element in the bucket. Then remove the last element
      - Linked List
        
        Use a linked list
  - - - The key value can be any hashable type. Any value belongin to a hashable type will have a hashcode (used as the key).
      - Each bucket contains an array to store all the values in the same bucket.
      - If there are too many values in the same bucket, these values will be maintained in a height-balanced binary search tree instead.
        
        Using height-balanced BST:
        Average time complexity of insertion and search: O(1).
        Wost case time complexity of insertion and search: O(logN)
- - - - All values belong to the same group will be mapped in the same group.
        
        Values which needed to be separated into different groups will not be mapped into the same group.