Hash Table: Difference between revisions
Line 11: | Line 11: | ||
=Overview= | =Overview= | ||
Hash tables are one of the most used data structures in programming. They don't have that many operations ([[#INSERT|INSERT()]], [[#DELETE|DELETE()]] and [[#SEARCH|SEARCH()]]), but what they do, they do really well. Conceptually, a hash table is an array that provides immediate random access for constant time insertion, deletion and lookup based on '''an arbitrary key''' and not an integral index, for a dynamic set of keys. The hash map implementation do store data in proper arrays, and the mapping between the arbitrary key and the integral position in the array is provided by a [[#Hash_Functions|hash function]]. | Hash tables are one of the most used data structures in programming. They don't have that many operations ([[#INSERT|INSERT()]], [[#DELETE|DELETE()]] and [[#SEARCH|SEARCH()]]), but what they do, they do really well. Conceptually, a hash table is an array that provides immediate random access for constant time insertion, deletion and lookup based on '''an arbitrary key''' and not an integral index, for a dynamic set of keys. The hash map implementation do store data in proper arrays, and the mapping between the arbitrary key and the integral position in the array is provided by a [[#Hash_Functions|hash function]]. Some time people refer to hash maps as [[Data_Structures#Dictionary|dictionaries]] | ||
=Canonical Use= | =Canonical Use= |
Revision as of 20:03, 16 October 2021
External
Internal
Overview
Hash tables are one of the most used data structures in programming. They don't have that many operations (INSERT(), DELETE() and SEARCH()), but what they do, they do really well. Conceptually, a hash table is an array that provides immediate random access for constant time insertion, deletion and lookup based on an arbitrary key and not an integral index, for a dynamic set of keys. The hash map implementation do store data in proper arrays, and the mapping between the arbitrary key and the integral position in the array is provided by a hash function. Some time people refer to hash maps as dictionaries
Canonical Use
Hash tables are used in situations where we need to do fast lookups of arbitrary keys.
Hash Table Implementation Discussion
The purpose of a hash table is to maintain a dynamic set of records, each record identified by a unique key, and provide constant time insertion, deletion and search.
Chaining
Linear Probing
Hash Functions
Supported Operations
INSERT(X)
Add a new key/value pair INSERT(X) to the hash map in O(1) running time.
DELETE(K)
Delete a key and the corresponding value DELETE(K) from the hash map in O(1) running time.
SEARCH(K)
Return the value corresponding to the provided key K SEARCH(K), or NULL if the key does not exist, in O(1) running time.