There are many useful applications of hashing, including:

• A compiler keeps a symbol table containing all the names declared within a program, together with information about the objects that are named.

• A hash table can be used to map names to numbers. This is useful in graph theory and in networking, where a domain name is mapped to an IP address: willie.cs.utexas.edu = 128.83.130.16

• Programs that play games such as chess keep hash tables of board positions that have been seen and evaluated before. In general, hashing is a good way to look up items that do not have a natural sort order.

• The Rabin-Karp string search algorithm uses hashing to tell whether strings of interest are present in the text being searched. This algorithm is used in plagiarism detection and DNA matching.

• If an expensive function may be called repeatedly with the same argument value, pairs of (argument, result) can be saved in a hash table, with argument as the key, and result can be reused. This is called memoization.

Contents    Page-10    Prev    Next    Page+10    Index