<< Chapter < Page Chapter >> Page >

8.6. universal hashing

(From Wikipedia, the free encyclopedia)

Universal hashing is a randomized algorithm for selecting a hash function F with the following property: for any two distinct inputs x and y, the probability that F(x)=F(y) (i.e., that there is a hash collision between x and y) is the same as if F was a random function. Thus, if F has function values in a range of size r, the probability of any particular hash collision should be 1/r. There are universal hashing methods that give a function F that can be evaluated in a handful of computer instructions.

Introduction

Hashing has been used to associate with an input, usually a string, a small value that originally was used as an index to look up something about that input in a table. Since then hashing has found other uses. For example, two inputs might be compared by checking to see if their hash values are the same. Thus, we can see that hash functions are many-to-one mappings. The use of the word "hash" is mnemonic because the intent of a hash function is to take as many of the inputs usually encountered and assign different values to them, by scrambling them or making a hash of the inputs, using the meaning of hash from domains such as cooking. If for any given input there are too many collisions that is viewed as unfortunate.

Universal hashing

Because a hash function is a many-to-one mapping, there must exist some set of elements that will collide under the hash function. One wants to design the hash function such that for the input sets, it is unlikely that elements collide. Proving in a mathematical sense that you are unlikely to encounter a particular set of inputs would appear to be an impossible task.

Randomized algorithms present a way of proving that you are unlikely to encounter a bad set of inputs. We can construct a Universal Class of hash functions with the property that for any given set of inputs they will scatter the inputs among the range of the function well -- essentially as well as choosing random values for those inputs. Thus, simply choosing a random function from the class allows a proof that the probabilistic expectation for any set of inputs is that they will be distributed randomly.

In fact, we are in many cases interested in only pairwise collisions. That is to say, the odds that any two inputs x and y collide will be approximately the same as the reciprocal of the size of the range. It might be that for any given universal class of hash functions there exist x, y and z such that if x and y collide then so does z. While some work has been done on the set issue, universal hashing only makes statements about pairwise collisions.

Example

A simple universal class of hash function is all functions h of the form h(x)= f(g(x)), where g(x)=ax+b (mod p) with p being a prime guaranteed larger than any possible input and each combination of a and b forming a different function in the class. f then becomes a mapping function to map elements from a domain which is 0 to p to a range of say 0 to n-1. f then can simply be taking the result of g mod n. There is only one f for all the functions in this class. To see why this class is universal, observe that for any two inputs and any two outputs, there are approximately p/n elements that can map to any output and for any of pair of those p/n elements you can solve the simultaneous equations in the field mod p, so for any pair of inputs there is a unique pair of a and b that will take it to those elements.

Universal hashing has numerous uses in computer science, for example in cryptography and in implementations of hash tables . Since the function is randomly chosen, an adversary hoping to create many hash collisions is unlikely to succeed.

Universal hashing has been generalized in many ways, most notably to the notion of k-wise independent hash functions, where the function is required to act like a random function on any set of k inputs.

8.7. perfect hashing

(From Wikipedia, the free encyclopedia)

A Perfect hash function of a set S is a hash function which maps different keys (elements) in S to different numbers. A perfect hash function with values in a range of size some constant times the number of elements in S can be used for efficient lookup operations, by placing the keys in a hash table according to the values of the perfect hash function.

A perfect hash function for a specific set S that can be evaluated in constant time, and with values in a small range, can be found by a randomized algorithm in a number of operations that is proportional to the size of S. The minimal size of the description of a perfect hash function depends on the range of its function values: The smaller the range, the more space is required. Any perfect hash functions suitable for use with a hash table require at least a number of bits that is proportional to the size of S. Many common implementations require a number of bits that is proportional to n log(n), where n is the size of S. This means that the space for storing the perfect hash function can be comparable to the space for storing the set.

Using a perfect hash function is best in situations where there is a large set which is not updated frequently, and many lookups into it. Efficient solutions to performing updates are known as dynamic perfect hashing, but these methods are relatively complicated to implement. A simple alternative to perfect hashing, which also allows dynamic updates, is cuckoo hashing.

A minimal perfect hash function is a perfect hash function that maps n keys to n consecutive integers -- usually [0..n-1] or [1..n]. A more formal way of expressing this is: Let j and k be elements of some set K. F is a minimal perfect hash function if F(j) =F(k) implies j=k and there exists an integer a such that the range of F is a..a+|K|-1.

A minimal perfect hash function F is order-preserving if for any keys j and k, j<k implies F(j)<F(k).

Questions & Answers

Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
Renato
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
?
Kyle
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
Adin
why?
Adin
what school?
Kyle
biomolecules are e building blocks of every organics and inorganic materials.
Joe
anyone know any internet site where one can find nanotechnology papers?
Damian Reply
research.net
kanaga
sciencedirect big data base
Ernesto
Introduction about quantum dots in nanotechnology
Praveena Reply
what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
Bharti
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
Daniel
how to know photocatalytic properties of tio2 nanoparticles...what to do now
Akash Reply
it is a goid question and i want to know the answer as well
Maciej
characteristics of micro business
Abigail
for teaching engĺish at school how nano technology help us
Anassong
Do somebody tell me a best nano engineering book for beginners?
s. Reply
there is no specific books for beginners but there is book called principle of nanotechnology
NANO
what is fullerene does it is used to make bukky balls
Devang Reply
are you nano engineer ?
s.
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
Tarell
what is the actual application of fullerenes nowadays?
Damian
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
Tarell
what is the Synthesis, properties,and applications of carbon nano chemistry
Abhijith Reply
Mostly, they use nano carbon for electronics and for materials to be strengthened.
Virgil
is Bucky paper clear?
CYNTHIA
carbon nanotubes has various application in fuel cells membrane, current research on cancer drug,and in electronics MEMS and NEMS etc
NANO
so some one know about replacing silicon atom with phosphorous in semiconductors device?
s. Reply
Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.
Harper
Do you know which machine is used to that process?
s.
how to fabricate graphene ink ?
SUYASH Reply
for screen printed electrodes ?
SUYASH
What is lattice structure?
s. Reply
of graphene you mean?
Ebrahim
or in general
Ebrahim
in general
s.
Graphene has a hexagonal structure
tahir
On having this app for quite a bit time, Haven't realised there's a chat room in it.
Cied
what is biological synthesis of nanoparticles
Sanket Reply
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!





Source:  OpenStax, Data structures and algorithms. OpenStax CNX. Jul 29, 2009 Download for free at http://cnx.org/content/col10765/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Data structures and algorithms' conversation and receive update notifications?

Ask