System and method for rapidly identifying the existence and location of an item in a file

• US 6,862,602 B2
• Filed: 10/01/2001
• Issued: 03/01/2005
• Est. Priority Date: 03/07/1997
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Guha, Ramanathan V.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/969,492
• Publication Number:
  US 20020073068A1
• Time in Patent Office: 1,247 Days
• Field of Search: 707/101, 707/100, 707/1, 707/2, 707/3, 707/4, 707/104.1, 707/103.R
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A system and method for rapidly identifying the existence and location of an item in a file using an improved hash table architecture. A hash table is constructed having a plurality of hash buckets, each identified by a primary hash key. Each hash entry in each hash bucket contains a pointer to a record in a master file, as well as a secondary hash key independent of the primary hash key. A search for a particular item is performed by identifying the appropriate hash bucket by obtaining a primary hash key for the search term. Individual hash entries within the hash bucket are checked for matches by comparing the stored secondary keys with the secondary key for the search term. Potentially matching records can be identified or ruled out without necessitating repeated reads of the master file. The improved hash table system and method is employed in a contextual text searching application for determining the intersection of a text search with a hierarchical categorization scheme.

Claims

1. A system for rapidly locating an item known to exist in a file, comprising:

a master file for storing a plurality of items;

a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a pointer to an item in the master file, for identifying the location of the item; and

a secondary hash key obtained by applying a secondary hash function;

a search term input device for obtaining a search term known to exist among the plurality of items;

a primary hash function application module coupled to the search term input device, for applying a primary hash function to obtain a primary hash key for the search term;

a secondary hash function application module coupled to the search term input device, for applying the secondary hash function to obtain a secondary hash key for the search term;

a hash key comparison module coupled to the hash table, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket, wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term; and

an output device coupled to the hash key comparison module, for, responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generating output identifying an item in the master file corresponding to the matching secondary hash key.

2. The system of claim 1, wherein the search term comprises a plurality of characters, and the primary hash function application module applies a primary hash function by performing successive exclusive-OR operations on successive characters of the search term.

3. The system of claim 1, wherein the search term comprises a plurality of segments, and the secondary hash function application module applies a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

4. The system of claim 1, wherein the output device outputs

the results of the hash key comparison performed by the hash key comparison module.

5. The system of claim 1, wherein:

the master file is implemented as a database in a computer system; and

the hash table is implemented as a database in a computer system.

6. The system of claim 1, wherein:

the master file stores a plurality of descriptors, each descriptor representing a document associated with a particular subject category; and

the item represents a result of a text search.

7. A method of locating an item known to exist in a file, the file having a plurality of items, comprising:

a) applying a primary hash function to obtain a primary hash key for a search term known to exist among the plurality of items;

b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and a secondary hash key;

c) applying a secondary hash function to obtain a secondary hash key for the search term;

d) comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket; and

e) responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generating output identifying an item in the file corresponding to the matching secondary hash key.

8. The method of claim 7, wherein the value in each hash entry represents a pointer to a record location in a master file.

9. A system for rapidly locating an item known to exist in a file, comprising:

master file storage means for storing a plurality of items; and

hash table means, coupled to the master file storage means, for storing a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

pointing means for pointing to an item in the master file, for identifying the location of the item; and

storing means for storing a secondary hash key obtained by applying a secondary hash function;

search term input means for obtaining a search term known to exist among the plurality of items;

primary hash function application means coupled to the search term input means, for applying a primary hash function to obtain a primary hash key for the search term;

secondary hash function application means coupled to the search term input means, for applying the secondary hash function to obtain a secondary hash key for the search term;

hash key comparison means coupled to the hash table means, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket, wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term; and

output means coupled to the hash key comparison means, for, responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generating output identifying an item in the master file corresponding to the matching secondary hash key.

10. The system of claim 9, wherein the search term comprises a plurality of characters, and the primary hash function application means applies a primary hash function by performing successive exclusive-OR operations on successive characters of the search term.

11. The system of claim 9, wherein the search term comprises a plurality of segments, and the secondary hash function application means applies a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

12. The system of claim 9, wherein the output means outputs

the results of the hash key comparison performed by the hash key comparison means.

