kids encyclopedia robot

Hash table facts for kids

Kids Encyclopedia Facts
Quick facts for kids
Hash table
Type Unsorted associative array
Invented 1953
Time complexity in big O notation
Operation Average Worst case
Search O(1 + n/k) O(n)
Insert O(1) O(1)
Delete O(1 + n/k) O(n)
Space complexity
Space O(n) O(n)
Hash table 3 1 1 0 1 0 0 SP
A small phone book as a hash table

A hash table is one type of tool for storing information. In computer science, these tools for keeping track of information, or data, are called data structures. A hash table is a data structure that uses a hash function to keep track of where data is put. Each piece of information to be stored has a name, which is called a key. For example, a key might be a person's name. Each name is matched up to one piece of data called a value, like the person's telephone number.

The data is kept in another data structure called an array, which is like many boxes, or buckets, in a row to hold data. Each box has a number starting from 0 and counting up.

The idea behind a hash table is to figure out which box to put data by using only its name. This means, no matter how many boxes are filled up, you can always find information quickly if you have its name. The hash table uses a hash function to figure out which number to put data in from its name. The hash function reads a name and gives back a number.

A good Hash Table will always find information at the same speed, no matter how much data is put in. A lot of Hash Tables also let the user put key/value pairs (a name and its data) in and take them out at the same speed.

Because of this, Hash Tables can often find information faster than other tools, such as search trees or other table lookup structure. As a result, they are used in many kinds of computer software. They are used most for associative arrays, databases, caches, and sets.

Images for kids

See also

Kids robot.svg In Spanish: Tabla hash para niños

kids search engine
Hash table Facts for Kids. Kiddle Encyclopedia.