2003/09/25 hash

A hash is a numerical representation of some string of bytes. The purpose is to give quick access to data. Ignoring the mechanics for a moment, let's say that we have an algorithm that calculates "orange" as the number 7, and "apple" as 200. We'd store "orange" in record 7 of our file, "apple" in 200, and that would let us quickly find where either of these were stored. A hash in perl (the array type that looks like "%mystuff") is an example of this kind of storage.

Bytes are of course just numbers to start with, but we need some sort of boundary for the numbers of a hash. A 4 byte string is a 32 byte number, which is already getting fairly large. We couldn't easily store the record number represented by "Lawrence, Anthony P.". That's why hash algrorithms always use some sort of folding to make a smaller number. A simplistic hash might just take the first 4 bytes of that string and use that number as our index. However, that introduces the problem of non-unique hash results: "Lawrence, Anthony P." and "Lawrence, Kansas" will produce exactly the same number. Perl and other systems that use hashes have to prepare for such things by having overflow storage locations: the algorithm checks the default location to see if it is what you asked for, but if not goes to a specific other location to look again.

Good design of hash algorithms (the formula that produces the hash number) can minimize clashes (prime numbers come into use here). On Unix systems, when files keyed by a hash function are written to disk, you will often have unused records: no data hashed to match some of the record numbers. This can produce "sparse" files: files that appear to be larger than the actual disk blocks that they consume. That's a function of how Unix file systems work; there's nothing special about the file itself except that sections of it are unallocated.

Jump to Comments

Many of the products and books I review are things I purchased for my own use. Some were given to me specifically for the purpose of reviewing them. I resell or can earn commissions from the sale of some of these items. Links within these pages may be affiliate links that pay me for referring you to them. That's mostly insignificant amounts of money; whenever it is not I have made my relationship plain. I also may own stock in companies mentioned here. If you have any question, please do feel free to contact me.

Specific links that take you to pages that allow you to purchase the item I reviewed are very likely to pay me a commission. Many of the books I review were given to me by the publishers specifically for the purpose of writing a review. These gifts and referral fees do not affect my opinions; I often give bad reviews anyway.

We use Google third-party advertising companies to serve ads when you visit our website. These companies may use information (not including your name, address, email address, or telephone number) about your visits to this and other websites in order to provide advertisements about goods and services of interest to you. If you would like more information about this practice and to know your choices about not having this information used by these companies, click here.