A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. Data structures are used in almost every program or software system. There are many different types of data structures, such as hash tables, binary search trees, skip lists, ternary search trees, etc. In particular, a hash table is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name) to their associated values (e.g., their telephone number). Currently, in many situations, hash tables turn out to be more efficient than search trees or other table lookup structures. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches and sets.
While hash tables are currently more efficient than search trees or other table lookup structures, the memory footprint (referring to the amount of main memory that a program uses or references while running) and access speed (referring to the lookup rate) could be improved. Hence, the functionality of hash tables should be maintained while reducing the memory footprint and improving access speed.