CentralNotice Hash table From Wikipedia, the free encyclopedia Jump to: navigation , search Not to be confused with Hash list or Hash tree . Hash table Type Unordered associative array Invented 1953 Time complexity in big O notation Average Worst case Space O( n ) [ 1 ] O( n ) Search O(1) O( n ) Insert O(1) O( n ) Delete O(1) O( n ) A small phone book as a hash table In computing , a hash table (also hash map ) is a data structure used to implement an associative array , a structure that can map keys to values . A hash table uses a hash function to compute an index into an array of buckets or slots , from which the correct value can be found. Ideally, the hash function will assign each key to a unique bucket, but this ideal situation is rarely achievable in practice (unless the hash keys are fixed; i.e. new entries are neve...