hash function

Discussion in 'C++' started by zoro, Dec 20, 2006.

  1. zoro

    zoro Guest

    i didn't understand what does it mean for a hash function to produce
    well-dispersed output, and why it is important?

    thank u for ur help
     
    zoro, Dec 20, 2006
    #1
    1. Advertising

  2. zoro

    Mirek Fidler Guest

    zoro wrote:
    > i didn't understand what does it mean for a hash function to produce
    > well-dispersed output, and why it is important?


    Well, let us start with what is the worst possibility here w.r.t.
    dispersing:

    Hash function that returns always zero (or other constant number) is
    valid, but alters hashing search operation to linear search.

    By well-dispersed is meant the "opposite" to this situation... (as many
    different values for different keys as possible).

    Mirek
     
    Mirek Fidler, Dec 20, 2006
    #2
    1. Advertising

  3. zoro wrote:
    > i didn't understand what does it mean for a hash function to produce
    > well-dispersed output, and why it is important?


    This almost sounds like homework, so I won't give you a direct answer.
    Instead consider the yellow pages (or a telephone book) as a very simple
    example of hashing:

    Telephone books usually use a hash function that says "return the first
    character of the input" and proceeds to put the item in the appropriate
    section (A for Alf, B for Bobo, C for Cirdan, etc).

    But consider what would happen if the telephone book used the hash function:
    "return 'A' for any input" instead.

    Now, assuming that all letters are equally likely to begin a name, the first
    function produces input that is well-dispersed. The second one does not. As
    for why it is important for the hash to produce well-dispersed output, I would
    hope that by now it has become clear.

    -n


    P.S.: Yes, I realize that my example is not perfect. But it was not meant to
    be and it does get the point across.
     
    Nikolaos D. Bougalis, Dec 21, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Red Orchid
    Replies:
    3
    Views:
    1,050
  2. Pieter Claassen
    Replies:
    1
    Views:
    1,120
    CBFalconer
    Aug 4, 2004
  3. Bo Peng
    Replies:
    4
    Views:
    792
  4. rp
    Replies:
    1
    Views:
    540
    red floyd
    Nov 10, 2011
  5. Srijayanth Sridhar
    Replies:
    19
    Views:
    627
    David A. Black
    Jul 2, 2008
Loading...

Share This Page