A tree is an efficient data structure, but it is not the fastest possible method for data retrieval. The fastest method would be to use an indexed array. If the whole key is converted into a number then that number could be used as the index into an array. Searching would simply involve looking up data in the array. If there are only limited values for the key then this could be useful, unfortunately this is rarely possible.
A hash table is a combination of an indexed array and a linked list. The key is used to generate a number (called the hash value) ,this number will not be unique to every key. The function used to generate the number from the key is called the hashing function. Since the hash value is not unique there will be a number of keys for each hash value. These are stored as a linked list. The hash value is used to index an array and then the linked list for that value is searched.
A simple hash function for words may be the ASCII value of the first character. The table will have 256 entries and each linked list will be a list of words which have the same first character.
The efficiency of hashing will depend on how randomly the hash function distributes key values into hash values. Our simple example would not be very efficient because there are more words starting with 't' than with '&'. A better hash function may be to add together all the characters in the key and use this value modulus 256.
Some languages provide a more complete way of creating new types - Abstract Data Types (ADTs). An ADT comprises the storage of the type and the operations allowed on the type. Languages such as Ada,C++, Haskell and Java allow ADTs. In C we must use functions.
Example: Complex numbers:This program contains a data structure and some functions that perform operations on it. These definitions allow us to use complex numbers without having to worry about how to perform arithmetic on them. The main program performs a fourier transform, it would be considerably longer and harder to follow without the ADT.