"Bin Chen" 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

On Mar 28, 1:45 am, Måns Rullgård wrote:
> "Bin Chen" 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
> > }
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 wrote:
>> > 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)))

this almost the same as

((struct inode*) mapping - (struct inode *) NULL )

>> > #define s(x) ((x)+((x)>>PAGE_HASH_BITS))
>> > return s(i+index) & (PAGE_HASH_SIZE-1);
>> > #undef i
>> > #undef s
>> > }
> 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

On 3ÔÂ30ÈÕ, ÏÂÎç3ʱ15·Ö, jasen wrote:
> On 2007-03-29, Bin Chen wrote:
>
> >> > 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)))
>
> this almost the same as
>
> ((struct inode*) mapping - (struct inode *) NULL )
>
> >> > #define s(x) ((x)+((x)>>PAGE_HASH_BITS))
> >> > return s(i+index) & (PAGE_HASH_SIZE-1);
> >> > #undef i
> >> > #undef s
> >> > }
> > 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

More precise?