LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Home Forums Tutorials Articles Register
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 03-04-2008, 02:39 AM   #1
ahm_irf
Member
 
Registered: Feb 2007
Posts: 37

Rep: Reputation: 15
Needs to know hashing functions used for array indexing


I wanna know the hash functions that I can used for indexing arrays.

Are there hash functions that can generate values lie between any range. e.g. if array size is n, the value hash function will generate should lie between 0 to n.
 
Old 03-04-2008, 03:22 AM   #2
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: Debian
Posts: 2,536

Rep: Reputation: 111Reputation: 111
http://en.wikipedia.org/wiki/List_of...hash_functions
 
Old 03-04-2008, 07:12 PM   #3
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 10,659
Blog Entries: 4

Rep: Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941Reputation: 3941
What is traditionally done is that a "hash function" is applied to the key, and the hash-function returns an integer. (The design of the hash function is intended to be such that it generates a well-distributed span of output-values so that all of the hash-buckets might be more-or-less-equally filled.)

The hash-function result is forced to be a positive integer using some process such as anding it with the value 0x7FFFFFF (which forces the leftmost or "sign" bit to be zero).

Finally, the arithmetic modulo operator is applied, taking the hash-value mod the number-of-buckets. (This operator gives the remainder from a division operation.)

A hash-lookup function derives its speed from this hashing-process. Once the proper 'bucket-number' has been determined, only the values in that particular bucket need to be searched for the desired value. If the hash-function is a good one, and the (should-always-be-prime...) number of buckets is appropriate, this will reduce the search-space to a usefully-small subset.

It should be noted that a hash-lookup structure is not strictly "an array" in the most-traditional sense. A traditional array is a contiguous block of storage... but "a traditional array" is not nearly as useful in-practice as is a hash-based structure. A hash-structure handles a variable number of entries with aplomb, and also does not waste storage if the key-value distribution is "sparse." The algorithm is simple, blisteringly fast, and "much better than nothing."

Last edited by sundialsvcs; 03-04-2008 at 07:15 PM.
 
  


Reply



Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Passing Array Elements to functions melikai Programming 4 10-31-2006 10:27 PM
Standard C library numeric array functions? bulliver Programming 8 04-12-2006 08:45 PM
using arrays and functions and trying to initialize a point in the array mshinska Programming 1 11-11-2005 02:21 AM
array functions in c djgerbavore Programming 6 01-07-2005 03:28 PM
php: array with functions ldp Programming 7 09-22-2004 04:55 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 05:03 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration