Hash Table: Difference between revisions
Jump to navigation
Jump to search
| Line 5: | Line 5: | ||
=Overview= | =Overview= | ||
A hash table is a [[Data Structures#Dynamic_Set|dynamic set]] that supports [[Data Structures#INSERT|INSERT]], [[Data Structures#DELETE|DELETE]] and [[Data Structures#SEARCH|SEARCH]] - a [[Data_Structures#Dictionary|dictionary]]. | A hash table is a [[Data Structures#Dynamic_Set|dynamic set]] that supports [[Data Structures#INSERT|INSERT]], [[Data Structures#DELETE|DELETE]] and [[Data Structures#SEARCH|SEARCH]] - a [[Data_Structures#Dictionary|dictionary]]. | ||
The simplest, and the most time-efficient implementation of a hash table is a | |||
=Time Complexity= | =Time Complexity= | ||
Revision as of 21:52, 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
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).
Direct-Address Table
Hash Table
TODO
TODO Hash Map