13. The system of claim 9, wherein:

the master file storage means is implemented as a database in a computer system; and

the hash table means is implemented as a database in a computer system.

14. The system of claim 9, wherein:

the master file storage means stores a plurality of descriptor means, each descriptor means for representing a document associated with a particular subject category; and

the item represents a result of a text search.

15. A system for locating an item known to exist in a file, the file having a plurality of items, comprising:

primary hash function means, for applying a primary hash function to obtain a primary hash key for a search term known to exist among the plurality of items;

hash bucket identification means, coupled to the primary hash function means, for identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and a secondary hash key;

secondary hash function means, for applying a secondary hash function to obtain a secondary hash key for the search term;

comparing means, coupled to the secondary hash function means and to the hash bucket identification means, for comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket; and

output means, coupled to the comparing means, for, responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generating output identifying an item in the file corresponding to the matching secondary hash key.

16. A computer-implemented method for locating an item known to exist in a file, comprising:

a) accessing a master file for storing a plurality of items;

b) obtaining a search term known to exist among the plurality of items;

c) applying a primary hash function to obtain a primary hash key for the search term;

d) applying a secondary hash function to obtain a secondary hash key for the search term;

e) accessing a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a pointer to an item in the master file, for identifying the location of the item; and

a secondary hash key obtained by applying the secondary hash function;

f) comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket, wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term; and

g) responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generating output identifying an item in the master file corresponding to the matching secondary hash key.

17. The method of claim 16, wherein the search term comprises a plurality of characters, and c) comprises applying a primary hash function by performing successive exclusive-OR operations on successive characters of the search term.

18. The method of claim 16, wherein the search term comprises a plurality of segments, and d) comprises applying a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

19. The method of claim 16, further comprising:

h) outputting the results of f).

20. The method of claim 16, wherein:

the master file is a database in a computer system; and

the hash table is a database in a computer system.

21. The method of claim 16, wherein:

the master file stores a plurality of descriptors, each descriptor representing a document associated with a particular subject category; and

the item represents a result of a text search.

22. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for locating an item known to exist in a file, comprising:

computer-readable program code devices configured to cause a computer to access a master file for storing a plurality of items;

computer-readable program code devices configured to cause a computer to obtain a search term known to exist among the plurality of items;

computer-readable program code devices configured to cause a computer to apply a primary hash function to obtain a primary hash key for the search term;

computer-readable program code devices configured to cause a computer to apply a secondary hash function to obtain a secondary hash key for the search term;

computer-readable program code devices configured to cause a computer to access a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a pointer to an item in the master file, for identifying the location of the item; and

a secondary hash key obtained by applying the secondary hash function;

computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket, wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term; and

computer-readable program code devices configured to cause a computer to, responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generate output identifying an item in the master file corresponding to the matching secondary hash key.

23. The computer program product of claim 22, wherein the search term comprises a plurality of characters, and the computer-readable program code devices configured to cause a computer to apply a primary hash function comprise computer-readable program code devices configured to cause a computer to apply a primary hash function by performing successive exclusive-OR operations on successive characters of the search term.

24. The computer program product of claim 22, wherein the search term comprises a plurality of segments, and the computer-readable program code devices configured to cause a computer to apply a primary hash function comprise computer-readable program code devices configured to cause a computer to apply a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

25. The computer program product of claim 22, further comprising:

computer-readable program code devices configured to cause a computer to output the results of the computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket.

26. The computer program product of claim 22, wherein:

the master file is a database in a computer system; and

the hash table is a database in a computer system.

27. The computer program product of claim 22, wherein:

the master file stores a plurality of descriptors, each descriptor representing a document associated with a particular subject category; and

the item represents a result of a text search.

28. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for locating an item known to exist in a file, the file having a plurality of items, comprising:

computer-readable program code devices configured to cause a computer to apply a primary hash function to obtain a primary hash key for a search term known to exist among the plurality of items;

computer-readable program code devices configured to cause a computer to identify a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and a secondary hash key;

computer-readable program code devices configured to cause a computer to apply a secondary hash function to obtain a secondary hash key for the search term;

computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket; and

