Hash Table
Jump to navigation
Jump to search
Internal
Overview
A hash table is a dynamic set that supports INSERT, DELETE and SEARCH - a dictionary.
The simplest, and the most time-efficient implementation of a hash table is a direct address table. However, this implementation is in most cases inefficient from the point of view of allocated space.
Direct-Address Table
Hash Table
When the number of keys actually stored is small relative to the total number of possible keys, a hash table is much more effective alternative to a direct-address table.
Hash Table Time Complexity
In the worst case, searching an element in a hash table can take as long as the search in a linked list Θ(n). However, on average SEARCH, INSERT and DELETE operations take O(1).
TODO
TODO Hash Map