随机算法 (Fall 2011)/Cuckoo hashing and Carmichael number: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
(Created page with "=== Cuckoo hashing* === Cuckoo hashing also achieves constant search time on a linear space, and after acquiring the hash functions, the accesses to the table can be done in para…")
 
imported>Addbot
m (Bot: 21 interwiki links moved, now provided by Wikidata on d:q849530)
 
Line 1: Line 1:
=== Cuckoo hashing* ===
In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]].  
Cuckoo hashing also achieves constant search time on a linear space, and after acquiring the hash functions, the accesses to the table can be done in parallel. Cuckoo hashing is considered by some researchers as a more "modern" hashing technique than FKS.  


The data structure is defined as follows.
All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number.
 
{{Math-stub}}
For a set <math>S</math> of <math>n</math> items from the universe:
[[Category:Number theory]]
* A table <math>T</math> of <math>M</math> entries.
* Two hash functions <math>h_1</math> and <math>h_2</math> that map the universe <math>[N]</math> to <math>[M]</math> are stored separately in fixed places.
* For any item <math>x\in S</math>, either <math>T[h_1(x)]</math> or <math>T[h_2(x)]</math> stores <math>x</math>.
 
To search for an item <math>x</math>:
* Retrieve <math>h_1</math> and <math>h_2</math> from where they are stored.
* If <math>T[h_1(x)]=x</math>, returns <math>h_1(x)</math>; If <math>T[h_2(x)]=x</math>, returns <math>h_2(x)</math>; otherwise, return NOT_FOUND.
After retrieving the hash functions, it accesses the table twice, which can be done in parallel.
 
We only need to guarantee that it is possible to find a placement of the <math>n</math> items, such that
* each item is placed in one of the two entries it is hashed to;
* no two items are placed into one entry.
This problem can be formulated as a matching problem:
 
Suppose we have a bipartite graph, where there are <math>n</math> vertices on left and <math>M</math> vertices on right. Each vertex on left corresponds to an item and each vertex on right corresponds to a table entry. An edge connect an item vertex and an entry vertex if at least one of the two hash functions maps the item to the entry. With this reformulation, the problem of finding a feasible placement of items is reduced to finding a [http://en.wikipedia.org/wiki/Matching_(graph_theory) matching] (edge independent set) of size <math>n</math>.
 
It was shown by Pagh that such a matching exists with constant probability for linear table size <math>M=O(n)</math> when <math>h_1</math> and <math>h_2</math> are drawn uniformly and independently from a <math>O(\log n)</math>-universal family of hash functions. We will not describe the detailed proof here.

Latest revision as of 08:08, 11 March 2013

In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.

All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ n }[/math] is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. Template:Math-stub

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Cuckoo_hashing&oldid=7723"