data structures - Is Universal family of hash functions only to prevent enemy attack? -
if intention have hash function spreads data evenly of buckets, need not come family of hash functions, 1 hash function, correct?
the purpose of having family of hash functions make harder enemy build pathological data set when pick hash function randomly, he/she has no information hash function employed. understanding right?
edit: since trying close unclear; question know real purpose of employing universal family of hash functions.
i 1 hash function, correct?
as note later in question, "enemy" knows hash function you're using prepare pathological data set.
further, hashing first stage in storing data table's buckets - if you're implementing open addressing / closed hashing, need select alternative buckets probe after collisions: simple approaches linear , quadratic probing provide adequate collision avoidance, , mathematically simpler , therefore faster rehashing, don't maintain probability of next probe finding unused bucket @ load factor. rehashing good hash function (including family of such functions) does, if that's important you may prefer use family of hash functions.
note in-memory hash table used @ offsets/sectors on disk data stored, rehashing calculations already-in-memory data may far more appealing higher probability (with linear/quadratic probing) of waiting on disk i/o find collision.
Comments
Post a Comment