Hash Table: Difference between revisions
Jump to navigation
Jump to search
| Line 12: | Line 12: | ||
=Hash Table= | =Hash 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= | ||
Revision as of 21:53, 17 August 2018
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
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