computer-readable program code devices configured to cause a computer to, responsive to the comparison of secondary hash keys resulting in a single match in the identified hash bucket, generate output identifying an item in the file corresponding to the matching secondary hash key.

29. A system for rapidly locating a data item, comprising:

a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a data item; and

a secondary hash key obtained by applying a secondary hash function;

a search term input device for obtaining a search term;

a primary hash function application module coupled to the search term input device, for applying a primary hash function to obtain a primary hash key for the search term;

a secondary hash function application module coupled to the search term input device, for applying the secondary hash function to obtain a secondary hash key for the search term; and

a hash key comparison module coupled to the hash table, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

30. The system of claim 29, further comprising:

an output device coupled to the hash key comparison module, for, responsive to the results of the hash key comparison indicating a match, outputting the location of the matching item in the master file.

31. A method of locating a data item, comprising:

a) applying a primary hash function to obtain a primary hash key for a search term;

b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a data item and a secondary hash key;

c) applying a secondary hash function to obtain a secondary hash key for the search term; and

d) comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket.

32. The method of claim 31, further comprising:

e) responsive to the comparison of d) resulting in identification of a matching hash entry, outputting the data item corresponding to the identified hash entry.

33. A system for locating a data item, comprising:

hash table means for storing a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

first storing means for storing a data item; and

second storing means for storing a secondary hash key obtained by applying a secondary hash function;

search term input means for obtaining a search term;

primary hash function application means coupled to the search term input means, for applying a primary hash function to obtain a primary hash key for the search term;

secondary hash function application means coupled to the search term input means, for applying the secondary hash function to obtain a secondary hash key for the search term; and

hash key comparison means coupled to the hash table means, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

34. The system of claim 33, further comprising:

output means coupled to the hash key comparison means, for, responsive to the results of the hash key comparison indicating a match, outputting the data item corresponding to the matching hash entry.

35. A computer-implemented method for rapidly identifying the existence of an item in a file, comprising:

a) accessing a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a data item; and

a secondary hash key obtained by applying a secondary hash function;

b) obtaining a search term;

c) applying a primary hash function to obtain a primary hash key for the search term;

d) applying the secondary hash function to obtain a secondary hash key for the search term; and

e) comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

36. The method of claim 35, further comprising:

f) responsive to the results of e) indicating a match, outputting the data item corresponding to the matching hash entry.

37. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for locating a data item, comprising:

computer-readable program code devices configured to cause a computer to access a hash table, comprising a plurality of hash buckets, each bash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising;

a data item; and

a secondary hash key obtained by applying a secondary hash function;

computer-readable program code devices configured to cause a computer to obtain a search term;

computer-readable program code devices configured to cause a computer to apply a primary hash function to obtain a primary hash key for the search term;

computer-readable program code devices configured to cause a computer to apply the secondary hash function to obtain a secondary hash key for the search term; and

computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

38. The computer program product of claim 37, further comprising computer-readable program code devices configured to, responsive to the results of the comparison indicating a match, output the data item corresponding to the matching hash entry.

39. A method of adding an item to a hash table, comprising:

a) applying a primary hash function to the item to obtain a primary hash key;

b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key;

c) creating a hash entry in the identified bucket;

d) applying a secondary hash function to the item to obtain a secondary hash key; and

e) forming a hash entry record from the secondary hash key; and

f) writing the hash entry record in the identified bucket.

40. The method of claim 39, further comprising:

a) adding a record containing the item to a master file.

41. The method of claim 40, wherein e) comprises:

e.1) combining the secondary hash key with a pointer to the record containing the item in the master file.

42. The method of claim 40, wherein the hash entry comprising a pointer to the record in the master file.

43. The method of claim 42, wherein the item has a value, and wherein e) comprises:

e.1) combining the secondary hash key with the value of the item.

44. The method of claim 39, wherein the item comprises a plurality of characters, and a) comprises applying a primary hash function by performing successive exclusive-OR operations on successive characters of the item.

45. The method of claim 39, wherein the item comprises a plurality of segments, and d) comprises applying a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

46. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for adding an item to a hash table, comprising:

computer-readable program code devices configured to cause a computer to apply a primary hash function to the item to obtain a primary hash key;

computer-readable program code devices configured to cause a computer to identify a hash bucket having a primary hash key corresponding to the obtained primary hash key;

