7742:. As long as zeroes are forbidden in the string, the zero-padding can be ignored when evaluating the hash function without affecting universality. Note that if zeroes are allowed in the string, then it might be best to append a fictitious non-zero (e.g., 1) character to all strings prior to padding: this will ensure that universality is not affected.
7240:
2537:, they hold if the data set is chosen by an adversary. However, the adversary has to make this choice before (or independent of) the algorithm's random choice of a hash function. If the adversary can observe the random choice of the algorithm, randomness serves no purpose, and the situation is the same as deterministic hashing.
1508:
is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e.g. hash tables), a careful distinction between the uniform distance
1773:
Several hash table implementations are based on universal hashing. In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over. (Some collision resolution
6877:
7692:
vector of machine words. If the length of the string can be bounded by a small number, it is best to use the vector solution from above (conceptually padding the vector with zeros up to the upper bound). The space required is the maximal length of the string, but the time to evaluate
7628:
8086:
4524:
scheme described by
Dietzfelbinger et al. in 1997. By avoiding modular arithmetic, this method is much easier to implement and also runs significantly faster in practice (usually by at least a factor of four). The scheme assumes the number of bins is a power of two,
43:, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of
6989:
2605:
Since any computer data can be represented as one or more machine words, one generally needs hash functions for three types of domains: machine words ("integers"); fixed-length vectors of machine words; and variable-length vectors ("strings").
511:
6466:
4863:
6693:
6066:
2614:
This section refers to the case of hashing integers that fit in machines words; thus, operations like multiplication, addition, division, etc. are cheap machine-level instructions. Let the universe to be hashed be
7434:
3623:
3801:
7938:
2810:
3346:
4243:
4456:
1376:
7810:
3056:
1512:
For some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal. When a family is strongly universal, this is guaranteed: if
8775:
6954:
6599:
6285:
5008:
4331:
7403:
1786:, allow a number of collisions before picking a new hash function). A survey of fastest known universal and strongly universal hash functions for integers, vectors, and strings is found in.
1462:
Given a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in
7235:{\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}
1087:
1754:
1210:
1027:
794:
6347:
is a universal family with the uniform difference property, the following family (dating back to Carter and Wegman) also has the uniform difference property (and hence is universal):
4060:
3488:
1605:
894:
8632:
8493:
5705:
5557:
5384:
5143:
4510:
8969:
8735:
8568:
8153:
6528:
In practice, if double-precision arithmetic is available, this is instantiated with the multiply-shift hash family of hash functions. Initialize the hash function with a vector
2667:
7930:
7306:
5813:
5763:
5223:
5183:
5091:
5051:
163:
3994:
3895:
2380:
287:
686:
5868:
5601:
2937:
1662:
1437:
368:
189:
6181:
6125:
5916:
5479:
1276:
974:
8905:
6499:
4609:
2235:
2166:
7889:
5332:
3695:
3175:
2981:
2706:
2122:
2076:
706:
8191:
4665:
1770:
algorithms are based on universal hashing. In such applications, the software chooses a new hash function for every message, based on a unique nonce for that message.
653:
8700:
6685:
6659:
4927:
4556:
4357:
4091:
3201:
3139:
2885:
2032:
1563:
1133:
5505:
4154:
4128:
3930:
2511:
2417:
1697:
1631:
622:
8999:
8932:
8652:
8533:
8513:
8118:
7830:
4732:
2291:
225:
7720:
7678:
5945:
2571:
2446:
2264:
1905:
7272:
5653:
5627:
5430:
5275:
5249:
4899:
3831:
3422:
3376:
3227:
2839:
2474:
1986:
1933:
1236:
734:
542:
7426:
6981:
6626:
6204:
8866:
8842:
8795:
8672:
8588:
7850:
7740:
7652:
7326:
6523:
6345:
6325:
6305:
6145:
6089:
5404:
5295:
4752:
4705:
4685:
4629:
4576:
3950:
3851:
3647:
3442:
3396:
3267:
3247:
3099:
3079:
2859:
2591:
2535:
2314:
2206:
2186:
2006:
1957:
1876:
1856:
1832:
1812:
1530:
1506:
1457:
1153:
834:
814:
582:
562:
307:
245:
107:
87:
6883:
It is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice. Initialize the hash function with a vector
1486:
1113:
920:
377:
9735:
6353:
4760:
317:: sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function.
7331:
The same scheme can also be used for hashing integers, by interpreting their bits as vectors of bytes. In this variant, the vector technique is known as
8937:
One can apply vector hashing to blocks. For instance, one applies vector hashing to each 16-word block of the string, and applies string hashing to the
6872:{\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}
39:
at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in
313:
of a bin. This means that all data keys land in the same bin, making hashing useless. Furthermore, a deterministic hash function does not allow for
9666:
5953:
8868:
to be implemented without division (using faster operations like addition and shifts). For instance, on modern architectures one can work with
7623:{\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}
3496:
8971:
results. Since the slower string hashing is applied on a substantially smaller vector, this will essentially be as fast as vector hashing.
8081:{\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}
3703:
584:. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key.
9769:
9477:
9245:
6206:-bit unsigned integers. This version of multiply-shift is due to Dietzfelbinger, and was later analyzed more precisely by Woelfel.
2714:
3275:
655:. This concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for
9754:
9413:
4165:
8197:
Using properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:
4362:
1664:. Unfortunately, the same is not true of (merely) universal families. For example, the family made of the identity function
9134:
1281:
7328:
was the number of half-words in the vector. Thus, the algorithm runs at a "rate" of one multiplication per word of input.
9335:
7748:
2989:
9052: – type of universal hash function in cryptography proposed as an alternative to collision-resistant hash functions
8804:
Other universal families of hash functions used to hash unknown-length strings to fixed-length hash values include the
8740:
6886:
6531:
6217:
5947:. To obtain a truly 'universal' hash function, one can use the multiply-add-shift scheme that picks higher-order bits
4932:
4255:
9719:
9650:
9515:
9175:
7341:
320:
The solution to these problems is to pick a function randomly from a family of hash functions. A family of functions
227:
keys, which is not known in advance. Usually, the goal of hashing is to obtain a low number of collisions (keys from
1032:
247:
that land in the same bin). A deterministic hash function cannot offer any guarantee in an adversarial setting if
9049:
8515:
be length of the longer one; for the analysis, the shorter string is conceptually padded with zeros up to length
6214:
This section is concerned with hashing a fixed-length vector of machine words. Interpret the input as a vector
1165:
982:
749:
3999:
8347:
4578:
be the number of bits in a machine word. Then the hash functions are parametrised over odd positive integers
3447:
2888:
9680:
1702:
839:
8593:
8454:
5658:
5510:
5337:
5096:
8797:
is sufficiently large compared to the length of strings hashed, the family is very close to universal (in
4461:
7246:
If double-precision operations are not available, one can interpret the input as a vector of half-words (
1767:
8940:
8705:
8538:
8123:
2618:
1778:, pick a new hash function every time there is a collision. Other collision resolution schemes, such as
9764:
7894:
7277:
5768:
5710:
5188:
5148:
5056:
5016:
1568:
1381:
Another property is uniformity. We say that a family is uniform if all hash values are equally likely:
112:
3955:
3856:
2319:
250:
9396:
7654:
bits. Experimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for
665:
9058:
8343:
5818:
5562:
2897:
1384:
323:
168:
6150:
6094:
5876:
5435:
1775:
1241:
929:
8871:
8820:
To mitigate the computational penalty of modular arithmetic, three tricks are used in practice:
6471:
4581:
2211:
2127:
587:
Sometimes, the definition is relaxed by a constant factor, only requiring collision probability
9571:
9391:
7855:
7338:
Strong universality at high speed is also possible. Initialize the hash function with a vector
5303:
3656:
3144:
2942:
2675:
2594:
2081:
2037:
1459:. Universality does not imply uniformity. However, strong universality does imply uniformity.
691:
9642:
9633:
8158:
4634:
1636:
627:
9353:. Mathematical Foundations of Computer Science 1999. LNCS. Vol. 1672. pp. 262–272.
9040:
9019:
8677:
8362:
can be avoided altogether by simply allowing integer to overflow because it is equivalent to
6664:
6631:
4906:
4528:
4336:
4065:
3180:
3104:
2864:
2011:
1939:, this number is proportional to the expected running time of an operation involving the key
1535:
1118:
5484:
4133:
4096:
3900:
2479:
2385:
1667:
1610:
590:
8977:
8910:
8798:
8637:
8518:
8498:
8091:
7815:
7335:
and it provides a practical alternative to multiplication-based universal hashing schemes.
4710:
3650:
2269:
1159:
194:
48:
32:
9453:
7696:
7657:
5921:
2547:
2422:
2240:
1881:
8:
8391:
7249:
5632:
5606:
5409:
5254:
5228:
4876:
3810:
3401:
3355:
3206:
2818:
2593:
from the family and repeats. Universality guarantees that the number of repetitions is a
2451:
1965:
1910:
1215:
711:
519:
310:
7408:
6963:
6608:
6186:
516:
In other words, any two different keys of the universe collide with probability at most
9660:
9543:
9493:
9272:
9249:
9221:
9034:
8851:
8827:
8780:
8657:
8573:
7835:
7725:
7637:
7332:
7311:
6508:
6330:
6310:
6290:
6130:
6074:
5389:
5298:
5280:
4737:
4690:
4670:
4614:
4561:
3935:
3836:
3632:
3427:
3381:
3252:
3232:
3084:
3064:
2844:
2576:
2520:
2299:
2191:
2171:
1991:
1942:
1861:
1841:
1817:
1797:
1515:
1491:
1442:
1138:
819:
799:
567:
547:
506:{\displaystyle \forall x,y\in U,~x\neq y:~~|\{h\in H:h(x)=h(y)\}|\leq {\frac {|H|}{m}}}
292:
230:
92:
72:
9290:
Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997).
6461:{\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}
4858:{\displaystyle h_{a}(x)=(a\cdot x\,\,{\bmod {\,}}2^{w})\,\,\mathrm {div} \,\,2^{w-M}.}
1465:
1092:
899:
9715:
9646:
9511:
9409:
9171:
9118:
9101:
8805:
2448:. This only holds with a hash family whose collision probability is bounded above by
1936:
3490:
possible non-zero values for the right hand side. Thus the collision probability is
2573:
number of collisions. If it observes too many collisions, it chooses another random
9759:
9553:
9503:
9401:
9354:
9306:
9276:
9264:
9113:
9006:
1783:
9588:
9439:
Proc. 19th
International Colloquium on Automata, Languages and Programming (ICALP)
9291:
8370:+ 1) in many programming languages. Below table shows values chosen to initialize
4093:
between the samples. As a result, the statistical distance to a uniform family is
9534:
Kaser, Owen; Lemire, Daniel (2013). "Strongly universal string hashing is fast".
9204:
9191:
9064:
9025:
8419:
9433:
Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992).
9141:
5145:
has either all 1's or all 0's as its highest order M bits (depending on whether
9405:
9097:
8845:
8423:
5432:. The probability that these bits are all 0's or all 1's is therefore at most
2541:
2382:. Thus, if the capacity of each bin is capped to three times the average size (
1779:
40:
9490:
Proceedings of the 43rd annual ACM Symposium on Theory of
Computing (STOC '11)
9268:
9748:
9481:
9379:
9358:
9331:
9217:
64:
36:
9557:
9507:
6061:{\displaystyle h_{a,b}(x)=((ax+b){\bmod {2}}^{w+M})\,\mathrm {div} \,2^{w},}
9707:
9310:
1763:
52:
7832:
is not known a priori. A universal family proposed by treats the string
9002:
4359:. Moreover, this analysis is nearly tight; Carter and Wegman show that
20:
9617:
9602:
9289:
976:, which counts collisions. The uniform difference property is stronger.
926:
Note that the definition of universality is only concerned with whether
44:
8974:
One chooses a power-of-two as the divisor, allowing arithmetic modulo
2544:. For instance, a randomized algorithm may be prepared to handle some
2540:
The second and third guarantee are typically used in conjunction with
2293:
bins, there are no collisions at all with probability at least a half.
9739:
3618:{\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}
24:
1834:
keys, using a universal family guarantees the following properties.
9226:
9548:
9498:
8155:
is chosen randomly from a universal family mapping integer domain
5013:
To understand the behavior of the hash function, notice that, if
739:
Many, but not all, universal families have the following stronger
8809:
1378:. Pairwise independence is sometimes called strong universality.
9712:
The Art of
Computer Programming, Vol. III: Sorting and Searching
9432:
9203:
Jean-Philippe
Aumasson, Willi Meier, Raphael Phan, Luca Henzen.
3796:{\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}
1135:
is the bitwise exclusive or operation. This is only possible if
9001:
to be implemented without division (using faster operations of
2672:
The original proposal of Carter and Wegman was to pick a prime
9292:"A Reliable Randomized Algorithm for the Closest-Pair Problem"
6525:
is a power of two, one may replace summation by exclusive or.
5297:
is a random odd integer and odd integers have inverses in the
9736:
Open Data
Structures - Section 5.1.1 - Multiplicative Hashing
8061:
7852:
as the coefficients of a polynomial modulo a large prime. If
7570:
7171:
6808:
6446:
6008:
5682:
5534:
5406:-bit integers with the least significant set bit on position
5361:
5200:
5160:
5120:
5068:
5028:
4801:
4484:
4223:
4204:
4062:
is thus almost uniform, up to a difference in probability of
4040:
3762:
2805:{\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m}
2790:
2771:
1725:
1576:
1067:
874:
708:-almost universality. So for example, a universal family has
9351:
Efficient
Strongly Universal and Optimally Universal Hashing
9388:
Proc. 20th ACM-SIAM Symposium on
Discrete Algorithms (SODA)
3341:{\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}
2419:), the total number of keys in overflowing bins is at most
1759:
9451:
9435:
Polynomial Hash
Functions Are Reliable (Extended Abstract)
1699:
is clearly universal, but the family made of the function
9452:
Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999).
5873:
This analysis is tight, as can be shown with the example
5225:
is larger). Assume that the least significant set bit of
4754:
bits as the hash code. In mathematical notation, this is
1509:
property and pairwise independent is sometimes not made.
9714:(3rd ed.). Reading, Mass; London: Addison-Wesley.
9220:(2015). "High Speed Hashing for Integers and Strings".
9069:
Pages displaying short descriptions of redirect targets
9045:
Pages displaying short descriptions of redirect targets
9030:
Pages displaying short descriptions of redirect targets
4238:{\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}
979:(Similarly, a universal family can be XOR universal if
4451:{\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m+1)}
8980:
8943:
8913:
8874:
8854:
8830:
8783:
8743:
8708:
8680:
8660:
8640:
8596:
8576:
8541:
8521:
8501:
8457:
8161:
8126:
8094:
7941:
7897:
7858:
7838:
7818:
7751:
7728:
7699:
7660:
7640:
7437:
7411:
7344:
7314:
7280:
7252:
6992:
6966:
6889:
6696:
6667:
6634:
6611:
6534:
6511:
6474:
6356:
6333:
6313:
6293:
6220:
6189:
6153:
6133:
6097:
6077:
5956:
5924:
5879:
5821:
5771:
5713:
5661:
5635:
5609:
5565:
5513:
5487:
5438:
5412:
5392:
5340:
5306:
5283:
5257:
5231:
5191:
5151:
5099:
5059:
5019:
4935:
4909:
4879:
4763:
4740:
4713:
4693:
4673:
4637:
4617:
4584:
4564:
4531:
4464:
4365:
4339:
4258:
4168:
4136:
4099:
4068:
4002:
3958:
3938:
3903:
3859:
3839:
3813:
3706:
3659:
3635:
3499:
3450:
3430:
3404:
3384:
3358:
3278:
3255:
3235:
3209:
3183:
3147:
3107:
3087:
3067:
2992:
2945:
2900:
2867:
2847:
2821:
2717:
2678:
2621:
2579:
2550:
2523:
2482:
2454:
2425:
2388:
2322:
2302:
2272:
2243:
2214:
2194:
2174:
2130:
2084:
2040:
2014:
1994:
1968:
1945:
1913:
1884:
1864:
1844:
1820:
1800:
1705:
1670:
1639:
1613:
1571:
1538:
1518:
1494:
1468:
1445:
1387:
1371:{\displaystyle P(h(x)=z_{1}\land h(y)=z_{2})=1/m^{2}}
1284:
1244:
1218:
1168:
1141:
1121:
1095:
1035:
985:
932:
902:
842:
822:
802:
752:
714:
694:
668:
630:
593:
570:
550:
522:
380:
326:
295:
253:
233:
197:
171:
115:
95:
75:
9243:
9054:
Pages displaying wikidata descriptions as a fallback
4872:
satisfy the uniform difference property and is only
7805:{\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}
6983:bits each. The following hash family is universal:
3051:{\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}
165:). The algorithm will have to handle some data set
9632:
9630:
8993:
8963:
8926:
8899:
8860:
8836:
8789:
8769:
8729:
8702:. The probability of collision through the random
8694:
8666:
8646:
8626:
8582:
8562:
8527:
8507:
8487:
8185:
8147:
8112:
8080:
7924:
7883:
7844:
7824:
7804:
7734:
7714:
7672:
7646:
7622:
7420:
7397:
7320:
7300:
7266:
7234:
6975:
6948:
6871:
6679:
6653:
6620:
6593:
6517:
6493:
6460:
6339:
6319:
6299:
6279:
6198:
6175:
6139:
6119:
6083:
6060:
5939:
5910:
5862:
5807:
5757:
5699:
5647:
5621:
5595:
5551:
5499:
5473:
5424:
5398:
5378:
5326:
5289:
5269:
5243:
5217:
5177:
5137:
5085:
5045:
5002:
4921:
4893:
4857:
4746:
4726:
4699:
4679:
4659:
4623:
4603:
4570:
4550:
4504:
4450:
4351:
4325:
4237:
4148:
4122:
4085:
4054:
3988:
3944:
3924:
3889:
3845:
3825:
3795:
3689:
3641:
3617:
3482:
3436:
3416:
3390:
3370:
3340:
3261:
3241:
3221:
3195:
3169:
3133:
3093:
3073:
3050:
2975:
2931:
2879:
2853:
2833:
2804:
2700:
2661:
2585:
2565:
2529:
2505:
2468:
2440:
2411:
2374:
2308:
2296:The expected number of keys in bins with at least
2285:
2258:
2229:
2200:
2180:
2160:
2116:
2070:
2026:
2000:
1980:
1951:
1927:
1899:
1870:
1850:
1826:
1806:
1748:
1691:
1656:
1625:
1599:
1557:
1524:
1500:
1480:
1451:
1431:
1370:
1270:
1230:
1204:
1147:
1127:
1107:
1081:
1021:
968:
914:
888:
828:
808:
788:
728:
700:
688:on the collision probability, we say that we have
680:
647:
616:
576:
556:
536:
505:
362:
301:
281:
239:
219:
183:
157:
101:
81:
8770:{\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}
7165:
7038:
6949:{\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}
6594:{\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}
6280:{\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}
5559:contain both 0's and 1's, so it is certain that
4520:The state of the art for hashing integers is the
2476:. If a weaker definition is used, bounding it by
9746:
8815:
7904:
5003:{\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}
4936:
4366:
4326:{\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}
4259:
9165:
9037: – Hash functions computed by exclusive or
8374:and a for some of the popular implementations.
7398:{\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}
2517:As the above guarantees hold for any fixed set
9476:
8590:is a root of the polynomial with coefficients
4515:
69:Assume we want to map keys from some universe
9166:Motwani, Rajeev; Raghavan, Prabhakar (1995).
8055:
7998:
6799:
6742:
1959:(for example a query, insertion or deletion).
9665:: CS1 maint: multiple names: authors list (
9529:
9527:
9455:UMAC: Fast and Secure Message Authentication
9095:
9067: – Hash function without any collisions
8958:
8944:
7919:
7907:
7295:
7281:
7274:-bit integers). The algorithm will then use
7073:
7059:
4983:
4939:
4419:
4369:
4306:
4262:
3983:
3959:
3884:
3860:
3526:
3500:
3477:
3451:
2926:
2907:
2656:
2622:
1082:{\displaystyle h(x)\oplus h(y)~{\bmod {~}}m}
470:
428:
357:
333:
152:
128:
9533:
9374:
9372:
9370:
9368:
9170:. Cambridge University Press. p. 221.
5815:are also 1, which happens with probability
5093:have the same highest-order 'M' bits, then
3649:is a universal family is via the notion of
9542:(11). Oxford University Press: 1624–1638.
8737:brings the total collision probability to
8674:, so the collision probability is at most
1789:
9603:"Hash functions: An empirical comparison"
9547:
9524:
9497:
9395:
9225:
9117:
8844:to be close to a power of two, such as a
7609:
7608:
7596:
7595:
7212:
7211:
7199:
7198:
6849:
6848:
6836:
6835:
6628:bits each. Then if the number of bins is
6444:
6044:
6032:
4835:
4834:
4822:
4821:
4805:
4799:
4798:
1878:, the expected number of keys in the bin
1205:{\displaystyle \forall x,y\in U,~x\neq y}
1022:{\displaystyle \forall x,y\in U,~x\neq y}
789:{\displaystyle \forall x,y\in U,~x\neq y}
35:or data structure) refers to selecting a
9641:(2nd ed.). Prentice Hall. pp.
9365:
9126:
4055:{\displaystyle (h(x)-h(y))~{\bmod {~}}m}
2237:), the expected number of collisions is
1565:, then the family made of the functions
9428:
9426:
9348:
9106:Journal of Computer and System Sciences
3483:{\displaystyle \lfloor (p-1)/m\rfloor }
9747:
9486:The power of simple tabulation hashing
9378:
9330:
9216:
9192:"Advances in Cryptology - CRYPTO 2008"
9091:
9089:
9087:
9085:
9083:
6147:is a random non-negative integer with
2208:(i.e., is determined by a function in
1749:{\displaystyle h(x)=x{\bmod {2^{L'}}}}
1488:to the hash functions. (Similarly, if
889:{\displaystyle h(x)-h(y)~{\bmod {~}}m}
16:Technique for selecting hash functions
9706:
9445:
9283:
9239:
9237:
9132:
9102:"Universal Classes of Hash Functions"
9061: – Type of mathematical sequence
8627:{\displaystyle {\bar {x}}-{\bar {y}}}
8488:{\displaystyle {\bar {x}},{\bar {y}}}
5700:{\displaystyle a(x-y){\bmod {2}}^{w}}
5552:{\displaystyle a(x-y){\bmod {2}}^{w}}
5379:{\displaystyle a(x-y){\bmod {2}}^{w}}
5138:{\displaystyle a(x-y){\bmod {2}}^{w}}
4159:The family of simpler hash functions
3229:is nonzero and has an inverse modulo
1962:The expected number of pairs of keys
1278:is as if they were perfectly random:
1238:will hash to any pair of hash values
9600:
9423:
7634:The result is strongly universal on
6183:. This requires doing arithmetic on
5386:will be uniformly distributed among
4505:{\displaystyle (p-1)~{\bmod {~}}m=1}
2887:. (This is a single iteration of a
2841:are randomly chosen integers modulo
1532:is a strongly universal family with
9463:Advances in Cryptology (CRYPTO '99)
9342:
9080:
8350:. Above algorithm is also known as
3785:
3330:
3040:
2609:
1935:. When implementing hash tables by
13:
9700:
9250:"Subquadratic Algorithms for 3SUM"
9234:
8964:{\displaystyle \lceil k/16\rceil }
8730:{\displaystyle h_{\mathrm {int} }}
8721:
8718:
8715:
8563:{\displaystyle h_{\mathrm {int} }}
8554:
8551:
8548:
8148:{\displaystyle h_{\mathrm {int} }}
8139:
8136:
8133:
7985:
7982:
7979:
7683:
7604:
7601:
7598:
7491:
7488:
7485:
7482:
7479:
7476:
7207:
7204:
7201:
6844:
6841:
6838:
6501:is chosen independently at random.
6209:
6091:is a random positive integer with
6040:
6037:
6034:
4830:
4827:
4824:
2662:{\displaystyle \{0,\dots ,|U|-1\}}
2215:
1169:
986:
816:is drawn randomly from the family
753:
564:is drawn uniformly at random from
381:
14:
9781:
9729:
9615:
9572:"Hebrew University Course Slides"
9384:String hashing for linear probing
7925:{\displaystyle p\geq \max\{u,m\}}
7301:{\displaystyle \lceil k/2\rceil }
5808:{\displaystyle w-1,\ldots ,w-M+1}
5758:{\displaystyle h_{a}(x)=h_{a}(y)}
5218:{\displaystyle ay{\bmod {2}}^{w}}
5178:{\displaystyle ax{\bmod {2}}^{w}}
5086:{\displaystyle ay{\bmod {2}}^{w}}
5046:{\displaystyle ax{\bmod {2}}^{w}}
3952:is also uniformly distributed in
2939:is a universal family, note that
2316:keys in them is bounded above by
1600:{\displaystyle h{\bmod {2^{L'}}}}
289:, since the adversary may choose
158:{\displaystyle =\{0,\dots ,m-1\}}
9122:. Conference version in STOC'77.
9022: – Family of Hash functions
8848:. This allows arithmetic modulo
4130:, which becomes negligible when
3989:{\displaystyle \{1,\dots ,p-1\}}
3890:{\displaystyle \{1,\dots ,p-1\}}
2600:
2513:, this result is no longer true.
9770:Computational complexity theory
9673:
9624:
9609:
9594:
9581:
9564:
9470:
9244:Baran, Ilya; Demaine, Erik D.;
9050:Universal one-way hash function
5507:, then higher-order M bits of
3778:
3323:
3033:
2375:{\displaystyle 2n/(t-2(n/m)+1)}
1633:is also strongly universal for
282:{\displaystyle |U|>m\cdot n}
58:
9336:"Text-book algorithms at SODA"
9324:
9210:
9197:
9184:
9159:
8634:. This polynomial has at most
8618:
8603:
8535:. A collision before applying
8479:
8464:
8180:
8174:
8171:
8168:
8162:
8107:
8101:
7967:
7961:
7952:
7878:
7872:
7799:
7767:
7758:
7709:
7703:
7592:
7500:
7471:
7464:
7455:
7448:
7392:
7360:
7351:
7160:
7116:
7110:
7078:
7025:
7019:
7010:
7003:
6943:
6905:
6896:
6729:
6723:
6714:
6707:
6588:
6550:
6541:
6436:
6423:
6375:
6369:
6360:
6274:
6236:
6227:
6029:
6003:
5988:
5985:
5979:
5973:
5752:
5746:
5730:
5724:
5677:
5665:
5590:
5584:
5575:
5569:
5529:
5517:
5356:
5344:
5115:
5103:
4980:
4974:
4958:
4952:
4818:
4786:
4780:
4774:
4654:
4648:
4477:
4465:
4445:
4433:
4416:
4404:
4388:
4382:
4303:
4297:
4281:
4275:
4216:
4191:
4185:
4179:
4117:
4103:
4033:
4030:
4024:
4015:
4009:
4003:
3919:
3907:
3789:
3779:
3774:
3755:
3743:
3737:
3731:
3725:
3716:
3710:
3684:
3678:
3669:
3663:
3598:
3586:
3578:
3567:
3555:
3552:
3546:
3534:
3515:
3503:
3466:
3454:
3334:
3324:
3310:
3297:
3163:
3155:
3120:
3108:
3044:
3034:
2970:
2964:
2955:
2949:
2783:
2764:
2749:
2746:
2740:
2734:
2694:
2686:
2646:
2638:
2560:
2554:
2500:
2486:
2435:
2429:
2369:
2360:
2346:
2334:
2253:
2247:
2224:
2218:
2155:
2134:
2100:
2088:
2065:
2059:
2050:
2044:
1894:
1888:
1715:
1709:
1680:
1674:
1475:
1469:
1412:
1403:
1397:
1391:
1344:
1328:
1322:
1300:
1294:
1288:
1162:: we have this property when
1158:An even stronger condition is
1102:
1096:
1060:
1054:
1045:
1039:
957:
951:
942:
936:
909:
903:
867:
861:
852:
846:
681:{\displaystyle \epsilon <1}
611:
597:
493:
485:
474:
467:
461:
452:
446:
424:
354:
348:
345:
263:
255:
207:
199:
122:
116:
1:
9681:"String (Java Platform SE 6)"
9074:
9043: – Data mining technique
9028: – Type of hash function
8348:linear congruential generator
5863:{\displaystyle 1/2^{M-1}=2/m}
5596:{\displaystyle h(x)\neq h(y)}
4734:and then keep the high order
2932:{\displaystyle H=\{h_{a,b}\}}
2889:linear congruential generator
1432:{\displaystyle P(h(x)=z)=1/m}
1212:we have the probability that
662:If we have an upper bound of
363:{\displaystyle H=\{h:U\to \}}
9755:Cryptographic hash functions
9119:10.1016/0022-0000(79)90044-8
8352:Multiplicative hash function
3853:is uniformly distributed in
1089:is uniformly distributed in
896:is uniformly distributed in
184:{\displaystyle S\subseteq U}
7:
9631:Kernighan; Ritchie (1988).
9013:
8816:Avoiding modular arithmetic
8438:java.lang.String.hashCode()
8358:operator and the parameter
7745:Now assume we want to hash
6307:machine words (integers of
6176:{\displaystyle b<2^{2w}}
6120:{\displaystyle a<2^{2w}}
5911:{\displaystyle x=2^{w-M-2}}
5474:{\displaystyle 2/2^{M}=2/m}
4516:Avoiding modular arithmetic
2168:. When the number of bins,
1768:message authentication code
1271:{\displaystyle z_{1},z_{2}}
969:{\displaystyle h(x)-h(y)=0}
741:uniform difference property
10:
9786:
9639:The C Programming Language
9406:10.1137/1.9781611973068.72
8900:{\displaystyle p=2^{61}-1}
6494:{\displaystyle h_{i}\in H}
4604:{\displaystyle a<2^{w}}
3424:is excluded) and, varying
2230:{\displaystyle \Omega (n)}
2161:{\displaystyle O(n^{2}/m)}
62:
9349:Woelfel, Philipp (1999).
9269:10.1007/s00453-007-9036-3
9205:"The Hash Function BLAKE"
7884:{\displaystyle x_{i}\in }
7688:This refers to hashing a
5327:{\displaystyle Z_{2^{w}}}
3690:{\displaystyle h(x)-h(y)}
3170:{\displaystyle p\geq |U|}
2976:{\displaystyle h(x)=h(y)}
2701:{\displaystyle p\geq |U|}
2595:geometric random variable
2117:{\displaystyle n(n-1)/2m}
2071:{\displaystyle h(x)=h(y)}
701:{\displaystyle \epsilon }
9589:"Library Hash Functions"
9359:10.1007/3-540-48340-3_24
9059:Low-discrepancy sequence
8199:
8186:{\displaystyle \mapsto }
8120:is uniformly random and
7812:, where a good bound on
5481:. On the other hand, if
4660:{\displaystyle h_{a}(x)}
1657:{\displaystyle L'\leq L}
648:{\displaystyle \leq 1/m}
9618:"String hash functions"
9508:10.1145/1993636.1993638
9007:NH hash-function family
8695:{\displaystyle \ell /p}
8344:Rabin-Karp rolling hash
7932:be a prime and define:
7405:of random integers on
7308:multiplications, where
6680:{\displaystyle M\leq w}
6654:{\displaystyle m=2^{M}}
4922:{\displaystyle x\neq y}
4611:(that fit in a word of
4551:{\displaystyle m=2^{M}}
4352:{\displaystyle x\neq y}
4086:{\displaystyle \pm 1/p}
3653:. Write the difference
3196:{\displaystyle x\neq y}
3134:{\displaystyle (p-1)/m}
2880:{\displaystyle a\neq 0}
2027:{\displaystyle x\neq y}
1790:Mathematical guarantees
1776:dynamic perfect hashing
1756:fails to be universal.
1558:{\displaystyle m=2^{L}}
1128:{\displaystyle \oplus }
544:when the hash function
9311:10.1006/jagm.1997.0873
9133:Miltersen, Peter Bro.
8995:
8965:
8928:
8901:
8862:
8838:
8824:One chooses the prime
8791:
8771:
8731:
8696:
8668:
8648:
8628:
8584:
8564:
8529:
8509:
8489:
8187:
8149:
8114:
8082:
8023:
7926:
7885:
7846:
7826:
7806:
7736:
7722:is just the length of
7716:
7674:
7648:
7624:
7542:
7422:
7399:
7322:
7302:
7268:
7236:
7077:
6977:
6950:
6873:
6773:
6681:
6655:
6622:
6595:
6519:
6495:
6462:
6412:
6341:
6321:
6301:
6281:
6200:
6177:
6141:
6121:
6085:
6062:
5941:
5912:
5864:
5809:
5759:
5701:
5649:
5623:
5597:
5553:
5501:
5500:{\displaystyle c<M}
5475:
5426:
5400:
5380:
5328:
5291:
5271:
5245:
5219:
5179:
5139:
5087:
5047:
5004:
4923:
4895:
4859:
4748:
4728:
4701:
4681:
4661:
4625:
4605:
4572:
4552:
4506:
4452:
4353:
4327:
4239:
4150:
4149:{\displaystyle p\gg m}
4124:
4123:{\displaystyle O(m/p)}
4087:
4056:
3996:. The distribution of
3990:
3946:
3926:
3925:{\displaystyle a(x-y)}
3891:
3847:
3827:
3797:
3691:
3643:
3619:
3484:
3444:in the allowed range,
3438:
3418:
3392:
3372:
3342:
3263:
3243:
3223:
3197:
3171:
3135:
3095:
3075:
3052:
2977:
2933:
2881:
2855:
2835:
2806:
2702:
2663:
2587:
2567:
2531:
2507:
2506:{\displaystyle O(1/m)}
2470:
2442:
2413:
2412:{\displaystyle t=3n/m}
2376:
2310:
2287:
2260:
2231:
2202:
2182:
2162:
2118:
2078:) is bounded above by
2072:
2028:
2002:
1982:
1953:
1929:
1901:
1872:
1852:
1828:
1808:
1750:
1693:
1692:{\displaystyle h(x)=x}
1658:
1627:
1626:{\displaystyle h\in H}
1601:
1559:
1526:
1502:
1482:
1453:
1433:
1372:
1272:
1232:
1206:
1149:
1129:
1109:
1083:
1023:
970:
916:
890:
830:
810:
790:
736:-almost universality.
730:
702:
682:
649:
618:
617:{\displaystyle O(1/m)}
578:
558:
538:
507:
364:
303:
283:
241:
221:
185:
159:
103:
83:
9558:10.1093/comjnl/bxt070
9299:Journal of Algorithms
9168:Randomized Algorithms
9041:Min-wise independence
9020:K-independent hashing
8996:
8994:{\displaystyle 2^{w}}
8966:
8934:'s are 32-bit values.
8929:
8927:{\displaystyle x_{i}}
8902:
8863:
8839:
8792:
8777:. Thus, if the prime
8772:
8732:
8697:
8669:
8649:
8647:{\displaystyle \ell }
8629:
8585:
8565:
8530:
8528:{\displaystyle \ell }
8510:
8508:{\displaystyle \ell }
8490:
8451:Consider two strings
8188:
8150:
8115:
8113:{\displaystyle a\in }
8083:
8003:
7927:
7886:
7847:
7827:
7825:{\displaystyle \ell }
7807:
7737:
7717:
7675:
7649:
7625:
7516:
7423:
7400:
7323:
7303:
7269:
7237:
7043:
6978:
6951:
6874:
6747:
6682:
6656:
6623:
6596:
6520:
6496:
6463:
6386:
6342:
6322:
6302:
6282:
6201:
6178:
6142:
6122:
6086:
6063:
5942:
5913:
5865:
5810:
5760:
5702:
5650:
5624:
5598:
5554:
5502:
5476:
5427:
5401:
5381:
5329:
5292:
5272:
5246:
5220:
5180:
5140:
5088:
5048:
5005:
4924:
4896:
4860:
4749:
4729:
4727:{\displaystyle 2^{w}}
4702:
4682:
4662:
4626:
4606:
4573:
4553:
4507:
4453:
4354:
4328:
4240:
4151:
4125:
4088:
4057:
3991:
3947:
3927:
3892:
3848:
3828:
3798:
3692:
3644:
3620:
3485:
3439:
3419:
3393:
3378:possible choices for
3373:
3343:
3264:
3244:
3224:
3198:
3172:
3136:
3096:
3076:
3053:
2978:
2934:
2882:
2856:
2836:
2807:
2703:
2664:
2588:
2568:
2532:
2508:
2471:
2443:
2414:
2377:
2311:
2288:
2286:{\displaystyle n^{2}}
2261:
2232:
2203:
2183:
2163:
2119:
2073:
2029:
2003:
1983:
1954:
1930:
1902:
1873:
1853:
1829:
1809:
1751:
1694:
1659:
1628:
1602:
1560:
1527:
1503:
1483:
1454:
1434:
1373:
1273:
1233:
1207:
1160:pairwise independence
1150:
1130:
1110:
1084:
1024:
971:
917:
891:
831:
811:
791:
731:
703:
683:
650:
619:
579:
559:
539:
508:
365:
304:
284:
242:
222:
220:{\displaystyle |S|=n}
186:
160:
104:
84:
49:randomized algorithms
9390:. pp. 655–664.
9334:(18 December 2009).
9009:takes this approach.
8978:
8941:
8911:
8872:
8852:
8828:
8799:statistical distance
8781:
8741:
8706:
8678:
8658:
8638:
8594:
8574:
8539:
8519:
8499:
8455:
8159:
8124:
8092:
7939:
7895:
7856:
7836:
7816:
7749:
7726:
7715:{\displaystyle h(s)}
7697:
7673:{\displaystyle w=32}
7658:
7638:
7435:
7409:
7342:
7312:
7278:
7250:
6990:
6964:
6887:
6694:
6665:
6632:
6609:
6532:
6509:
6472:
6354:
6331:
6311:
6291:
6218:
6187:
6151:
6131:
6095:
6075:
5954:
5940:{\displaystyle y=3x}
5922:
5877:
5819:
5769:
5765:if and only if bits
5711:
5659:
5633:
5607:
5563:
5511:
5485:
5436:
5410:
5390:
5338:
5304:
5281:
5255:
5251:appears on position
5229:
5189:
5149:
5097:
5057:
5017:
4933:
4907:
4877:
4761:
4738:
4711:
4691:
4671:
4635:
4615:
4582:
4562:
4529:
4462:
4363:
4337:
4256:
4166:
4134:
4097:
4066:
4000:
3956:
3936:
3901:
3857:
3837:
3811:
3704:
3657:
3651:statistical distance
3633:
3497:
3448:
3428:
3402:
3382:
3356:
3276:
3253:
3233:
3207:
3181:
3145:
3105:
3085:
3065:
2990:
2943:
2898:
2865:
2845:
2819:
2715:
2676:
2619:
2577:
2566:{\displaystyle O(n)}
2548:
2521:
2480:
2452:
2441:{\displaystyle O(m)}
2423:
2386:
2320:
2300:
2270:
2266:. When hashing into
2259:{\displaystyle O(n)}
2241:
2212:
2192:
2188:is chosen linear in
2172:
2128:
2124:, which is of order
2082:
2038:
2012:
1992:
1966:
1943:
1911:
1900:{\displaystyle h(x)}
1882:
1862:
1842:
1818:
1798:
1703:
1668:
1637:
1611:
1569:
1536:
1516:
1492:
1466:
1443:
1385:
1282:
1242:
1216:
1166:
1155:is a power of two.)
1139:
1119:
1093:
1033:
983:
930:
900:
840:
820:
800:
750:
712:
692:
666:
628:
591:
568:
548:
520:
378:
324:
309:to be precisely the
293:
251:
231:
195:
169:
113:
93:
73:
33:randomized algorithm
9708:Knuth, Donald Ervin
9441:. pp. 235–246.
9135:"Universal Hashing"
8354:. In practice, the
7267:{\displaystyle w/2}
5648:{\displaystyle w-M}
5622:{\displaystyle c=M}
5425:{\displaystyle w-c}
5270:{\displaystyle w-c}
5244:{\displaystyle x-y}
4894:{\displaystyle 2/m}
4631:bits). To evaluate
3826:{\displaystyle x-y}
3629:Another way to see
3417:{\displaystyle a=0}
3371:{\displaystyle p-1}
3222:{\displaystyle x-y}
2834:{\displaystyle a,b}
2469:{\displaystyle 1/m}
1981:{\displaystyle x,y}
1928:{\displaystyle n/m}
1439:for any hash value
1231:{\displaystyle x,y}
729:{\displaystyle 1/m}
537:{\displaystyle 1/m}
9190:David Wagner, ed.
9035:Tabulation hashing
8991:
8961:
8924:
8897:
8858:
8834:
8787:
8767:
8727:
8692:
8664:
8644:
8624:
8580:
8560:
8525:
8505:
8485:
8183:
8145:
8110:
8078:
7922:
7881:
7842:
7822:
7802:
7732:
7712:
7670:
7644:
7620:
7421:{\displaystyle 2w}
7418:
7395:
7333:tabulation hashing
7318:
7298:
7264:
7232:
6976:{\displaystyle 2w}
6973:
6946:
6869:
6677:
6651:
6621:{\displaystyle 2w}
6618:
6591:
6515:
6491:
6458:
6337:
6317:
6297:
6277:
6199:{\displaystyle 2w}
6196:
6173:
6137:
6117:
6081:
6058:
5937:
5908:
5860:
5805:
5755:
5697:
5645:
5619:
5593:
5549:
5497:
5471:
5422:
5396:
5376:
5334:, it follows that
5324:
5287:
5267:
5241:
5215:
5175:
5135:
5083:
5043:
5000:
4919:
4891:
4855:
4744:
4724:
4697:
4677:
4657:
4621:
4601:
4568:
4548:
4502:
4448:
4349:
4323:
4235:
4146:
4120:
4083:
4052:
3986:
3942:
3922:
3897:, it follows that
3887:
3843:
3823:
3793:
3687:
3639:
3615:
3480:
3434:
3414:
3388:
3368:
3338:
3259:
3239:
3219:
3193:
3167:
3131:
3091:
3071:
3048:
2973:
2929:
2877:
2851:
2831:
2802:
2698:
2659:
2583:
2563:
2527:
2503:
2466:
2438:
2409:
2372:
2306:
2283:
2256:
2227:
2198:
2178:
2158:
2114:
2068:
2024:
1998:
1978:
1949:
1925:
1897:
1868:
1848:
1824:
1804:
1794:For any fixed set
1766:and several other
1746:
1689:
1654:
1623:
1597:
1555:
1522:
1498:
1478:
1449:
1429:
1368:
1268:
1228:
1202:
1145:
1125:
1105:
1079:
1019:
966:
912:
886:
826:
806:
786:
726:
698:
678:
645:
614:
574:
554:
534:
503:
360:
299:
279:
237:
217:
181:
155:
99:
79:
9765:Search algorithms
9601:Kankowsk, Peter.
9492:. pp. 1–10.
9415:978-0-89871-680-1
8861:{\displaystyle p}
8837:{\displaystyle p}
8806:Rabin fingerprint
8790:{\displaystyle p}
8765:
8752:
8667:{\displaystyle p}
8621:
8606:
8583:{\displaystyle a}
8482:
8467:
8449:
8448:
8426:'s hash function
8394:'s hash function
8067:
7964:
7845:{\displaystyle x}
7761:
7735:{\displaystyle s}
7647:{\displaystyle w}
7576:
7467:
7451:
7354:
7321:{\displaystyle k}
7177:
7022:
7006:
6899:
6814:
6806:
6726:
6710:
6544:
6518:{\displaystyle m}
6452:
6372:
6340:{\displaystyle H}
6320:{\displaystyle w}
6300:{\displaystyle k}
6230:
6140:{\displaystyle b}
6084:{\displaystyle a}
5399:{\displaystyle w}
5290:{\displaystyle a}
4901:-almost-universal
4868:This scheme does
4747:{\displaystyle M}
4700:{\displaystyle a}
4680:{\displaystyle x}
4624:{\displaystyle w}
4571:{\displaystyle w}
4490:
4482:
4229:
4221:
4210:
4202:
4046:
4038:
3945:{\displaystyle p}
3846:{\displaystyle a}
3768:
3760:
3642:{\displaystyle H}
3437:{\displaystyle i}
3391:{\displaystyle a}
3262:{\displaystyle a}
3242:{\displaystyle p}
3203:their difference
3094:{\displaystyle 0}
3074:{\displaystyle i}
3061:for some integer
2854:{\displaystyle p}
2796:
2788:
2777:
2769:
2586:{\displaystyle h}
2530:{\displaystyle S}
2309:{\displaystyle t}
2201:{\displaystyle n}
2181:{\displaystyle m}
2001:{\displaystyle S}
1952:{\displaystyle x}
1871:{\displaystyle S}
1851:{\displaystyle x}
1827:{\displaystyle n}
1807:{\displaystyle S}
1774:schemes, such as
1525:{\displaystyle H}
1501:{\displaystyle m}
1452:{\displaystyle z}
1192:
1148:{\displaystyle m}
1073:
1065:
1009:
880:
872:
836:, the difference
829:{\displaystyle H}
809:{\displaystyle h}
776:
577:{\displaystyle H}
557:{\displaystyle h}
501:
422:
419:
404:
302:{\displaystyle S}
240:{\displaystyle S}
102:{\displaystyle m}
82:{\displaystyle U}
29:universal hashing
9777:
9725:
9695:
9694:
9692:
9691:
9677:
9671:
9670:
9664:
9656:
9636:
9628:
9622:
9621:
9613:
9607:
9606:
9598:
9592:
9587:Robert Uzgalis.
9585:
9579:
9578:
9576:
9568:
9562:
9561:
9551:
9536:Computer Journal
9531:
9522:
9521:
9501:
9474:
9468:
9466:
9460:
9449:
9443:
9442:
9430:
9421:
9419:
9399:
9376:
9363:
9362:
9346:
9340:
9339:
9328:
9322:
9321:
9319:
9317:
9296:
9287:
9281:
9280:
9254:
9241:
9232:
9231:
9229:
9214:
9208:
9201:
9195:
9188:
9182:
9181:
9163:
9157:
9156:
9154:
9152:
9146:
9140:. Archived from
9139:
9130:
9124:
9123:
9121:
9093:
9070:
9055:
9046:
9031:
9000:
8998:
8997:
8992:
8990:
8989:
8970:
8968:
8967:
8962:
8954:
8933:
8931:
8930:
8925:
8923:
8922:
8906:
8904:
8903:
8898:
8890:
8889:
8867:
8865:
8864:
8859:
8843:
8841:
8840:
8835:
8796:
8794:
8793:
8788:
8776:
8774:
8773:
8768:
8766:
8758:
8753:
8745:
8736:
8734:
8733:
8728:
8726:
8725:
8724:
8701:
8699:
8698:
8693:
8688:
8673:
8671:
8670:
8665:
8653:
8651:
8650:
8645:
8633:
8631:
8630:
8625:
8623:
8622:
8614:
8608:
8607:
8599:
8589:
8587:
8586:
8581:
8569:
8567:
8566:
8561:
8559:
8558:
8557:
8534:
8532:
8531:
8526:
8514:
8512:
8511:
8506:
8494:
8492:
8491:
8486:
8484:
8483:
8475:
8469:
8468:
8460:
8439:
8377:
8376:
8338:
8335:
8332:
8329:
8326:
8323:
8320:
8317:
8314:
8311:
8308:
8305:
8302:
8299:
8296:
8293:
8290:
8287:
8284:
8281:
8278:
8275:
8272:
8269:
8266:
8263:
8260:
8257:
8254:
8251:
8248:
8245:
8242:
8239:
8236:
8233:
8230:
8227:
8224:
8221:
8218:
8215:
8212:
8209:
8206:
8203:
8192:
8190:
8189:
8184:
8154:
8152:
8151:
8146:
8144:
8143:
8142:
8119:
8117:
8116:
8111:
8087:
8085:
8084:
8079:
8077:
8073:
8069:
8068:
8065:
8059:
8058:
8052:
8051:
8033:
8032:
8022:
8017:
8002:
8001:
7990:
7989:
7988:
7966:
7965:
7957:
7951:
7950:
7931:
7929:
7928:
7923:
7890:
7888:
7887:
7882:
7868:
7867:
7851:
7849:
7848:
7843:
7831:
7829:
7828:
7823:
7811:
7809:
7808:
7803:
7798:
7797:
7779:
7778:
7763:
7762:
7754:
7741:
7739:
7738:
7733:
7721:
7719:
7718:
7713:
7679:
7677:
7676:
7671:
7653:
7651:
7650:
7645:
7629:
7627:
7626:
7621:
7619:
7618:
7607:
7591:
7590:
7578:
7577:
7574:
7568:
7567:
7558:
7557:
7541:
7530:
7512:
7511:
7496:
7495:
7494:
7469:
7468:
7460:
7454:
7453:
7452:
7444:
7427:
7425:
7424:
7419:
7404:
7402:
7401:
7396:
7391:
7390:
7372:
7371:
7356:
7355:
7347:
7327:
7325:
7324:
7319:
7307:
7305:
7304:
7299:
7291:
7273:
7271:
7270:
7265:
7260:
7241:
7239:
7238:
7233:
7231:
7230:
7210:
7197:
7193:
7192:
7191:
7179:
7178:
7175:
7169:
7168:
7159:
7158:
7137:
7136:
7109:
7108:
7093:
7092:
7076:
7069:
7057:
7042:
7041:
7024:
7023:
7015:
7009:
7008:
7007:
6999:
6982:
6980:
6979:
6974:
6955:
6953:
6952:
6947:
6942:
6941:
6917:
6916:
6901:
6900:
6892:
6878:
6876:
6875:
6870:
6868:
6867:
6847:
6834:
6830:
6829:
6828:
6816:
6815:
6812:
6804:
6803:
6802:
6796:
6795:
6783:
6782:
6772:
6761:
6746:
6745:
6728:
6727:
6719:
6713:
6712:
6711:
6703:
6686:
6684:
6683:
6678:
6660:
6658:
6657:
6652:
6650:
6649:
6627:
6625:
6624:
6619:
6600:
6598:
6597:
6592:
6587:
6586:
6562:
6561:
6546:
6545:
6537:
6524:
6522:
6521:
6516:
6500:
6498:
6497:
6492:
6484:
6483:
6467:
6465:
6464:
6459:
6454:
6453:
6450:
6443:
6439:
6435:
6434:
6422:
6421:
6411:
6400:
6374:
6373:
6365:
6346:
6344:
6343:
6338:
6326:
6324:
6323:
6318:
6306:
6304:
6303:
6298:
6286:
6284:
6283:
6278:
6273:
6272:
6248:
6247:
6232:
6231:
6223:
6205:
6203:
6202:
6197:
6182:
6180:
6179:
6174:
6172:
6171:
6146:
6144:
6143:
6138:
6126:
6124:
6123:
6118:
6116:
6115:
6090:
6088:
6087:
6082:
6067:
6065:
6064:
6059:
6054:
6053:
6043:
6028:
6027:
6016:
6015:
5972:
5971:
5946:
5944:
5943:
5938:
5917:
5915:
5914:
5909:
5907:
5906:
5869:
5867:
5866:
5861:
5856:
5845:
5844:
5829:
5814:
5812:
5811:
5806:
5764:
5762:
5761:
5756:
5745:
5744:
5723:
5722:
5706:
5704:
5703:
5698:
5696:
5695:
5690:
5689:
5654:
5652:
5651:
5646:
5628:
5626:
5625:
5620:
5602:
5600:
5599:
5594:
5558:
5556:
5555:
5550:
5548:
5547:
5542:
5541:
5506:
5504:
5503:
5498:
5480:
5478:
5477:
5472:
5467:
5456:
5455:
5446:
5431:
5429:
5428:
5423:
5405:
5403:
5402:
5397:
5385:
5383:
5382:
5377:
5375:
5374:
5369:
5368:
5333:
5331:
5330:
5325:
5323:
5322:
5321:
5320:
5296:
5294:
5293:
5288:
5276:
5274:
5273:
5268:
5250:
5248:
5247:
5242:
5224:
5222:
5221:
5216:
5214:
5213:
5208:
5207:
5184:
5182:
5181:
5176:
5174:
5173:
5168:
5167:
5144:
5142:
5141:
5136:
5134:
5133:
5128:
5127:
5092:
5090:
5089:
5084:
5082:
5081:
5076:
5075:
5052:
5050:
5049:
5044:
5042:
5041:
5036:
5035:
5009:
5007:
5006:
5001:
4996:
4973:
4972:
4951:
4950:
4928:
4926:
4925:
4920:
4900:
4898:
4897:
4892:
4887:
4864:
4862:
4861:
4856:
4851:
4850:
4833:
4817:
4816:
4807:
4806:
4773:
4772:
4753:
4751:
4750:
4745:
4733:
4731:
4730:
4725:
4723:
4722:
4706:
4704:
4703:
4698:
4686:
4684:
4683:
4678:
4666:
4664:
4663:
4658:
4647:
4646:
4630:
4628:
4627:
4622:
4610:
4608:
4607:
4602:
4600:
4599:
4577:
4575:
4574:
4569:
4557:
4555:
4554:
4549:
4547:
4546:
4511:
4509:
4508:
4503:
4492:
4491:
4488:
4480:
4457:
4455:
4454:
4449:
4432:
4403:
4402:
4381:
4380:
4358:
4356:
4355:
4350:
4332:
4330:
4329:
4324:
4319:
4296:
4295:
4274:
4273:
4244:
4242:
4241:
4236:
4231:
4230:
4227:
4219:
4212:
4211:
4208:
4200:
4178:
4177:
4155:
4153:
4152:
4147:
4129:
4127:
4126:
4121:
4113:
4092:
4090:
4089:
4084:
4079:
4061:
4059:
4058:
4053:
4048:
4047:
4044:
4036:
3995:
3993:
3992:
3987:
3951:
3949:
3948:
3943:
3931:
3929:
3928:
3923:
3896:
3894:
3893:
3888:
3852:
3850:
3849:
3844:
3832:
3830:
3829:
3824:
3802:
3800:
3799:
3794:
3792:
3770:
3769:
3766:
3758:
3696:
3694:
3693:
3688:
3648:
3646:
3645:
3640:
3624:
3622:
3621:
3616:
3611:
3585:
3574:
3533:
3522:
3489:
3487:
3486:
3481:
3473:
3443:
3441:
3440:
3435:
3423:
3421:
3420:
3415:
3397:
3395:
3394:
3389:
3377:
3375:
3374:
3369:
3347:
3345:
3344:
3339:
3337:
3321:
3320:
3268:
3266:
3265:
3260:
3248:
3246:
3245:
3240:
3228:
3226:
3225:
3220:
3202:
3200:
3199:
3194:
3176:
3174:
3173:
3168:
3166:
3158:
3140:
3138:
3137:
3132:
3127:
3100:
3098:
3097:
3092:
3080:
3078:
3077:
3072:
3057:
3055:
3054:
3049:
3047:
2983:only holds when
2982:
2980:
2979:
2974:
2938:
2936:
2935:
2930:
2925:
2924:
2886:
2884:
2883:
2878:
2860:
2858:
2857:
2852:
2840:
2838:
2837:
2832:
2811:
2809:
2808:
2803:
2798:
2797:
2794:
2786:
2779:
2778:
2775:
2767:
2733:
2732:
2707:
2705:
2704:
2699:
2697:
2689:
2668:
2666:
2665:
2660:
2649:
2641:
2610:Hashing integers
2592:
2590:
2589:
2584:
2572:
2570:
2569:
2564:
2536:
2534:
2533:
2528:
2512:
2510:
2509:
2504:
2496:
2475:
2473:
2472:
2467:
2462:
2447:
2445:
2444:
2439:
2418:
2416:
2415:
2410:
2405:
2381:
2379:
2378:
2373:
2356:
2333:
2315:
2313:
2312:
2307:
2292:
2290:
2289:
2284:
2282:
2281:
2265:
2263:
2262:
2257:
2236:
2234:
2233:
2228:
2207:
2205:
2204:
2199:
2187:
2185:
2184:
2179:
2167:
2165:
2164:
2159:
2151:
2146:
2145:
2123:
2121:
2120:
2115:
2107:
2077:
2075:
2074:
2069:
2033:
2031:
2030:
2025:
2007:
2005:
2004:
1999:
1987:
1985:
1984:
1979:
1958:
1956:
1955:
1950:
1934:
1932:
1931:
1926:
1921:
1906:
1904:
1903:
1898:
1877:
1875:
1874:
1869:
1857:
1855:
1854:
1849:
1833:
1831:
1830:
1825:
1813:
1811:
1810:
1805:
1784:2-choice hashing
1755:
1753:
1752:
1747:
1745:
1744:
1743:
1742:
1741:
1698:
1696:
1695:
1690:
1663:
1661:
1660:
1655:
1647:
1632:
1630:
1629:
1624:
1606:
1604:
1603:
1598:
1596:
1595:
1594:
1593:
1592:
1564:
1562:
1561:
1556:
1554:
1553:
1531:
1529:
1528:
1523:
1507:
1505:
1504:
1499:
1487:
1485:
1484:
1481:{\displaystyle }
1479:
1458:
1456:
1455:
1450:
1438:
1436:
1435:
1430:
1425:
1377:
1375:
1374:
1369:
1367:
1366:
1357:
1343:
1342:
1315:
1314:
1277:
1275:
1274:
1269:
1267:
1266:
1254:
1253:
1237:
1235:
1234:
1229:
1211:
1209:
1208:
1203:
1190:
1154:
1152:
1151:
1146:
1134:
1132:
1131:
1126:
1114:
1112:
1111:
1108:{\displaystyle }
1106:
1088:
1086:
1085:
1080:
1075:
1074:
1071:
1063:
1028:
1026:
1025:
1020:
1007:
975:
973:
972:
967:
921:
919:
918:
915:{\displaystyle }
913:
895:
893:
892:
887:
882:
881:
878:
870:
835:
833:
832:
827:
815:
813:
812:
807:
795:
793:
792:
787:
774:
735:
733:
732:
727:
722:
707:
705:
704:
699:
687:
685:
684:
679:
658:
654:
652:
651:
646:
641:
623:
621:
620:
615:
607:
583:
581:
580:
575:
563:
561:
560:
555:
543:
541:
540:
535:
530:
512:
510:
509:
504:
502:
497:
496:
488:
482:
477:
427:
420:
417:
402:
372:universal family
369:
367:
366:
361:
308:
306:
305:
300:
288:
286:
285:
280:
266:
258:
246:
244:
243:
238:
226:
224:
223:
218:
210:
202:
190:
188:
187:
182:
164:
162:
161:
156:
108:
106:
105:
100:
88:
86:
85:
80:
9785:
9784:
9780:
9779:
9778:
9776:
9775:
9774:
9745:
9744:
9732:
9722:
9703:
9701:Further reading
9698:
9689:
9687:
9685:docs.oracle.com
9679:
9678:
9674:
9658:
9657:
9653:
9629:
9625:
9614:
9610:
9599:
9595:
9586:
9582:
9574:
9570:
9569:
9565:
9532:
9525:
9518:
9478:Pătraşcu, Mihai
9475:
9471:
9458:
9450:
9446:
9431:
9424:
9416:
9397:10.1.1.215.4253
9377:
9366:
9347:
9343:
9329:
9325:
9315:
9313:
9294:
9288:
9284:
9252:
9246:Pătraşcu, Mihai
9242:
9235:
9215:
9211:
9202:
9198:
9189:
9185:
9178:
9164:
9160:
9150:
9148:
9144:
9137:
9131:
9127:
9098:Wegman, Mark N.
9096:Carter, Larry;
9094:
9081:
9077:
9068:
9065:Perfect hashing
9053:
9044:
9029:
9026:Rolling hashing
9016:
8985:
8981:
8979:
8976:
8975:
8950:
8942:
8939:
8938:
8918:
8914:
8912:
8909:
8908:
8885:
8881:
8873:
8870:
8869:
8853:
8850:
8849:
8829:
8826:
8825:
8818:
8782:
8779:
8778:
8757:
8744:
8742:
8739:
8738:
8714:
8713:
8709:
8707:
8704:
8703:
8684:
8679:
8676:
8675:
8659:
8656:
8655:
8639:
8636:
8635:
8613:
8612:
8598:
8597:
8595:
8592:
8591:
8575:
8572:
8571:
8547:
8546:
8542:
8540:
8537:
8536:
8520:
8517:
8516:
8500:
8497:
8496:
8474:
8473:
8459:
8458:
8456:
8453:
8452:
8437:
8380:Implementation
8340:
8339:
8336:
8333:
8330:
8327:
8324:
8321:
8318:
8315:
8312:
8309:
8306:
8303:
8300:
8297:
8294:
8291:
8288:
8285:
8282:
8279:
8276:
8273:
8270:
8267:
8264:
8261:
8258:
8255:
8252:
8249:
8246:
8243:
8240:
8237:
8234:
8231:
8228:
8225:
8222:
8219:
8216:
8213:
8210:
8207:
8204:
8201:
8160:
8157:
8156:
8132:
8131:
8127:
8125:
8122:
8121:
8093:
8090:
8089:
8064:
8060:
8054:
8053:
8041:
8037:
8028:
8024:
8018:
8007:
7997:
7996:
7995:
7991:
7978:
7977:
7973:
7956:
7955:
7946:
7942:
7940:
7937:
7936:
7896:
7893:
7892:
7863:
7859:
7857:
7854:
7853:
7837:
7834:
7833:
7817:
7814:
7813:
7793:
7789:
7774:
7770:
7753:
7752:
7750:
7747:
7746:
7727:
7724:
7723:
7698:
7695:
7694:
7686:
7684:Hashing strings
7659:
7656:
7655:
7639:
7636:
7635:
7614:
7610:
7597:
7583:
7579:
7573:
7569:
7563:
7559:
7547:
7543:
7531:
7520:
7507:
7503:
7475:
7474:
7470:
7459:
7458:
7443:
7442:
7438:
7436:
7433:
7432:
7410:
7407:
7406:
7386:
7382:
7367:
7363:
7346:
7345:
7343:
7340:
7339:
7313:
7310:
7309:
7287:
7279:
7276:
7275:
7256:
7251:
7248:
7247:
7217:
7213:
7200:
7184:
7180:
7174:
7170:
7164:
7163:
7145:
7141:
7123:
7119:
7101:
7097:
7085:
7081:
7065:
7058:
7047:
7037:
7036:
7035:
7031:
7014:
7013:
6998:
6997:
6993:
6991:
6988:
6987:
6965:
6962:
6961:
6931:
6927:
6912:
6908:
6891:
6890:
6888:
6885:
6884:
6854:
6850:
6837:
6821:
6817:
6811:
6807:
6798:
6797:
6791:
6787:
6778:
6774:
6762:
6751:
6741:
6740:
6739:
6735:
6718:
6717:
6702:
6701:
6697:
6695:
6692:
6691:
6666:
6663:
6662:
6645:
6641:
6633:
6630:
6629:
6610:
6607:
6606:
6576:
6572:
6557:
6553:
6536:
6535:
6533:
6530:
6529:
6510:
6507:
6506:
6479:
6475:
6473:
6470:
6469:
6449:
6445:
6430:
6426:
6417:
6413:
6401:
6390:
6385:
6381:
6364:
6363:
6355:
6352:
6351:
6332:
6329:
6328:
6327:bits each). If
6312:
6309:
6308:
6292:
6289:
6288:
6262:
6258:
6243:
6239:
6222:
6221:
6219:
6216:
6215:
6212:
6210:Hashing vectors
6188:
6185:
6184:
6164:
6160:
6152:
6149:
6148:
6132:
6129:
6128:
6108:
6104:
6096:
6093:
6092:
6076:
6073:
6072:
6049:
6045:
6033:
6017:
6011:
6007:
6006:
5961:
5957:
5955:
5952:
5951:
5923:
5920:
5919:
5890:
5886:
5878:
5875:
5874:
5852:
5834:
5830:
5825:
5820:
5817:
5816:
5770:
5767:
5766:
5740:
5736:
5718:
5714:
5712:
5709:
5708:
5691:
5685:
5681:
5680:
5660:
5657:
5656:
5634:
5631:
5630:
5608:
5605:
5604:
5603:. Finally, if
5564:
5561:
5560:
5543:
5537:
5533:
5532:
5512:
5509:
5508:
5486:
5483:
5482:
5463:
5451:
5447:
5442:
5437:
5434:
5433:
5411:
5408:
5407:
5391:
5388:
5387:
5370:
5364:
5360:
5359:
5339:
5336:
5335:
5316:
5312:
5311:
5307:
5305:
5302:
5301:
5282:
5279:
5278:
5256:
5253:
5252:
5230:
5227:
5226:
5209:
5203:
5199:
5198:
5190:
5187:
5186:
5169:
5163:
5159:
5158:
5150:
5147:
5146:
5129:
5123:
5119:
5118:
5098:
5095:
5094:
5077:
5071:
5067:
5066:
5058:
5055:
5054:
5037:
5031:
5027:
5026:
5018:
5015:
5014:
4992:
4968:
4964:
4946:
4942:
4934:
4931:
4930:
4908:
4905:
4904:
4883:
4878:
4875:
4874:
4840:
4836:
4823:
4812:
4808:
4804:
4800:
4768:
4764:
4762:
4759:
4758:
4739:
4736:
4735:
4718:
4714:
4712:
4709:
4708:
4692:
4689:
4688:
4672:
4669:
4668:
4642:
4638:
4636:
4633:
4632:
4616:
4613:
4612:
4595:
4591:
4583:
4580:
4579:
4563:
4560:
4559:
4542:
4538:
4530:
4527:
4526:
4518:
4487:
4483:
4463:
4460:
4459:
4428:
4398:
4394:
4376:
4372:
4364:
4361:
4360:
4338:
4335:
4334:
4315:
4291:
4287:
4269:
4265:
4257:
4254:
4253:
4226:
4222:
4207:
4203:
4173:
4169:
4167:
4164:
4163:
4135:
4132:
4131:
4109:
4098:
4095:
4094:
4075:
4067:
4064:
4063:
4043:
4039:
4001:
3998:
3997:
3957:
3954:
3953:
3937:
3934:
3933:
3902:
3899:
3898:
3858:
3855:
3854:
3838:
3835:
3834:
3833:is nonzero and
3812:
3809:
3808:
3777:
3765:
3761:
3705:
3702:
3701:
3658:
3655:
3654:
3634:
3631:
3630:
3607:
3581:
3570:
3529:
3518:
3498:
3495:
3494:
3469:
3449:
3446:
3445:
3429:
3426:
3425:
3403:
3400:
3399:
3383:
3380:
3379:
3357:
3354:
3353:
3322:
3313:
3309:
3277:
3274:
3273:
3254:
3251:
3250:
3234:
3231:
3230:
3208:
3205:
3204:
3182:
3179:
3178:
3162:
3154:
3146:
3143:
3142:
3123:
3106:
3103:
3102:
3086:
3083:
3082:
3066:
3063:
3062:
3032:
2991:
2988:
2987:
2944:
2941:
2940:
2914:
2910:
2899:
2896:
2895:
2866:
2863:
2862:
2846:
2843:
2842:
2820:
2817:
2816:
2793:
2789:
2774:
2770:
2722:
2718:
2716:
2713:
2712:
2693:
2685:
2677:
2674:
2673:
2645:
2637:
2620:
2617:
2616:
2612:
2603:
2578:
2575:
2574:
2549:
2546:
2545:
2522:
2519:
2518:
2492:
2481:
2478:
2477:
2458:
2453:
2450:
2449:
2424:
2421:
2420:
2401:
2387:
2384:
2383:
2352:
2329:
2321:
2318:
2317:
2301:
2298:
2297:
2277:
2273:
2271:
2268:
2267:
2242:
2239:
2238:
2213:
2210:
2209:
2193:
2190:
2189:
2173:
2170:
2169:
2147:
2141:
2137:
2129:
2126:
2125:
2103:
2083:
2080:
2079:
2039:
2036:
2035:
2013:
2010:
2009:
1993:
1990:
1989:
1967:
1964:
1963:
1944:
1941:
1940:
1917:
1912:
1909:
1908:
1883:
1880:
1879:
1863:
1860:
1859:
1843:
1840:
1839:
1819:
1816:
1815:
1799:
1796:
1795:
1792:
1734:
1733:
1729:
1728:
1724:
1704:
1701:
1700:
1669:
1666:
1665:
1640:
1638:
1635:
1634:
1612:
1609:
1608:
1585:
1584:
1580:
1579:
1575:
1570:
1567:
1566:
1549:
1545:
1537:
1534:
1533:
1517:
1514:
1513:
1493:
1490:
1489:
1467:
1464:
1463:
1444:
1441:
1440:
1421:
1386:
1383:
1382:
1362:
1358:
1353:
1338:
1334:
1310:
1306:
1283:
1280:
1279:
1262:
1258:
1249:
1245:
1243:
1240:
1239:
1217:
1214:
1213:
1167:
1164:
1163:
1140:
1137:
1136:
1120:
1117:
1116:
1094:
1091:
1090:
1070:
1066:
1034:
1031:
1030:
984:
981:
980:
931:
928:
927:
901:
898:
897:
877:
873:
841:
838:
837:
821:
818:
817:
801:
798:
797:
751:
748:
747:
718:
713:
710:
709:
693:
690:
689:
667:
664:
663:
656:
637:
629:
626:
625:
603:
592:
589:
588:
569:
566:
565:
549:
546:
545:
526:
521:
518:
517:
492:
484:
483:
481:
473:
423:
379:
376:
375:
325:
322:
321:
294:
291:
290:
262:
254:
252:
249:
248:
232:
229:
228:
206:
198:
196:
193:
192:
170:
167:
166:
114:
111:
110:
109:bins (labelled
94:
91:
90:
74:
71:
70:
67:
61:
17:
12:
11:
5:
9783:
9773:
9772:
9767:
9762:
9757:
9743:
9742:
9731:
9730:External links
9728:
9727:
9726:
9720:
9702:
9699:
9697:
9696:
9672:
9651:
9623:
9608:
9593:
9580:
9563:
9523:
9516:
9482:Thorup, Mikkel
9469:
9444:
9422:
9414:
9380:Thorup, Mikkel
9364:
9341:
9332:Thorup, Mikkel
9323:
9282:
9263:(4): 584–596.
9233:
9218:Thorup, Mikkel
9209:
9207:. 2014. p. 10.
9196:
9183:
9176:
9158:
9147:on 24 May 2011
9125:
9112:(2): 143–154.
9078:
9076:
9073:
9072:
9071:
9062:
9056:
9047:
9038:
9032:
9023:
9015:
9012:
9011:
9010:
8988:
8984:
8972:
8960:
8957:
8953:
8949:
8946:
8935:
8921:
8917:
8896:
8893:
8888:
8884:
8880:
8877:
8857:
8846:Mersenne prime
8833:
8817:
8814:
8786:
8764:
8761:
8756:
8751:
8748:
8723:
8720:
8717:
8712:
8691:
8687:
8683:
8663:
8643:
8620:
8617:
8611:
8605:
8602:
8579:
8556:
8553:
8550:
8545:
8524:
8504:
8481:
8478:
8472:
8466:
8463:
8447:
8446:
8443:
8440:
8434:
8433:
8430:
8427:
8416:
8415:
8412:
8409:
8408:STLPort 4.6.2
8405:
8404:
8401:
8398:
8388:
8387:
8384:
8383:INITIAL_VALUE
8381:
8346:is based on a
8200:
8195:
8194:
8182:
8179:
8176:
8173:
8170:
8167:
8164:
8141:
8138:
8135:
8130:
8109:
8106:
8103:
8100:
8097:
8076:
8072:
8063:
8057:
8050:
8047:
8044:
8040:
8036:
8031:
8027:
8021:
8016:
8013:
8010:
8006:
8000:
7994:
7987:
7984:
7981:
7976:
7972:
7969:
7963:
7960:
7954:
7949:
7945:
7921:
7918:
7915:
7912:
7909:
7906:
7903:
7900:
7880:
7877:
7874:
7871:
7866:
7862:
7841:
7821:
7801:
7796:
7792:
7788:
7785:
7782:
7777:
7773:
7769:
7766:
7760:
7757:
7731:
7711:
7708:
7705:
7702:
7690:variable-sized
7685:
7682:
7669:
7666:
7663:
7643:
7632:
7631:
7617:
7613:
7606:
7603:
7600:
7594:
7589:
7586:
7582:
7572:
7566:
7562:
7556:
7553:
7550:
7546:
7540:
7537:
7534:
7529:
7526:
7523:
7519:
7515:
7510:
7506:
7502:
7499:
7493:
7490:
7487:
7484:
7481:
7478:
7473:
7466:
7463:
7457:
7450:
7447:
7441:
7428:bits. Compute
7417:
7414:
7394:
7389:
7385:
7381:
7378:
7375:
7370:
7366:
7362:
7359:
7353:
7350:
7317:
7297:
7294:
7290:
7286:
7283:
7263:
7259:
7255:
7244:
7243:
7229:
7226:
7223:
7220:
7216:
7209:
7206:
7203:
7196:
7190:
7187:
7183:
7173:
7167:
7162:
7157:
7154:
7151:
7148:
7144:
7140:
7135:
7132:
7129:
7126:
7122:
7118:
7115:
7112:
7107:
7104:
7100:
7096:
7091:
7088:
7084:
7080:
7075:
7072:
7068:
7064:
7061:
7056:
7053:
7050:
7046:
7040:
7034:
7030:
7027:
7021:
7018:
7012:
7005:
7002:
6996:
6972:
6969:
6945:
6940:
6937:
6934:
6930:
6926:
6923:
6920:
6915:
6911:
6907:
6904:
6898:
6895:
6881:
6880:
6866:
6863:
6860:
6857:
6853:
6846:
6843:
6840:
6833:
6827:
6824:
6820:
6810:
6801:
6794:
6790:
6786:
6781:
6777:
6771:
6768:
6765:
6760:
6757:
6754:
6750:
6744:
6738:
6734:
6731:
6725:
6722:
6716:
6709:
6706:
6700:
6676:
6673:
6670:
6648:
6644:
6640:
6637:
6617:
6614:
6590:
6585:
6582:
6579:
6575:
6571:
6568:
6565:
6560:
6556:
6552:
6549:
6543:
6540:
6514:
6503:
6502:
6490:
6487:
6482:
6478:
6457:
6448:
6442:
6438:
6433:
6429:
6425:
6420:
6416:
6410:
6407:
6404:
6399:
6396:
6393:
6389:
6384:
6380:
6377:
6371:
6368:
6362:
6359:
6336:
6316:
6296:
6276:
6271:
6268:
6265:
6261:
6257:
6254:
6251:
6246:
6242:
6238:
6235:
6229:
6226:
6211:
6208:
6195:
6192:
6170:
6167:
6163:
6159:
6156:
6136:
6114:
6111:
6107:
6103:
6100:
6080:
6069:
6068:
6057:
6052:
6048:
6042:
6039:
6036:
6031:
6026:
6023:
6020:
6014:
6010:
6005:
6002:
5999:
5996:
5993:
5990:
5987:
5984:
5981:
5978:
5975:
5970:
5967:
5964:
5960:
5936:
5933:
5930:
5927:
5905:
5902:
5899:
5896:
5893:
5889:
5885:
5882:
5859:
5855:
5851:
5848:
5843:
5840:
5837:
5833:
5828:
5824:
5804:
5801:
5798:
5795:
5792:
5789:
5786:
5783:
5780:
5777:
5774:
5754:
5751:
5748:
5743:
5739:
5735:
5732:
5729:
5726:
5721:
5717:
5694:
5688:
5684:
5679:
5676:
5673:
5670:
5667:
5664:
5644:
5641:
5638:
5618:
5615:
5612:
5592:
5589:
5586:
5583:
5580:
5577:
5574:
5571:
5568:
5546:
5540:
5536:
5531:
5528:
5525:
5522:
5519:
5516:
5496:
5493:
5490:
5470:
5466:
5462:
5459:
5454:
5450:
5445:
5441:
5421:
5418:
5415:
5395:
5373:
5367:
5363:
5358:
5355:
5352:
5349:
5346:
5343:
5319:
5315:
5310:
5286:
5266:
5263:
5260:
5240:
5237:
5234:
5212:
5206:
5202:
5197:
5194:
5172:
5166:
5162:
5157:
5154:
5132:
5126:
5122:
5117:
5114:
5111:
5108:
5105:
5102:
5080:
5074:
5070:
5065:
5062:
5040:
5034:
5030:
5025:
5022:
4999:
4995:
4991:
4988:
4985:
4982:
4979:
4976:
4971:
4967:
4963:
4960:
4957:
4954:
4949:
4945:
4941:
4938:
4918:
4915:
4912:
4890:
4886:
4882:
4866:
4865:
4854:
4849:
4846:
4843:
4839:
4832:
4829:
4826:
4820:
4815:
4811:
4803:
4797:
4794:
4791:
4788:
4785:
4782:
4779:
4776:
4771:
4767:
4743:
4721:
4717:
4696:
4676:
4656:
4653:
4650:
4645:
4641:
4620:
4598:
4594:
4590:
4587:
4567:
4545:
4541:
4537:
4534:
4522:multiply-shift
4517:
4514:
4501:
4498:
4495:
4486:
4479:
4476:
4473:
4470:
4467:
4447:
4444:
4441:
4438:
4435:
4431:
4427:
4424:
4421:
4418:
4415:
4412:
4409:
4406:
4401:
4397:
4393:
4390:
4387:
4384:
4379:
4375:
4371:
4368:
4348:
4345:
4342:
4322:
4318:
4314:
4311:
4308:
4305:
4302:
4299:
4294:
4290:
4286:
4283:
4280:
4277:
4272:
4268:
4264:
4261:
4246:
4245:
4234:
4225:
4218:
4215:
4206:
4199:
4196:
4193:
4190:
4187:
4184:
4181:
4176:
4172:
4145:
4142:
4139:
4119:
4116:
4112:
4108:
4105:
4102:
4082:
4078:
4074:
4071:
4051:
4042:
4035:
4032:
4029:
4026:
4023:
4020:
4017:
4014:
4011:
4008:
4005:
3985:
3982:
3979:
3976:
3973:
3970:
3967:
3964:
3961:
3941:
3921:
3918:
3915:
3912:
3909:
3906:
3886:
3883:
3880:
3877:
3874:
3871:
3868:
3865:
3862:
3842:
3822:
3819:
3816:
3805:
3804:
3791:
3788:
3784:
3781:
3776:
3773:
3764:
3757:
3754:
3751:
3748:
3745:
3742:
3739:
3736:
3733:
3730:
3727:
3724:
3721:
3718:
3715:
3712:
3709:
3686:
3683:
3680:
3677:
3674:
3671:
3668:
3665:
3662:
3638:
3627:
3626:
3614:
3610:
3606:
3603:
3600:
3597:
3594:
3591:
3588:
3584:
3580:
3577:
3573:
3569:
3566:
3563:
3560:
3557:
3554:
3551:
3548:
3545:
3542:
3539:
3536:
3532:
3528:
3525:
3521:
3517:
3514:
3511:
3508:
3505:
3502:
3479:
3476:
3472:
3468:
3465:
3462:
3459:
3456:
3453:
3433:
3413:
3410:
3407:
3387:
3367:
3364:
3361:
3350:
3349:
3336:
3333:
3329:
3326:
3319:
3316:
3312:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3284:
3281:
3258:
3249:. Solving for
3238:
3218:
3215:
3212:
3192:
3189:
3186:
3165:
3161:
3157:
3153:
3150:
3130:
3126:
3122:
3119:
3116:
3113:
3110:
3090:
3070:
3059:
3058:
3046:
3043:
3039:
3036:
3031:
3028:
3025:
3022:
3019:
3016:
3013:
3010:
3007:
3004:
3001:
2998:
2995:
2972:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2928:
2923:
2920:
2917:
2913:
2909:
2906:
2903:
2876:
2873:
2870:
2850:
2830:
2827:
2824:
2813:
2812:
2801:
2792:
2785:
2782:
2773:
2766:
2763:
2760:
2757:
2754:
2751:
2748:
2745:
2742:
2739:
2736:
2731:
2728:
2725:
2721:
2696:
2692:
2688:
2684:
2681:
2658:
2655:
2652:
2648:
2644:
2640:
2636:
2633:
2630:
2627:
2624:
2611:
2608:
2602:
2599:
2582:
2562:
2559:
2556:
2553:
2526:
2515:
2514:
2502:
2499:
2495:
2491:
2488:
2485:
2465:
2461:
2457:
2437:
2434:
2431:
2428:
2408:
2404:
2400:
2397:
2394:
2391:
2371:
2368:
2365:
2362:
2359:
2355:
2351:
2348:
2345:
2342:
2339:
2336:
2332:
2328:
2325:
2305:
2294:
2280:
2276:
2255:
2252:
2249:
2246:
2226:
2223:
2220:
2217:
2197:
2177:
2157:
2154:
2150:
2144:
2140:
2136:
2133:
2113:
2110:
2106:
2102:
2099:
2096:
2093:
2090:
2087:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2034:that collide (
2023:
2020:
2017:
1997:
1977:
1974:
1971:
1960:
1948:
1924:
1920:
1916:
1896:
1893:
1890:
1887:
1867:
1847:
1838:For any fixed
1823:
1803:
1791:
1788:
1780:cuckoo hashing
1740:
1737:
1732:
1727:
1723:
1720:
1717:
1714:
1711:
1708:
1688:
1685:
1682:
1679:
1676:
1673:
1653:
1650:
1646:
1643:
1622:
1619:
1616:
1591:
1588:
1583:
1578:
1574:
1552:
1548:
1544:
1541:
1521:
1497:
1477:
1474:
1471:
1448:
1428:
1424:
1420:
1417:
1414:
1411:
1408:
1405:
1402:
1399:
1396:
1393:
1390:
1365:
1361:
1356:
1352:
1349:
1346:
1341:
1337:
1333:
1330:
1327:
1324:
1321:
1318:
1313:
1309:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1265:
1261:
1257:
1252:
1248:
1227:
1224:
1221:
1201:
1198:
1195:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1144:
1124:
1104:
1101:
1098:
1078:
1069:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1018:
1015:
1012:
1006:
1003:
1000:
997:
994:
991:
988:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
924:
923:
911:
908:
905:
885:
876:
869:
866:
863:
860:
857:
854:
851:
848:
845:
825:
805:
785:
782:
779:
773:
770:
767:
764:
761:
758:
755:
725:
721:
717:
697:
677:
674:
671:
644:
640:
636:
633:
613:
610:
606:
602:
599:
596:
573:
553:
533:
529:
525:
500:
495:
491:
487:
480:
476:
472:
469:
466:
463:
460:
457:
454:
451:
448:
445:
442:
439:
436:
433:
430:
426:
416:
413:
410:
407:
401:
398:
395:
392:
389:
386:
383:
359:
356:
353:
350:
347:
344:
341:
338:
335:
332:
329:
298:
278:
275:
272:
269:
265:
261:
257:
236:
216:
213:
209:
205:
201:
180:
177:
174:
154:
151:
148:
145:
142:
139:
136:
133:
130:
127:
124:
121:
118:
98:
78:
60:
57:
15:
9:
6:
4:
3:
2:
9782:
9771:
9768:
9766:
9763:
9761:
9758:
9756:
9753:
9752:
9750:
9741:
9737:
9734:
9733:
9723:
9721:0-201-89685-0
9717:
9713:
9709:
9705:
9704:
9686:
9682:
9676:
9668:
9662:
9654:
9652:0-13-110362-8
9648:
9644:
9640:
9635:
9627:
9619:
9616:Yigit, Ozan.
9612:
9604:
9597:
9590:
9584:
9573:
9567:
9559:
9555:
9550:
9545:
9541:
9537:
9530:
9528:
9519:
9517:9781450306911
9513:
9509:
9505:
9500:
9495:
9491:
9487:
9483:
9479:
9473:
9464:
9457:
9456:
9448:
9440:
9436:
9429:
9427:
9420:, section 5.3
9417:
9411:
9407:
9403:
9398:
9393:
9389:
9385:
9381:
9375:
9373:
9371:
9369:
9360:
9356:
9352:
9345:
9337:
9333:
9327:
9312:
9308:
9304:
9300:
9293:
9286:
9278:
9274:
9270:
9266:
9262:
9258:
9251:
9247:
9240:
9238:
9228:
9223:
9219:
9213:
9206:
9200:
9193:
9187:
9179:
9177:0-521-47465-5
9173:
9169:
9162:
9143:
9136:
9129:
9120:
9115:
9111:
9107:
9103:
9099:
9092:
9090:
9088:
9086:
9084:
9079:
9066:
9063:
9060:
9057:
9051:
9048:
9042:
9039:
9036:
9033:
9027:
9024:
9021:
9018:
9017:
9008:
9004:
8986:
8982:
8973:
8955:
8951:
8947:
8936:
8919:
8915:
8894:
8891:
8886:
8882:
8878:
8875:
8855:
8847:
8831:
8823:
8822:
8821:
8813:
8811:
8807:
8802:
8800:
8784:
8762:
8759:
8754:
8749:
8746:
8710:
8689:
8685:
8681:
8661:
8654:roots modulo
8641:
8615:
8609:
8600:
8577:
8570:implies that
8543:
8522:
8502:
8476:
8470:
8461:
8444:
8441:
8436:
8435:
8431:
8428:
8425:
8421:
8418:
8417:
8413:
8410:
8407:
8406:
8402:
8399:
8397:
8393:
8390:
8389:
8385:
8382:
8379:
8378:
8375:
8373:
8369:
8368:Max-Int-Value
8365:
8361:
8357:
8353:
8349:
8345:
8247:INITIAL_VALUE
8198:
8177:
8165:
8128:
8104:
8098:
8095:
8074:
8070:
8048:
8045:
8042:
8038:
8034:
8029:
8025:
8019:
8014:
8011:
8008:
8004:
7992:
7974:
7970:
7958:
7947:
7943:
7935:
7934:
7933:
7916:
7913:
7910:
7901:
7898:
7875:
7869:
7864:
7860:
7839:
7819:
7794:
7790:
7786:
7783:
7780:
7775:
7771:
7764:
7755:
7743:
7729:
7706:
7700:
7691:
7681:
7667:
7664:
7661:
7641:
7615:
7611:
7587:
7584:
7580:
7564:
7560:
7554:
7551:
7548:
7544:
7538:
7535:
7532:
7527:
7524:
7521:
7517:
7513:
7508:
7504:
7497:
7461:
7445:
7439:
7431:
7430:
7429:
7415:
7412:
7387:
7383:
7379:
7376:
7373:
7368:
7364:
7357:
7348:
7336:
7334:
7329:
7315:
7292:
7288:
7284:
7261:
7257:
7253:
7227:
7224:
7221:
7218:
7214:
7194:
7188:
7185:
7181:
7155:
7152:
7149:
7146:
7142:
7138:
7133:
7130:
7127:
7124:
7120:
7113:
7105:
7102:
7098:
7094:
7089:
7086:
7082:
7070:
7066:
7062:
7054:
7051:
7048:
7044:
7032:
7028:
7016:
7000:
6994:
6986:
6985:
6984:
6970:
6967:
6959:
6938:
6935:
6932:
6928:
6924:
6921:
6918:
6913:
6909:
6902:
6893:
6864:
6861:
6858:
6855:
6851:
6831:
6825:
6822:
6818:
6792:
6788:
6784:
6779:
6775:
6769:
6766:
6763:
6758:
6755:
6752:
6748:
6736:
6732:
6720:
6704:
6698:
6690:
6689:
6688:
6674:
6671:
6668:
6646:
6642:
6638:
6635:
6615:
6612:
6604:
6583:
6580:
6577:
6573:
6569:
6566:
6563:
6558:
6554:
6547:
6538:
6526:
6512:
6488:
6485:
6480:
6476:
6468:, where each
6455:
6440:
6431:
6427:
6418:
6414:
6408:
6405:
6402:
6397:
6394:
6391:
6387:
6382:
6378:
6366:
6357:
6350:
6349:
6348:
6334:
6314:
6294:
6269:
6266:
6263:
6259:
6255:
6252:
6249:
6244:
6240:
6233:
6224:
6207:
6193:
6190:
6168:
6165:
6161:
6157:
6154:
6134:
6112:
6109:
6105:
6101:
6098:
6078:
6055:
6050:
6046:
6024:
6021:
6018:
6012:
6000:
5997:
5994:
5991:
5982:
5976:
5968:
5965:
5962:
5958:
5950:
5949:
5948:
5934:
5931:
5928:
5925:
5903:
5900:
5897:
5894:
5891:
5887:
5883:
5880:
5871:
5857:
5853:
5849:
5846:
5841:
5838:
5835:
5831:
5826:
5822:
5802:
5799:
5796:
5793:
5790:
5787:
5784:
5781:
5778:
5775:
5772:
5749:
5741:
5737:
5733:
5727:
5719:
5715:
5692:
5686:
5674:
5671:
5668:
5662:
5642:
5639:
5636:
5616:
5613:
5610:
5587:
5581:
5578:
5572:
5566:
5544:
5538:
5526:
5523:
5520:
5514:
5494:
5491:
5488:
5468:
5464:
5460:
5457:
5452:
5448:
5443:
5439:
5419:
5416:
5413:
5393:
5371:
5365:
5353:
5350:
5347:
5341:
5317:
5313:
5308:
5300:
5284:
5264:
5261:
5258:
5238:
5235:
5232:
5210:
5204:
5195:
5192:
5170:
5164:
5155:
5152:
5130:
5124:
5112:
5109:
5106:
5100:
5078:
5072:
5063:
5060:
5038:
5032:
5023:
5020:
5011:
4997:
4993:
4989:
4986:
4977:
4969:
4965:
4961:
4955:
4947:
4943:
4916:
4913:
4910:
4902:
4888:
4884:
4880:
4871:
4852:
4847:
4844:
4841:
4837:
4813:
4809:
4795:
4792:
4789:
4783:
4777:
4769:
4765:
4757:
4756:
4755:
4741:
4719:
4715:
4694:
4674:
4651:
4643:
4639:
4618:
4596:
4592:
4588:
4585:
4565:
4543:
4539:
4535:
4532:
4523:
4513:
4499:
4496:
4493:
4474:
4471:
4468:
4442:
4439:
4436:
4429:
4425:
4422:
4413:
4410:
4407:
4399:
4395:
4391:
4385:
4377:
4373:
4346:
4343:
4340:
4320:
4316:
4312:
4309:
4300:
4292:
4288:
4284:
4278:
4270:
4266:
4251:
4250:approximately
4232:
4213:
4197:
4194:
4188:
4182:
4174:
4170:
4162:
4161:
4160:
4157:
4143:
4140:
4137:
4114:
4110:
4106:
4100:
4080:
4076:
4072:
4069:
4049:
4027:
4021:
4018:
4012:
4006:
3980:
3977:
3974:
3971:
3968:
3965:
3962:
3939:
3916:
3913:
3910:
3904:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3840:
3820:
3817:
3814:
3786:
3782:
3771:
3752:
3749:
3746:
3740:
3734:
3728:
3722:
3719:
3713:
3707:
3700:
3699:
3698:
3681:
3675:
3672:
3666:
3660:
3652:
3636:
3612:
3608:
3604:
3601:
3595:
3592:
3589:
3582:
3575:
3571:
3564:
3561:
3558:
3549:
3543:
3540:
3537:
3530:
3523:
3519:
3512:
3509:
3506:
3493:
3492:
3491:
3474:
3470:
3463:
3460:
3457:
3431:
3411:
3408:
3405:
3385:
3365:
3362:
3359:
3331:
3327:
3317:
3314:
3306:
3303:
3300:
3294:
3291:
3288:
3285:
3282:
3279:
3272:
3271:
3270:
3256:
3236:
3216:
3213:
3210:
3190:
3187:
3184:
3159:
3151:
3148:
3128:
3124:
3117:
3114:
3111:
3088:
3068:
3041:
3037:
3029:
3026:
3023:
3020:
3017:
3014:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2986:
2985:
2984:
2967:
2961:
2958:
2952:
2946:
2921:
2918:
2915:
2911:
2904:
2901:
2892:
2890:
2874:
2871:
2868:
2848:
2828:
2825:
2822:
2799:
2780:
2761:
2758:
2755:
2752:
2743:
2737:
2729:
2726:
2723:
2719:
2711:
2710:
2709:
2690:
2682:
2679:
2670:
2653:
2650:
2642:
2634:
2631:
2628:
2625:
2607:
2601:Constructions
2598:
2596:
2580:
2557:
2551:
2543:
2538:
2524:
2497:
2493:
2489:
2483:
2463:
2459:
2455:
2432:
2426:
2406:
2402:
2398:
2395:
2392:
2389:
2366:
2363:
2357:
2353:
2349:
2343:
2340:
2337:
2330:
2326:
2323:
2303:
2295:
2278:
2274:
2250:
2244:
2221:
2195:
2175:
2152:
2148:
2142:
2138:
2131:
2111:
2108:
2104:
2097:
2094:
2091:
2085:
2062:
2056:
2053:
2047:
2041:
2021:
2018:
2015:
1995:
1975:
1972:
1969:
1961:
1946:
1938:
1922:
1918:
1914:
1891:
1885:
1865:
1845:
1837:
1836:
1835:
1821:
1801:
1787:
1785:
1781:
1777:
1771:
1769:
1765:
1761:
1757:
1738:
1735:
1730:
1721:
1718:
1712:
1706:
1686:
1683:
1677:
1671:
1651:
1648:
1644:
1641:
1620:
1617:
1614:
1589:
1586:
1581:
1572:
1550:
1546:
1542:
1539:
1519:
1510:
1495:
1472:
1460:
1446:
1426:
1422:
1418:
1415:
1409:
1406:
1400:
1394:
1388:
1379:
1363:
1359:
1354:
1350:
1347:
1339:
1335:
1331:
1325:
1319:
1316:
1311:
1307:
1303:
1297:
1291:
1285:
1263:
1259:
1255:
1250:
1246:
1225:
1222:
1219:
1199:
1196:
1193:
1187:
1184:
1181:
1178:
1175:
1172:
1161:
1156:
1142:
1122:
1099:
1076:
1057:
1051:
1048:
1042:
1036:
1016:
1013:
1010:
1004:
1001:
998:
995:
992:
989:
977:
963:
960:
954:
948:
945:
939:
933:
906:
883:
864:
858:
855:
849:
843:
823:
803:
783:
780:
777:
771:
768:
765:
762:
759:
756:
746:
745:
744:
742:
737:
723:
719:
715:
695:
675:
672:
669:
660:
642:
638:
634:
631:
608:
604:
600:
594:
585:
571:
551:
531:
527:
523:
514:
498:
489:
478:
464:
458:
455:
449:
443:
440:
437:
434:
431:
414:
411:
408:
405:
399:
396:
393:
390:
387:
384:
373:
351:
342:
339:
336:
330:
327:
318:
316:
312:
296:
276:
273:
270:
267:
259:
234:
214:
211:
203:
178:
175:
172:
149:
146:
143:
140:
137:
134:
131:
125:
119:
96:
76:
66:
65:Hash function
56:
54:
50:
46:
42:
38:
37:hash function
34:
30:
26:
22:
9711:
9688:. Retrieved
9684:
9675:
9638:
9626:
9611:
9596:
9583:
9566:
9539:
9535:
9489:
9485:
9472:
9467:, Equation 1
9462:
9454:
9447:
9438:
9434:
9387:
9383:
9350:
9344:
9326:
9314:. Retrieved
9305:(1): 19–51.
9302:
9298:
9295:(Postscript)
9285:
9260:
9257:Algorithmica
9256:
9212:
9199:
9186:
9167:
9161:
9149:. Retrieved
9142:the original
9128:
9109:
9105:
8819:
8803:
8450:
8395:
8371:
8367:
8363:
8359:
8355:
8351:
8341:
8196:
7744:
7689:
7687:
7633:
7337:
7330:
7245:
6960:integers on
6957:
6882:
6605:integers on
6602:
6527:
6504:
6213:
6070:
5872:
5012:
4873:
4869:
4867:
4521:
4519:
4249:
4247:
4158:
3806:
3628:
3351:
3060:
2894:To see that
2893:
2814:
2671:
2613:
2604:
2539:
2516:
1793:
1772:
1764:Poly1305-AES
1758:
1511:
1461:
1380:
1157:
1029:, the value
978:
925:
740:
738:
661:
624:rather than
586:
515:
371:
370:is called a
319:
314:
68:
59:Introduction
53:cryptography
28:
18:
9316:10 February
9003:bit masking
4667:, multiply
4252:universal:
2708:and define
45:hash tables
41:expectation
21:mathematics
9749:Categories
9690:2015-06-10
9227:1504.06804
9075:References
6956:of random
6601:of random
4903:; for any
3352:There are
63:See also:
9740:Pat Morin
9661:cite book
9549:1202.4961
9499:1011.5200
9392:CiteSeerX
9194:. p. 145.
8959:⌉
8945:⌈
8892:−
8760:ℓ
8682:ℓ
8642:ℓ
8619:¯
8610:−
8604:¯
8523:ℓ
8503:ℓ
8480:¯
8465:¯
8420:Kernighan
8392:Bernstein
8172:↦
8099:∈
8046:−
8043:ℓ
8035:⋅
8020:ℓ
8005:∑
7962:¯
7902:≥
7870:∈
7820:ℓ
7795:ℓ
7784:…
7759:¯
7536:−
7518:∑
7465:¯
7449:¯
7377:…
7352:¯
7296:⌉
7282:⌈
7225:−
7114:⋅
7074:⌉
7060:⌈
7045:∑
7020:¯
7004:¯
6936:−
6922:…
6897:¯
6862:−
6785:⋅
6767:−
6749:∑
6724:¯
6708:¯
6672:≤
6581:−
6567:…
6542:¯
6486:∈
6406:−
6388:∑
6370:¯
6267:−
6253:…
6228:¯
5901:−
5895:−
5839:−
5794:−
5785:…
5776:−
5707:is 1 and
5672:−
5640:−
5629:then bit
5579:≠
5524:−
5417:−
5351:−
5262:−
5236:−
5110:−
4987:≤
4914:≠
4845:−
4793:⋅
4472:−
4458:whenever
4423:≥
4344:≠
4310:≤
4141:≫
4070:±
4019:−
3978:−
3969:…
3914:−
3879:−
3870:…
3818:−
3750:−
3735:≡
3720:−
3673:−
3593:−
3562:−
3550:≤
3541:−
3527:⌋
3510:−
3501:⌊
3478:⌋
3461:−
3452:⌊
3363:−
3315:−
3304:−
3295:⋅
3289:⋅
3283:≡
3214:−
3188:≠
3152:≥
3115:−
3027:⋅
3006:≡
2872:≠
2683:≥
2651:−
2632:…
2542:rehashing
2341:−
2216:Ω
2095:−
2019:≠
1649:≤
1618:∈
1317:∧
1197:≠
1182:∈
1170:∀
1123:⊕
1049:⊕
1014:≠
999:∈
987:∀
946:−
856:−
781:≠
766:∈
754:∀
696:ϵ
670:ϵ
632:≤
479:≤
435:∈
409:≠
394:∈
382:∀
346:→
315:rehashing
274:⋅
176:⊆
147:−
138:…
25:computing
9710:(1998).
9484:(2011).
9382:(2009).
9248:(2008).
9100:(1979).
9014:See also
8907:, while
8808:and the
8495:and let
8088:, where
5277:. Since
4333:for all
4248:is only
3141:. Since
3081:between
1937:chaining
1739:′
1645:′
1607:for all
1590:′
657:example)
311:preimage
9760:Hashing
9591:. 1996.
9277:9855995
9151:24 June
9005:). The
8810:Buzhash
8424:Ritchie
4707:modulo
3932:modulo
3398:(since
3269:yields
796:, when
9718:
9649:
9514:
9412:
9394:
9275:
9174:
8334:return
8283:length
8211:String
8066:
7891:, let
7575:
7176:
6813:
6805:
6451:
6071:where
4558:. Let
4489:
4481:
4228:
4220:
4209:
4201:
4045:
4037:
3807:Since
3767:
3759:
2815:where
2795:
2787:
2776:
2768:
1191:
1115:where
1072:
1064:
1008:
879:
871:
775:
421:
418:
403:
51:, and
31:(in a
9575:(PDF)
9544:arXiv
9494:arXiv
9459:(PDF)
9273:S2CID
9253:(PDF)
9222:arXiv
9145:(PDF)
9138:(PDF)
8400:5381
8342:This
3177:, if
2861:with
2008:with
89:into
9716:ISBN
9667:link
9647:ISBN
9512:ISBN
9410:ISBN
9318:2011
9172:ISBN
9153:2009
8422:and
8396:djb2
8274:<
8256:uint
8238:uint
8205:hash
8202:uint
6661:for
6158:<
6127:and
6102:<
5918:and
5655:of
5492:<
5299:ring
5053:and
4589:<
3101:and
1782:and
1762:and
1760:UMAC
673:<
374:if,
268:>
23:and
9643:118
9634:"6"
9554:doi
9504:doi
9402:doi
9355:doi
9307:doi
9265:doi
9114:doi
8801:).
8445:31
8432:31
8403:33
8364:mod
8356:mod
8328:mod
8250:for
8229:int
8220:int
8062:mod
7905:max
7571:mod
7172:mod
6958:odd
6809:mod
6603:odd
6505:If
6447:mod
6287:of
6009:mod
5683:mod
5535:mod
5362:mod
5201:mod
5185:or
5161:mod
5121:mod
5069:mod
5029:mod
4870:not
4802:mod
4687:by
4485:mod
4224:mod
4205:mod
4041:mod
3783:mod
3763:mod
3697:as
3328:mod
3038:mod
2891:.)
2791:mod
2772:mod
1988:in
1907:is
1858:in
1814:of
1726:mod
1577:mod
1068:mod
875:mod
659:.
191:of
19:In
9751::
9738:,
9683:.
9663:}}
9659:{{
9645:.
9637:.
9552:.
9540:57
9538:.
9526:^
9510:.
9502:.
9488:.
9480:;
9461:.
9437:.
9425:^
9408:.
9400:.
9386:.
9367:^
9303:25
9301:.
9297:.
9271:.
9261:50
9259:.
9255:.
9236:^
9110:18
9108:.
9104:.
9082:^
8956:16
8887:61
8812:.
8442:0
8429:0
8414:5
8411:0
8386:a
8304:((
8289:++
7680:.
7668:32
6687::
5870:.
5010:.
4937:Pr
4929:,
4512:.
4367:Pr
4260:Pr
4156:.
2669:.
2597:.
743::
513:.
55:.
47:,
27:,
9724:.
9693:.
9669:)
9655:.
9620:.
9605:.
9577:.
9560:.
9556::
9546::
9520:.
9506::
9496::
9465:.
9418:.
9404::
9361:.
9357::
9338:.
9320:.
9309::
9279:.
9267::
9230:.
9224::
9180:.
9155:.
9116::
8987:w
8983:2
8952:/
8948:k
8920:i
8916:x
8895:1
8883:2
8879:=
8876:p
8856:p
8832:p
8785:p
8763:p
8755:+
8750:m
8747:1
8722:t
8719:n
8716:i
8711:h
8690:p
8686:/
8662:p
8616:y
8601:x
8578:a
8555:t
8552:n
8549:i
8544:h
8477:y
8471:,
8462:x
8372:h
8366:(
8360:p
8337:h
8331:p
8325:)
8322:x
8319:+
8316:)
8313:a
8310:*
8307:h
8301:=
8298:h
8295:)
8292:i
8286:;
8280:.
8277:x
8271:i
8268:;
8265:0
8262:=
8259:i
8253:(
8244:=
8241:h
8235:)
8232:p
8226:,
8223:a
8217:,
8214:x
8208:(
8193:.
8181:]
8178:m
8175:[
8169:]
8166:p
8163:[
8140:t
8137:n
8134:i
8129:h
8108:]
8105:p
8102:[
8096:a
8075:)
8071:p
8056:)
8049:i
8039:a
8030:i
8026:x
8015:0
8012:=
8009:i
7999:(
7993:(
7986:t
7983:n
7980:i
7975:h
7971:=
7968:)
7959:x
7953:(
7948:a
7944:h
7920:}
7917:m
7914:,
7911:u
7908:{
7899:p
7879:]
7876:u
7873:[
7865:i
7861:x
7840:x
7800:)
7791:x
7787:,
7781:,
7776:0
7772:x
7768:(
7765:=
7756:x
7730:s
7710:)
7707:s
7704:(
7701:h
7665:=
7662:w
7642:w
7630:.
7616:w
7612:2
7605:v
7602:i
7599:d
7593:)
7588:w
7585:2
7581:2
7565:i
7561:x
7555:1
7552:+
7549:i
7545:a
7539:1
7533:k
7528:0
7525:=
7522:i
7514:+
7509:0
7505:a
7501:(
7498:=
7492:g
7489:n
7486:o
7483:r
7480:t
7477:s
7472:)
7462:x
7456:(
7446:a
7440:h
7416:w
7413:2
7393:)
7388:k
7384:a
7380:,
7374:,
7369:0
7365:a
7361:(
7358:=
7349:a
7316:k
7293:2
7289:/
7285:k
7262:2
7258:/
7254:w
7242:.
7228:M
7222:w
7219:2
7215:2
7208:v
7205:i
7202:d
7195:)
7189:w
7186:2
7182:2
7166:)
7161:)
7156:1
7153:+
7150:i
7147:2
7143:a
7139:+
7134:1
7131:+
7128:i
7125:2
7121:x
7117:(
7111:)
7106:i
7103:2
7099:a
7095:+
7090:i
7087:2
7083:x
7079:(
7071:2
7067:/
7063:k
7055:0
7052:=
7049:i
7039:(
7033:(
7029:=
7026:)
7017:x
7011:(
7001:a
6995:h
6971:w
6968:2
6944:)
6939:1
6933:k
6929:a
6925:,
6919:,
6914:0
6910:a
6906:(
6903:=
6894:a
6879:.
6865:M
6859:w
6856:2
6852:2
6845:v
6842:i
6839:d
6832:)
6826:w
6823:2
6819:2
6800:)
6793:i
6789:a
6780:i
6776:x
6770:1
6764:k
6759:0
6756:=
6753:i
6743:(
6737:(
6733:=
6730:)
6721:x
6715:(
6705:a
6699:h
6675:w
6669:M
6647:M
6643:2
6639:=
6636:m
6616:w
6613:2
6589:)
6584:1
6578:k
6574:a
6570:,
6564:,
6559:0
6555:a
6551:(
6548:=
6539:a
6513:m
6489:H
6481:i
6477:h
6456:m
6441:)
6437:)
6432:i
6428:x
6424:(
6419:i
6415:h
6409:1
6403:k
6398:0
6395:=
6392:i
6383:(
6379:=
6376:)
6367:x
6361:(
6358:h
6335:H
6315:w
6295:k
6275:)
6270:1
6264:k
6260:x
6256:,
6250:,
6245:0
6241:x
6237:(
6234:=
6225:x
6194:w
6191:2
6169:w
6166:2
6162:2
6155:b
6135:b
6113:w
6110:2
6106:2
6099:a
6079:a
6056:,
6051:w
6047:2
6041:v
6038:i
6035:d
6030:)
6025:M
6022:+
6019:w
6013:2
6004:)
6001:b
5998:+
5995:x
5992:a
5989:(
5986:(
5983:=
5980:)
5977:x
5974:(
5969:b
5966:,
5963:a
5959:h
5935:x
5932:3
5929:=
5926:y
5904:2
5898:M
5892:w
5888:2
5884:=
5881:x
5858:m
5854:/
5850:2
5847:=
5842:1
5836:M
5832:2
5827:/
5823:1
5803:1
5800:+
5797:M
5791:w
5788:,
5782:,
5779:1
5773:w
5753:)
5750:y
5747:(
5742:a
5738:h
5734:=
5731:)
5728:x
5725:(
5720:a
5716:h
5693:w
5687:2
5678:)
5675:y
5669:x
5666:(
5663:a
5643:M
5637:w
5617:M
5614:=
5611:c
5591:)
5588:y
5585:(
5582:h
5576:)
5573:x
5570:(
5567:h
5545:w
5539:2
5530:)
5527:y
5521:x
5518:(
5515:a
5495:M
5489:c
5469:m
5465:/
5461:2
5458:=
5453:M
5449:2
5444:/
5440:2
5420:c
5414:w
5394:w
5372:w
5366:2
5357:)
5354:y
5348:x
5345:(
5342:a
5318:w
5314:2
5309:Z
5285:a
5265:c
5259:w
5239:y
5233:x
5211:w
5205:2
5196:y
5193:a
5171:w
5165:2
5156:x
5153:a
5131:w
5125:2
5116:)
5113:y
5107:x
5104:(
5101:a
5079:w
5073:2
5064:y
5061:a
5039:w
5033:2
5024:x
5021:a
4998:m
4994:/
4990:2
4984:}
4981:)
4978:y
4975:(
4970:a
4966:h
4962:=
4959:)
4956:x
4953:(
4948:a
4944:h
4940:{
4917:y
4911:x
4889:m
4885:/
4881:2
4853:.
4848:M
4842:w
4838:2
4831:v
4828:i
4825:d
4819:)
4814:w
4810:2
4796:x
4790:a
4787:(
4784:=
4781:)
4778:x
4775:(
4770:a
4766:h
4742:M
4720:w
4716:2
4695:a
4675:x
4655:)
4652:x
4649:(
4644:a
4640:h
4619:w
4597:w
4593:2
4586:a
4566:w
4544:M
4540:2
4536:=
4533:m
4500:1
4497:=
4494:m
4478:)
4475:1
4469:p
4466:(
4446:)
4443:1
4440:+
4437:m
4434:(
4430:/
4426:2
4420:}
4417:)
4414:1
4411:+
4408:m
4405:(
4400:a
4396:h
4392:=
4389:)
4386:1
4383:(
4378:a
4374:h
4370:{
4347:y
4341:x
4321:m
4317:/
4313:2
4307:}
4304:)
4301:y
4298:(
4293:a
4289:h
4285:=
4282:)
4279:x
4276:(
4271:a
4267:h
4263:{
4233:m
4217:)
4214:p
4198:x
4195:a
4192:(
4189:=
4186:)
4183:x
4180:(
4175:a
4171:h
4144:m
4138:p
4118:)
4115:p
4111:/
4107:m
4104:(
4101:O
4081:p
4077:/
4073:1
4050:m
4034:)
4031:)
4028:y
4025:(
4022:h
4016:)
4013:x
4010:(
4007:h
4004:(
3984:}
3981:1
3975:p
3972:,
3966:,
3963:1
3960:{
3940:p
3920:)
3917:y
3911:x
3908:(
3905:a
3885:}
3882:1
3876:p
3873:,
3867:,
3864:1
3861:{
3841:a
3821:y
3815:x
3803:.
3790:)
3787:m
3780:(
3775:)
3772:p
3756:)
3753:y
3747:x
3744:(
3741:a
3738:(
3732:)
3729:y
3726:(
3723:h
3717:)
3714:x
3711:(
3708:h
3685:)
3682:y
3679:(
3676:h
3670:)
3667:x
3664:(
3661:h
3637:H
3625:.
3613:m
3609:/
3605:1
3602:=
3599:)
3596:1
3590:p
3587:(
3583:/
3579:)
3576:m
3572:/
3568:)
3565:1
3559:p
3556:(
3553:(
3547:)
3544:1
3538:p
3535:(
3531:/
3524:m
3520:/
3516:)
3513:1
3507:p
3504:(
3475:m
3471:/
3467:)
3464:1
3458:p
3455:(
3432:i
3412:0
3409:=
3406:a
3386:a
3366:1
3360:p
3348:.
3335:)
3332:p
3325:(
3318:1
3311:)
3307:y
3301:x
3298:(
3292:m
3286:i
3280:a
3257:a
3237:p
3217:y
3211:x
3191:y
3185:x
3164:|
3160:U
3156:|
3149:p
3129:m
3125:/
3121:)
3118:1
3112:p
3109:(
3089:0
3069:i
3045:)
3042:p
3035:(
3030:m
3024:i
3021:+
3018:b
3015:+
3012:y
3009:a
3003:b
3000:+
2997:x
2994:a
2971:)
2968:y
2965:(
2962:h
2959:=
2956:)
2953:x
2950:(
2947:h
2927:}
2922:b
2919:,
2916:a
2912:h
2908:{
2905:=
2902:H
2875:0
2869:a
2849:p
2829:b
2826:,
2823:a
2800:m
2784:)
2781:p
2765:)
2762:b
2759:+
2756:x
2753:a
2750:(
2747:(
2744:=
2741:)
2738:x
2735:(
2730:b
2727:,
2724:a
2720:h
2695:|
2691:U
2687:|
2680:p
2657:}
2654:1
2647:|
2643:U
2639:|
2635:,
2629:,
2626:0
2623:{
2581:h
2561:)
2558:n
2555:(
2552:O
2525:S
2501:)
2498:m
2494:/
2490:1
2487:(
2484:O
2464:m
2460:/
2456:1
2436:)
2433:m
2430:(
2427:O
2407:m
2403:/
2399:n
2396:3
2393:=
2390:t
2370:)
2367:1
2364:+
2361:)
2358:m
2354:/
2350:n
2347:(
2344:2
2338:t
2335:(
2331:/
2327:n
2324:2
2304:t
2279:2
2275:n
2254:)
2251:n
2248:(
2245:O
2225:)
2222:n
2219:(
2196:n
2176:m
2156:)
2153:m
2149:/
2143:2
2139:n
2135:(
2132:O
2112:m
2109:2
2105:/
2101:)
2098:1
2092:n
2089:(
2086:n
2066:)
2063:y
2060:(
2057:h
2054:=
2051:)
2048:x
2045:(
2042:h
2022:y
2016:x
1996:S
1976:y
1973:,
1970:x
1947:x
1923:m
1919:/
1915:n
1895:)
1892:x
1889:(
1886:h
1866:S
1846:x
1822:n
1802:S
1736:L
1731:2
1722:x
1719:=
1716:)
1713:x
1710:(
1707:h
1687:x
1684:=
1681:)
1678:x
1675:(
1672:h
1652:L
1642:L
1621:H
1615:h
1587:L
1582:2
1573:h
1551:L
1547:2
1543:=
1540:m
1520:H
1496:m
1476:]
1473:m
1470:[
1447:z
1427:m
1423:/
1419:1
1416:=
1413:)
1410:z
1407:=
1404:)
1401:x
1398:(
1395:h
1392:(
1389:P
1364:2
1360:m
1355:/
1351:1
1348:=
1345:)
1340:2
1336:z
1332:=
1329:)
1326:y
1323:(
1320:h
1312:1
1308:z
1304:=
1301:)
1298:x
1295:(
1292:h
1289:(
1286:P
1264:2
1260:z
1256:,
1251:1
1247:z
1226:y
1223:,
1220:x
1200:y
1194:x
1188:,
1185:U
1179:y
1176:,
1173:x
1143:m
1103:]
1100:m
1097:[
1077:m
1061:)
1058:y
1055:(
1052:h
1046:)
1043:x
1040:(
1037:h
1017:y
1011:x
1005:,
1002:U
996:y
993:,
990:x
964:0
961:=
958:)
955:y
952:(
949:h
943:)
940:x
937:(
934:h
922:.
910:]
907:m
904:[
884:m
868:)
865:y
862:(
859:h
853:)
850:x
847:(
844:h
824:H
804:h
784:y
778:x
772:,
769:U
763:y
760:,
757:x
724:m
720:/
716:1
676:1
643:m
639:/
635:1
612:)
609:m
605:/
601:1
598:(
595:O
572:H
552:h
532:m
528:/
524:1
499:m
494:|
490:H
486:|
475:|
471:}
468:)
465:y
462:(
459:h
456:=
453:)
450:x
447:(
444:h
441::
438:H
432:h
429:{
425:|
415::
412:y
406:x
400:,
397:U
391:y
388:,
385:x
358:}
355:]
352:m
349:[
343:U
340::
337:h
334:{
331:=
328:H
297:S
277:n
271:m
264:|
260:U
256:|
235:S
215:n
212:=
208:|
204:S
200:|
179:U
173:S
153:}
150:1
144:m
141:,
135:,
132:0
129:{
126:=
123:]
120:m
117:[
97:m
77:U
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.