# # html hash
APLawrence.com -  Resources for Unix and Linux Systems, Bloggers and the self-employed

hash

I've removed advertising from most of this site and will eventually clean up the few pages where it remains.

While not terribly expensive to maintain, this does cost me something. If I don't get enough donations to cover that expense, I will be shutting the site down in early 2020.

If you found something useful today, please consider a small donation.



Some material is very old and may be incorrect today

© September 2003 Tony Lawrence

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.


If you found something useful today, please consider a small donation.



Got something to add? Send me email.





(OLDER)    <- More Stuff -> (NEWER)    (NEWEST)   

Printer Friendly Version

->
-> html hash


Inexpensive and informative Apple related e-books:

Take control of Apple TV, Second Edition

Take Control of iCloud

El Capitan: A Take Control Crash Course

Digital Sharing Crash Course

Take Control of IOS 11





More Articles by © Tony Lawrence





Printer Friendly Version

Have you tried Searching this site?

This is a Unix/Linux resource website. It contains technical articles about Unix, Linux and general computing related subjects, opinion, news, help files, how-to's, tutorials and more.

Contact us


Printer Friendly Version





C++ is a badly designed and ugly language. It would be a shame to use it in Emacs. (Richard Stallman)




Linux posts

Troubleshooting posts


This post tagged:

Programming

UnixWords



Unix/Linux Consultants

Skills Tests

Unix/Linux Book Reviews

My Unix/Linux Troubleshooting Book

This site runs on Linode