computer-readable program code devices configured to cause a computer to create a hash entry in the identified bucket;

computer-readable program code devices configured to cause a computer to apply a secondary hash function to the item to obtain a secondary hash key; and

computer-readable program code devices configured to cause a computer to form a hash entry record from the secondary hash key; and

computer-readable program code devices configured to cause a computer to write the hash entry record in the identified bucket.

47. The computer program product of claim 46, further comprising:

computer-readable program code devices configured to cause a computer to add a record containing the item to a master file.

48. The computer program product of claim 47, wherein the computer-readable program code devices configured to cause a computer to form a hash entry record from the secondary hash key comprise:

computer-readable program code devices configured to cause a computer to combine the secondary hash key with a pointer to the record containing the item in the master file.

49. The computer program product of claim 47, wherein the hash entry comprises a pointer to the record in the master file.

50. The computer program product of claim 46, wherein the item has a value, and wherein the computer-readable program code devices configured to cause a computer to form a hash entry record from the secondary hash key comprise:

computer-readable program code devices configured to cause a computer to combine the secondary hash key with the value of the item.

51. The computer program product of claim 46, wherein the item comprises a plurality of characters, and the computer-readable program code devices configured to cause a computer to apply a primary hash function to the item to obtain a primary hash key comprise computer-readable program code devices configured to cause a computer to apply a primary hash function by performing successive exclusive-OR operations on successive characters of the item.

52. The computer program product of claim 46, wherein the item comprises a plurality of segments, and the computer-readable program code devices configured to cause a computer to apply a secondary hash function to the item to obtain a secondary hash key comprise computer-readable program code devices configured to cause a computer to apply a secondary hash function by encoding each of at least one of the plurality of segments according to a predetermined encoding scheme.

53. A system for rapidly identifying the existence of an item in a file, comprising:

a master file for storing a plurality of items; and

a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising a pointer to an item in the master file, for identifying the location of the item; and

for each hash entry, a secondary hash key obtained by applying a secondary hash function.

54. The system of claim 53, further comprising:

a search term input device for obtaining a search term;

a primary hash function application module coupled to the search term input device, for applying a primary hash function to obtain a primary hash key for the search term;

a secondary hash function application module coupled to the search term input device, for applying the secondary hash function to obtain a secondary hash key for the search term; and

a hash key comparison module coupled to the hash table, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

55. The system of claim 53, further comprising:

an item comparison module, coupled to the master file and to the hash table, for, responsive to the hash key comparison module indicating at least one hash entry having a matching secondary hash key, comparing the search term with an item in the master file identified by the pointer in the hash entry.

56. The system of claim 55, further comprising an output device coupled to the item comparison module, for, responsive to the results of the item comparison indicating a match, outputting the location of the matching item in the master file.

57. The system of claim 53, wherein:

the master file stores a plurality of descriptors, each descriptor representing a document associated with a particular subject category; and

the item represents a result of a text search.

58. A method of identifying the existence of an item in a file, comprising:

a) applying a primary hash function to obtain a primary hash key for a search term;

b) identifying a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and being associated with a secondary hash key;

c) applying a secondary hash function to obtain a secondary hash key for the search term; and

d) comparing the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket.

59. The method of claim 58, wherein the value in each hash entry represents a pointer to a record location in a master file, the method further comprising:

e) responsive to d) indicating at least one match, retrieving a record in the master file having a location corresponding to the value in the matching hash entry; and

f) comparing the search term with the retrieved record.

60. The method of claim 59, further comprising:

g) responsive to f) indicating a match, outputting the pointer for the matching record.

61. The method of claim 59, further comprising:

g) responsive to f) indicating a match, outputting the matching record.

62. A system for rapidly identifying the existence of an item in a file, comprising:

master file storage means for storing a plurality of items; and

hash table means, coupled to the master file storage means, for storing a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising pointing means for pointing to an item in the master file, for identifying the location of the item; and

storing means for storing, for each hash bucket, a secondary hash key obtained by applying a secondary hash function.

63. The system of claim 62, further comprising:

search term input means for obtaining a search term;

primary hash function application means coupled to the search term input means, for applying a primary hash function to obtain a primary hash key for the search term;

