What is the characteristics of this hash function? - Linux

This is a discussion on What is the characteristics of this hash function? - Linux ; 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 ...

+ Reply to Thread
Results 1 to 5 of 5

Thread: What is the characteristics of this hash function?

  1. What is the characteristics of this hash function?

    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
    }


  2. Re: What is the characteristics of this hash function?

    "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錸s Rullg錼d
    mans@mansr.com

  3. Re: What is the characteristics of this hash function?

    On Mar 28, 1:45 am, M錸s Rullg錼d 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!



  4. Re: What is the characteristics of this hash function?

    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

  5. Re: What is the characteristics of this hash function?

    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?



+ Reply to Thread