|
Home > Archive > Unix Programming > March 2007 > What is the characteristics of this hash function?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
What is the characteristics of this hash function?
|
|
| Bin Chen 2007-03-27, 1:19 pm |
| This is from Linux kernel for hashing the page cache, but what is the
theory behind this? I mean, what ensure this hash function can
distribute the values equally to avoid the conflicts?
I also want to know any book has a collection of hash algorithms that
can apply to many different cases, or any websites?
/*
* We use a power-of-two hash table to avoid a modulus,
* and get a reasonable hash by knowing roughly how the
* inode pointer and indexes are distributed (ie, we
* roughly know which bits are "significant")
*
* For the time being it will work for struct address_space too (most
of
* them sitting inside the inodes). We might want to change it later.
*/
static inline unsigned long _page_hashfn(struct address_space *
mapping, unsigned long index)
{
#define i (((unsigned long) mapping)/(sizeof(struct inode) & ~
(sizeof(struct inode) - 1)))
#define s(x) ((x)+((x)>>PAGE_HASH_BITS))
return s(i+index) & (PAGE_HASH_SIZE-1);
#undef i
#undef s
}
| |
| Måns Rullgård 2007-03-27, 1:19 pm |
| "Bin Chen" <binary.chen@gmail.com> writes:
> This is from Linux kernel for hashing the page cache, but what is the
> theory behind this? I mean, what ensure this hash function can
> distribute the values equally to avoid the conflicts?
The comment you quoted pretty much explains it.
> I also want to know any book has a collection of hash algorithms that
> can apply to many different cases, or any websites?
Google for Bob Jenkins.
> /*
> * We use a power-of-two hash table to avoid a modulus,
> * and get a reasonable hash by knowing roughly how the
> * inode pointer and indexes are distributed (ie, we
> * roughly know which bits are "significant")
> *
> * For the time being it will work for struct address_space too (most of
> * them sitting inside the inodes). We might want to change it later.
> */
> static inline unsigned long _page_hashfn(struct address_space *
> mapping, unsigned long index)
> {
> #define i (((unsigned long) mapping)/(sizeof(struct inode) & ~
> (sizeof(struct inode) - 1)))
> #define s(x) ((x)+((x)>>PAGE_HASH_BITS))
> return s(i+index) & (PAGE_HASH_SIZE-1);
> #undef i
> #undef s
> }
>
--
Måns Rullgård
mans@mansr.com
| |
| Bin Chen 2007-03-29, 1:24 pm |
| On Mar 28, 1:45 am, M=E5ns Rullg=E5rd <m...@mansr.com> wrote:[vbcol=seagreen]
> "Bin Chen" <binary.c...@gmail.com> writes:
>
> The comment you quoted pretty much explains it.
>
>
> Google for Bob Jenkins.
>
>
>
I really don't know why the hash is calculated by this, especially why
this hash value has some relation to sizeof struct inode.
I do know why this is the power of two hash! It's not the hard part of
my question!
| |
|
| On 2007-03-29, Bin Chen <binary.chen@gmail.com> wrote:
this almost the same as
((struct inode*) mapping - (struct inode *) NULL )
[vbcol=seagreen]
> I really don't know why the hash is calculated by this, especially why
> this hash value has some relation to sizeof struct inode.
there must be some relationship between struct address_space and struct_inode
bye
Jasen
| |
| Bin Chen 2007-03-30, 7:17 am |
| On 3=D4=C230=C8=D5, =CF=C2=CE=E73=CA=B115=B7=D6, jasen <j...@free.net.nz> w=
rote:
> On 2007-03-29, Bin Chen <binary.c...@gmail.com> wrote:
>
>
> this almost the same as
>
> ((struct inode*) mapping - (struct inode *) NULL )
>
>
> there must be some relationship between struct address_space and struct_i=
node
More precise?
|
|
|
|
|