Hash Table: Difference between revisions
Jump to navigation
Jump to search
| Line 14: | Line 14: | ||
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|direct-address 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|direct-address table]]. | ||
A hash table uses an array of size proportional to the number of keys actually stored. | |||
==Hash Table Time Complexity== | ==Hash Table Time Complexity== | ||
Revision as of 22:02, 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
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.
A hash table uses an array of size proportional to the number of keys actually stored.
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