Hash Table: Difference between revisions
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
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]]. | ||
=Time Complexity= | =Time Complexity= | ||
Revision as of 21:49, 17 August 2018
Internal
Overview
A hash table is a dynamic set that supports INSERT, DELETE and SEARCH - a dictionary.
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).