secondary hash function application means coupled to the search term input means, for applying the secondary hash function to obtain a secondary hash key for the search term; and

hash key comparison means coupled to the hash table means, for comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

64. The system of claim 63, further comprising:

item comparison means, coupled to the master file storage means and to the hash table means, for, responsive to the hash key comparison means indicating at least one hash entry having a matching secondary hash key, comparing the search term with an item in the master file storage means identified by the pointing means in the hash entry.

65. The system of claim 64, further comprising:

output means coupled to the item comparison means, for, responsive to the results of the item comparison indicating a match, outputting the location of the matching item in the master file storage means.

66. A computer-implemented method for rapidly identifying the existence of an item in a file, comprising:

a) accessing a master file for storing a plurality of items; and

b) accessing a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising a pointer to an item in the master file, for identifying the location of the item and each hash entry being associated with a secondary hash key obtained by applying a secondary hash function.

67. The method of claim 66, further comprising:

c) obtaining a search term;

d) applying a primary hash function to obtain a primary hash key for the search term;

e) applying the secondary hash function to obtain a secondary hash key for the search term; and

f) comparing the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

68. The method of claim 67, further comprising:

g) responsive to f) indicating at least one hash entry having a matching secondary hash key, comparing the search term with an item in the master file identified by the pointer in the hash entry.

69. The method of claim 67, further comprising:

h) responsive to the results of g) indicating a match, outputting the location of the matching item in the master file.

70. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for rapidly identifying the existence of an item in a file, comprising:

computer-readable program code devices configured to cause a computer to access a master file for storing a plurality of items; and

computer-readable program code devices configured to cause a computer to access a hash table, comprising a plurality of hash buckets, each hash bucket identified by a primary hash key, each hash bucket comprising at least one hash entry, each hash entry comprising a pointer to an item in the master file, for identifying the location of the item and each hash entry being associated with a secondary hash key obtained by applying a secondary hash function.

71. The computer program product of claim 70, further comprising:

computer-readable program code devices configured to cause a computer to obtain a search term;

computer-readable program code devices configured to cause a computer to apply a primary hash function to obtain a primary hash key for the search term;

computer-readable program code devices configured to cause a computer to apply the secondary hash function to obtain a secondary hash key for the search term; and

computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket;

wherein the identified hash bucket is identified by a primary hash key matching the obtained primary hash key for the search term.

72. The computer program product of claim 71, further comprising:

computer-readable program code devices configured to cause a computer, responsive to the computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with at least one secondary hash key for a hash entry in an identified hash bucket indicating at least one hash entry having a matching secondary hash key, to compare the search term with an item in the master file identified by the pointer in the hash entry.

73. The computer program product of claim 72, further comprising computer-readable program code devices configured, responsive to the results of the item comparison indicating a match, to cause a computer to output the location of the matching item in the master file.

74. A computer program product comprising a computer-usable medium having computer-readable code embodied therein for identifying the existence of an item in a file, comprising:

computer-readable program code devices configured to cause a computer to apply a primary hash function to obtain a primary hash key for a search term;

computer-readable program code devices configured to cause a computer to identify a hash bucket having a primary hash key corresponding to the obtained primary hash key, the hash bucket comprising at least one hash entry, each hash entry comprising a value and being associated with a secondary hash key;

computer-readable program code devices configured to cause a computer to apply a secondary hash function to obtain a secondary hash key for the search term; and

computer-readable program code devices configured to cause a computer to compare the secondary hash key for the search term with the secondary hash key for at least one hash entry in the identified hash bucket.

75. The computer program product of claim 74, wherein the value in each hash entry represents a pointer to a record location in a master file, the computer program product further comprising:

computer-readable program code devices configured to cause a computer to, responsive to the comparison indicating at least one match, retrieve a record in the master file having a location corresponding to the value in the matching hash entry; and

computer-readable program code devices configured to cause a computer to compare the search term with the retrieved record.

76. The computer program product of claim 75, further comprising:

computer-readable program code devices configured to cause a computer, responsive to the computer-readable program code devices configured to cause a computer to compare the search term with the retrieved record indicating a match, to output the pointer for the matching record.