hash table is useful for any graph theory problem where the nodes have real names instead of numbers hereas the input is readvertices are assigned integers from onward by order of appearance againthe input is likely to have large groups of alphabetized entries for examplethe vertices could be computers then if one particular installation lists its computers as ibm ibm ibm there could be dramatic effect on efficiency if search tree is used third common use of hash tables is in programs that play games as the program searches through different lines of playit keeps track of positions it has seen by computing hash function based on the position (and storing its move for that positionif the same position recursusually by simple transposition of movesthe program can avoid expensive recomputation this general feature of all game-playing programs is known as the transposition table yet another use of hashing is in online spelling checkers if misspelling detection (as opposed to correctionis importantan entire dictionary can be prehashed and words can be checked in constant time hash tables are well suited for thisbecause it is not important to alphabetize wordsprinting out misspellings in the order they occurred in the document is certainly acceptable hash tables are often used to implement cachesboth in software (for instancethe cache in your internet browserand in hardware (for instancethe memory caches in modern computersthey are also used in hardware implementations of routers we close this by returning to the word puzzle problem of if the second algorithm described in is usedand we assume that the maximum word size is some small constantthen the time to read in the dictionary containing words and put it in hash table is (wthis time is likely to be dominated by the disk / and not the hashing routines the rest of the algorithm would test for the presence of word for each ordered quadruple (rowcolumnorientationnumber of charactersas each lookup would be ( )and there are only constant number of orientations ( and characters per wordthe running time of this phase would be ( cthe total running time would be ( )which is distinct improvement over the original ( wwe could make further optimizationswhich would decrease the running time in practicethese are described in the exercises exercises given input { and hash function (xx (mod ( )show the resulting separate chaining hash table hash table using linear probing hash table using quadratic probing hash table with second hash function ( ( mod show the result of rehashing the hash tables in exercise write program to compute the number of collisions required in long random sequence of insertions using linear probingquadratic probingand double hashing