data structures using one of these techniques is caching which saves information in the memorythe other is hashing which makes looking up the file location in the memory much quicker than most other methods hashing technique is used to implement compiler symbol tables in +the compiler uses symbol table to keep record of all the user-defined symbols in +program hashing facilitates the compiler to quickly look up variable names and other attributes associated with symbols hashing is also widely used for internet search engines real world applications of hashing cd databases for cdsit is desirable to have world-wide cd database so that when users put their disk in the cd playerthey get full table of contents on their own computer' screen these tables are not stored on the disks themselvesi the cd does not store any information about the songsrather this information is downloaded from the database the critical issue to solve here is that cds have no id numbers stored on themso how will the computer know which cd has been put in the playerthe only information that can be used is the track lengthand the fact that every cd is different basicallya big number is created from the track lengthsalso known as 'signaturethis signature is used to identify particular cd the signature is value obtained by hashing for examplea number of length of or hexadecimal digits is made upthe number is then sent to the databaseand that database looks for the closest match the reason being that track length may not be measured exactly drivers licenses/insurance cards like our cd exampleeven the driver' license numbers or insurance card numbers are created using hashing from data items that never changedate of birthnameetc sparse matrix sparse matrix is two-dimensional array in which most of the entries contain that isin sparse array there are very few non-zero entries of coursewe can store array as it isbut this would lead to sheer wastage of valuable memory so another possibility is to store the non-zero elements of the spare matrix as elements in array that is by using hashingwe can store two-dimensional array in one-dimensional array there is one-to-one correspondence between the elements in the sparse matrix and the elements in the array this concept is clearly visible in fig if the size of the sparse matrix is ynand there are non-zero entries in itthen from the coordinates ( ,jof matrixwe determine an index in an array by simple calculation thuswe have = ( ,jfor some function hcalled hash function the size of the array is proportional to this is far better from the size of the sparse matrix that required storage proportional to yn for exampleif we have triangular sparse matrix athen an entry [ijcan be mapped to an entry in the array by calculating the index using the hash function (iji( - )/ figure [ sparse matrix table file signatures file signatures provide compact means of identifying files we use functionh[ ]the file signaturewhich is property of the file although we can store files by namesignatures provide compact identity to files since signature depends on the contents of fileif any change is made to the filethen the signature will change in this waythe signature of file can be used as quick verification to see if anyone has altered the fileor if it has lost bit during transmission signatures are widely used for files that store marks of students game boards in the game board for tic-tac-toe or chessa position in game may be stored using hash function