At Wed, 16 Nov 2011 14:59:12 +0800,
Liu Yuan wrote:
>
> On 11/16/2011 02:45 PM, MORITA Kazutaka wrote:
>
> > At Wed, 16 Nov 2011 13:58:26 +0800,
> > Liu Yuan wrote:
> >>
> >> On 11/16/2011 01:50 PM, MORITA Kazutaka wrote:
> >>
> >>>>>
> >>>>> We already have a hash function, fnv_64a_buf(). How about using it
> >>>>> instead of introducing new one?
> >>>>>
> >>>>
> >>>>
> >>>> When I need a hash function that inputs an integer and outputs an
> >>>> integer for specified bits, I looked at the fnv_64a_buf(), it seems to
> >>>> me it tries to hash an string to integer. So I think these hash
> >>>> functions do a different thing, no?
> >>>
> >>> We already use it to calculate a hash value from a 64 bit object id:
> >>>
> >>> fnv_64a_buf(&oid, sizeof(uint64_t), FNV1A_64_INIT);
> >>>
> >>> I guess this generates a less random value than hash_64(), though.
> >>
> >>
> >> Umm, I didn't go over usage close enough, and this interface is more
> >> named to handle string hash, at least to me.
> >>
> >> So even we use it to hash integer, we need to further bit operation to
> >> remove extra bits. hash_long(hval, bits) has a nicer and more intuitive
> >> interface to handle integer.
> >
> > static inline uint64_t hash_64(uint64_t val, unsigned int bits)
> > {
> > uint64_t hash = fnv_64a_buf(&val, sizeof(uint64_t), FNV1A_64_INIT);
> >
> > return hash >> (64 - bits);
> > }
> >
> > Isn't this good for you?
> >
>
>
> I am not against it.
>
> >>
> >> How about coexisting these two? fnv_64a_buf() is supposed to handle
> >> string hash and hash_long() is supposed to handle integer otherwise.
> >
> > If you need a better randomized function for integers, I'm not against
> > introducing a new hash. But otherwise, FNV hash looks enough to me.
> >
>
>
> I really need an hash function that distribute OID to different hash
> lists, this is quite performance sensitive, since farm use it to lookup
> object hash table lists for every write operation to mark object dirty.
>
> mind do a test to show how well it perform on OID hash? If distributed
> randomly enough, I am happy to use it.
FNV hash is one of the famous hash functions. Although I don't know
its mathematical background so much, I think it would work well. Many
software use it. See also http://www.isthe.com/chongo/tech/comp/fnv/
Of course, testing would be appreciated. :)
Thanks,
Kazutaka
|
|