chap searching the set difference can be implemented in java using the expression &~ (is the symbol for bit-wise negationfor larger sets that do not fit into single computer wordthe equivalent operations can be performed in turn on the series of words making up the entire bit vector this method of computing sets from bit vectors is sometimes applied to document retrieval consider the problem of picking from collection of documents those few which contain selected keywords for each keywordthe document retrieval system stores bit vector with one bit for each document if the user wants to know which documents contain certain three keywordsthe corresponding three bit vectors are and'ed together those bit positions resulting in value of correspond to the desired documents alternativelya bit vector can be stored for each document to indicate those keywords appearing in the document such an organization is called signature file the signatures can be manipulated to find documents with desired combinations of keywords hashing this section presents completely different approach to searching tablesby direct access based on key value the process of finding record using some computation to map its key value to position in the table is called hashing most hashing schemes place records in the table in whatever order satisfies the needs of the address calculationthus the records are not ordered by value or frequency the function that maps key values to positions is called hash function and is usually denoted by the array that holds the records is called the hash table and will be denoted by ht position in the hash table is also known as slot the number of slots in hash table ht will be denoted by the variable with slots numbered from to the goal for hashing system is to arrange things such thatfor any key value and some hash function hi (kis slot in the table such that < (km and we have the key of the record stored at ht[iequal to hashing only works to store sets that ishashing cannot be used for applications where multiple records with the same key value are permitted hashing is not good method for answering range searches in other wordswe cannot easily find all records (if anywhose key values fall within certain range nor can we easily find the record with the minimum or maximum key valueor visit the records in key order hashing is most appropriate for answering the question"what recordif anyhas key value ?for applications where access involves only exact-match querieshashing is usually the search method of choice because it is extremely efficient when implemented correctly as you will see in this sectionhoweverthere