Database Reference
In-Depth Information
Review of Hashing
Hashing is a technique for mapping data from a large set to limited space in a much
smaller set. This appendix provides an overview of the subject. The appendix covers the
fundamentals of hashing under the following captions:
Introduction
Hash Functions
Collision Resolution
Hashing in Java
Summary and Concluding Remarks
A2.1 Introduction
In computer science, it is always important to establish mapping functions between
(what is called) the conceptual user view of data and actual physical storage reality in
the computer system. The former is what the end-user sees; the latter is what is actually
stored on the storage media. For reasons that will become clear in your courses in
software engineering, database systems, and operating systems, the two perspectives are
seldom identical.
Another equally important issue is how to find data that is stored. For example,
consider a transaction file for a financial institution, with millions of records. As you
can well imagine (based on earlier discussions), sequential access of records in this file,
would be suitable for a non-interactive program running in batch mode. However, it
would not be suitable for a program that needs to provide interactive responses to the
end used, based on different customers. You certainly would not want to process this
file relying solely on an array, linked list, queue, or stack. You could use a BST, a heap, or
better yet, a B-tree! But how would you determine where on the storage media to actually
store records of your file so they can be easily retrieved when needed? Hashing is one
technique for addressing this problem.
Hashing is a technique that addresses the problems of where (on a physical
storage medium) to store data and how to retrieve the data stored. In hashing, there is a
predictable relationship between a key value used to identify a record, and the record's
location on a storage medium.
 
Search WWH ::




Custom Search