HashTable Review

This page is review of the HashTable

A Hash table is defined as a data structure used to insert, look up, and remove key-value pairs quickly.

Rules of HashTables

  1. A hash table's load factor is determined by how many elements are kept there in relation to how big the table is.
  2. A Function that translates keys to array indices is known as a hash function.
  3. For lookup, insertion, and deletion operations, hash tables have an average-case time complexity of O(1). Yet, these operations may, in the worst case, require O(n) time, where n is the number of elements in the table.

Hash Table Properites

  • Hash Table: array that contains(key,value) pairs
  • Table Size: current capcity(array Length)
  • Load Factor: (Number of Key Value Pairs in Table)⁄(Table Size)

    • Choosing a Hash Function

  • To ensure that the number of collisions is kept to a minimum, a good hash function should distribute the keys throughout the hash table in a uniform manner.
  • To enable speedy hashing and key retrieval, the hash function should be efficient.
  • A hash function should be flexible enough to adjust as the data being hashed often changes.

    • List of Sources

    1. GeeksforGeeks
    2. Image Source