3057:. The stash, in this data structure, is an array of a constant number of keys, used to store keys that cannot successfully be inserted into the main hash table of the structure. This modification reduces the failure rate of cuckoo hashing to an inverse-polynomial function with an exponent that can be made arbitrarily large by increasing the stash size. However, larger stashes also mean slower searches for keys that are not present or are in the stash. A stash can be used in combination with more than two hash functions or with blocked cuckoo hashing to achieve both high load factors and small failure rates. The analysis of cuckoo hashing with a stash extends to practical hash functions, not just to the random hash function model commonly used in theoretical analysis of hashing.
114:, which happens when more than one key is mapped to the same cell. The basic idea of cuckoo hashing is to resolve collisions by using two hash functions instead of only one. This provides two possible locations in the hash table for each key. In one of the commonly used variants of the algorithm, the hash table is split into two smaller tables of equal size, and each hash function provides an index into one of these two tables. It is also possible for both hash functions to provide indexes into a single table.
20:
3111:-resident hash tables on modern processors. Kenneth Ross has shown bucketized versions of cuckoo hashing (variants that use buckets that contain more than one key) to be faster than conventional methods also for large hash tables, when space utilization is high. The performance of the bucketized cuckoo hash table was investigated further by Askitis, with its performance compared against alternative hashing schemes.
1815:, which is the fastest of the common approaches. The reason is that cuckoo hashing often causes two cache misses per search, to check the two locations where a key might be stored, while linear probing usually causes only one cache miss per search. However, because of its worst case guarantees on search time, cuckoo hashing can still be valuable when
3075:, replaces the stored keys of a cuckoo hash table with much shorter fingerprints, computed by applying another hash function to the keys. In order to allow these fingerprints to be moved around within the cuckoo filter, without knowing the keys that they came from, the two locations of each fingerprint may be computed from each other by a bitwise
1748:. With high probability, for load factor less than 1/2 (corresponding to a random graph in which the ratio of the number of edges to the number of vertices is bounded below 1/2), the graph is a pseudoforest and the cuckoo hashing algorithm succeeds in placing all keys. The same theory also proves that the expected size of a
1731:
called the "cuckoo graph" that has a vertex for each hash table location, and an edge for each hashed value, with the endpoints of the edge being the two possible locations of the value. Then, the greedy insertion algorithm for adding a set of values to a cuckoo hash table succeeds if and only if the
23:
Cuckoo hashing example. The arrows show the alternative location of each key. A new item would be inserted in the location of A by moving A to its alternative location, currently occupied by B, and moving B to its alternative location which is currently vacant. Insertion of a new item in the location
1951:
The following two tables show the insertion of some example elements. Each column corresponds to the state of the two hash tables over time. The possible insertion locations for each new value are highlighted. The last column illustrates a failed insertion due to a cycle, details below.
3130:'s recommendation system to solve the problem of "embedding table collisions", which can result in reduced model quality. The TikTok recommendation system "Monolith" takes advantage cuckoo hashing's collision resolution to prevent different concepts from being mapped to the same vectors.
3042:
Generalizations of cuckoo hashing that use more than two alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed. Using just three hash functions increases the load to 91%.
1803:, which is not 6-independent, but was shown in 2012 to have other properties sufficient for Cuckoo hashing. A third approach from 2014 is to slightly modify the cuckoo hashtable with a so-called stash, which makes it possible to use nothing more than 2-independent hash functions.
2948:
3038:
that it can tolerate to a number greater than the 50% threshold of the basic algorithm. Some of these methods can also be used to reduce the failure rate of cuckoo hashing, causing rebuilds of the data structure to be much less frequent.
1947:
1740:. Any vertex-induced subgraph with more edges than vertices corresponds to a set of keys for which there are an insufficient number of slots in the hash table. When the hash function is chosen randomly, the cuckoo graph is a
285:
1759:
Since a theoretical random hash function requires too much space for practical usage, an important theoretical question is which practical hash functions suffice for Cuckoo hashing. One approach is to use
1715:
Insertions succeed in expected constant time, even considering the possibility of having to rebuild the table, as long as the number of keys is kept below half of the capacity of the hash table, i.e., the
110:
is used to determine the location for each key, and its presence in the table (or the value associated with it) can be found by examining that cell of the table. However, open addressing suffers from
2872:
1877:
604:
1538:
1345:
1662:
3331:
AumĂĽller, Martin, Martin
Dietzfelbinger, and Philipp Woelfel. "Explicit and efficient hash families suffice for cuckoo hashing with a stash." Algorithmica 70.3 (2014): 428-456.
1047:
3079:
operation with the fingerprint, or with a hash of the fingerprint. This data structure forms an approximate set membership data structure with much the same properties as a
314:
1752:
of the cuckoo graph is small, ensuring that each insertion takes constant expected time. However, also with high probability, a load factor greater than 1/2 will lead to a
2816:
If you attempt to insert the element 45, then you get into a cycle, and fail. In the last row of the table we find the same initial situation as at the beginning again.
1797:
845:
453:
390:
1616:
994:
897:
1475:
1420:
1400:
1282:
1227:
1207:
1105:
1078:
1021:
969:
872:
711:
684:
637:
480:
417:
174:
147:
777:
740:
75:
2877:
1705:
1685:
1636:
917:
809:
657:
354:
334:
194:
1882:
3451:
AumĂĽller, Martin; Dietzfelbinger, Martin; Woelfel, Philipp (2014). "Explicit and efficient hash families suffice for cuckoo hashing with a stash".
3573:
3303:. Fourth Colloquium on Mathematics and Computer Science. Discrete Mathematics and Theoretical Computer Science. Vol. AG. pp. 403–406.
3749:
3313:
Cohen, Jeffrey S., and Daniel M. Kane. "Bounds on the independence required for cuckoo hashing." ACM Transactions on
Algorithms (2009).
199:
58:, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches in a variation of the behavior referred to as
3050:
uses more than one key per bucket and a balanced allocation scheme. Using just 2 keys per bucket permits a load factor above 80%.
3091:. However, it improves on a Bloom filter in multiple respects: its memory usage is smaller by a constant factor, it has better
3034:
Several variations of cuckoo hashing have been studied, primarily with the aim of improving its space usage by increasing the
3611:
3598:
3239:
3223:
3695:
3691:
3671:
3295:
62:; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table.
3322:
PÇŽtraĹźcu, Mihai, and Mikkel Thorup. "The power of simple tabulation hashing." Journal of the ACM (JACM) 59.3 (2012): 1-50.
3687:
2821:
1749:
1737:
1023:
by following the same procedure. The process continues until an empty position is found to insert the key. To avoid an
1832:
79:
874:
is occupied. If it is not, the item is inserted in that slot. However, if the slot is occupied, the existing item
779:
time since probing is not involved. This ignores the cost of the shrinking operation if the table is too sparse.
3416:
Kirsch, Adam; Mitzenmacher, Michael D.; Wieder, Udi (2010). "More robust hashing: cuckoo hashing with a stash".
3035:
1717:
24:
of H would not succeed: Since H is part of a cycle (together with W), the new item would get kicked out again.
3095:, and (unlike Bloom filters) it allows for fast deletion of set elements with no additional storage penalty.
501:
3545:
3083:: it can store the members of a set of keys, and test whether a query key is a member, with some chance of
1488:
1295:
48:
1641:
3769:
3280:
1745:
1030:
3061:
1108:
290:
3703:
3206:
3721:
3348:
3201:
1767:
814:
422:
359:
3092:
1761:
1557:
3681:
3517:
3482:
3437:
3402:
3344:
3115:
2943:{\displaystyle h'\left(45\right)=\left\lfloor {\frac {45}{11}}\right\rfloor {\bmod {1}}1=4}
1827:
The following hash functions are given (the two least significant digits of k in base 11):
1428:
1405:
1353:
1235:
1212:
1160:
1083:
1056:
999:
922:
850:
689:
662:
622:
458:
395:
152:
125:
32:
1799:-independence suffices, and at least 6-independence is needed. Another approach is to use
753:
716:
8:
1816:
788:
103:
974:
877:
3522:
Proc. 10th ACM Int. Conf. Emerging
Networking Experiments and Technologies (CoNEXT '14)
3486:
3460:
1942:{\displaystyle h'\left(k\right)=\left\lfloor {\frac {k}{11}}\right\rfloor {\bmod {1}}1}
1800:
1690:
1670:
1621:
902:
794:
642:
339:
319:
179:
3607:
3274:
3219:
3154:
3149:
3104:
3553:
Proceedings of the
International Workshop on Data Management on New Hardware (DaMoN)
1756:
with two or more cycles, causing the data structure to fail and need to be resized.
3774:
3744:
3525:
3490:
3470:
3425:
3388:
3211:
1728:
59:
3641:
3617:
3503:
3259:
196:
is the length of each table, the hash functions for the two tables is defined as,
3675:
3478:
3433:
3398:
3139:
1753:
91:
3668:
3144:
3088:
3084:
1812:
111:
36:
3739:
3474:
3393:
3376:
1111:
with new hash functions and the insertion procedure repeats. The following is
3763:
3377:"Balanced allocation and dictionaries with tightly packed constant size bins"
3251:
3215:
3103:
A study by
Zukowski et al. has shown that cuckoo hashing is much faster than
3072:
1554:
On lines 10 and 15, the "cuckoo approach" of kicking other keys which occupy
1024:
107:
51:
40:
3600:
Proceedings of the 32nd
Australasian Computer Science Conference (ACSC 2009)
3530:
3080:
3076:
3060:
Some people recommend a simplified generalization of cuckoo hashing called
1741:
1733:
1724:
3597:
Askitis, Nikolas (2009). "Fast and
Compact Hash Tables for Integer Keys".
1665:
3734:
3255:
3193:
1638:
is inserted into an empty slot in either of the two tables. The notation
71:
19:
3087:(queries that are incorrectly reported as being part of the set) but no
3708:
International
Colloquium on Automata, Languages and Programming (ICALP)
1112:
1050:
616:
99:
95:
44:
3429:
3754:
3247:
3240:"ESA - European Symposium on Algorithms: ESA Test-of-Time Award 2020"
3108:
3065:
54:
lookup time. The name derives from the behavior of some species of
3465:
3543:
280:{\displaystyle h_{1},\ h_{2}\ :\ \cup \rightarrow \{0,...,r-1\}}
3515:
3127:
55:
3724:, X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014.
3450:
3118:
presents open problems related to cuckoo hashing as of 2009.
3053:
Another variation of cuckoo hashing that has been studied is
2922:
2846:
1927:
1857:
3735:
Concurrent high-performance Cuckoo hashtable written in C++
3722:
3669:
A cool and practical alternative to traditional hash tables
3544:
Zukowski, Marcin; Heman, Sandor; Boncz, Peter (June 2006).
3701:
3520:(2014), "Cuckoo filter: Practically better than Bloom",
3415:
3339:
3337:
1811:
In practice, cuckoo hashing is about 20–30% slower than
3374:
1618:
repeats until every key has its own "nest", i.e. item
78:
in a 2001 conference paper. The paper was awarded the
3334:
3200:. Lecture Notes in Computer Science. Vol. 2161.
3098:
2880:
2824:
1885:
1835:
1770:
1693:
1673:
1644:
1624:
1560:
1491:
1431:
1408:
1356:
1298:
1238:
1215:
1163:
1086:
1059:
1033:
1002:
977:
925:
905:
880:
853:
817:
797:
756:
719:
692:
665:
645:
625:
504:
461:
425:
398:
362:
342:
322:
293:
202:
182:
155:
128:
3375:
Dietzfelbinger, Martin; Weidling, Christoph (2007).
3196:; Rodler, Flemming Friche (2001). "Cuckoo Hashing".
3642:"Monolith: The Recommendation System Behind TikTok"
3071:Another variation of a cuckoo hash table, called a
2942:
2866:
1941:
1871:
1791:
1699:
1679:
1656:
1630:
1610:
1532:
1469:
1414:
1394:
1339:
1276:
1221:
1201:
1099:
1072:
1041:
1015:
988:
963:
911:
891:
866:
839:
803:
771:
734:
705:
678:
651:
631:
598:
474:
447:
411:
384:
348:
328:
308:
279:
188:
168:
141:
2867:{\displaystyle h\left(45\right)=45{\bmod {1}}1=1}
3761:
3516:Fan, Bin; Andersen, Dave G.; Kaminsky, Michael;
3046:Another generalization of cuckoo hashing called
1736:, a graph with at most one cycle in each of its
3678:, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
3349:"Some Open Questions Related to Cuckoo Hashing"
1723:One method of proving this uses the theory of
1872:{\displaystyle h\left(k\right)=k{\bmod {1}}1}
3702:Naor, Moni; Segev, Gil; Wieder, Udi (2008).
3343:
811:, the first step involves examining if slot
274:
244:
3745:Static cuckoo hashtable generator for C/C++
3574:Efficient Hash Probes on Modern Processors
3297:Bipartite random graphs and cuckoo hashing
3293:
3192:
3529:
3464:
3392:
3205:
1732:cuckoo graph for this set of values is a
3188:
3186:
3184:
3182:
3180:
3178:
3176:
3174:
3172:
3170:
18:
3682:Cuckoo Hashing for Undergraduates, 2006
3596:
599:{\displaystyle T_{1}\ =\ x\vee T_{2}=x}
3762:
1544:17 rehash() 18 insert(x) 19
482:. The lookup operation is as follows:
70:Cuckoo hashing was first described by
3167:
1533:{\displaystyle \leftrightarrow T_{2}}
1340:{\displaystyle \leftrightarrow T_{1}}
639:) denotes that, the value of the key
122:Cuckoo hashing uses two hash tables,
3750:Cuckoo hash table written in Haskell
3704:"History-Independent Cuckoo Hashing"
3571:
356:is the set whose keys are stored in
3688:Cuckoo Hashing, Theory and Practice
1053:exceeds this fixed threshold, both
13:
3606:. Vol. 91. pp. 113–122.
3099:Comparison with related structures
1657:{\displaystyle x\leftrightarrow y}
1409:
1216:
294:
94:in which each non-empty cell of a
14:
3786:
3662:
1042:{\displaystyle {\text{Max-Loop}}}
3546:"Architecture-Conscious Hashing"
80:European Symposium on Algorithms
3634:
3590:
3579:(Research Report). IBM. RC24100
3565:
3537:
3509:
3497:
3444:
2769:
2764:
2687:
2683:
2644:
2621:
2619:
2610:
2541:
2524:
2333:
2330:
2324:
2257:
2242:
2179:
2176:
2129:
2117:
2114:
1049:is specified. If the number of
3740:Cuckoo hash map written in C++
3698:), Michael Mitzenmacher, 2007.
3409:
3368:
3325:
3316:
3307:
3287:
3232:
3121:
1786:
1774:
1648:
1605:
1602:
1596:
1577:
1527:
1524:
1518:
1505:
1492:
1464:
1461:
1455:
1442:
1389:
1386:
1380:
1367:
1334:
1331:
1325:
1312:
1299:
1271:
1268:
1262:
1249:
1196:
1193:
1187:
1174:
958:
955:
949:
936:
834:
828:
766:
760:
729:
723:
587:
584:
578:
565:
537:
534:
528:
515:
442:
436:
379:
373:
309:{\displaystyle \forall x\in S}
241:
1:
3294:Kutzelnigg, Reinhard (2006).
3160:
3029:
85:
16:Data structure hashing scheme
3572:Ross, Kenneth (2006-11-08).
1764:. In 2009 it was shown that
782:
90:Cuckoo hashing is a form of
82:Test-of-Time award in 2020.
7:
3728:
3133:
3055:cuckoo hashing with a stash
3007:100 replaces 105 in cell 9
2983:105 replaces 100 in cell 9
1806:
745:
10:
3791:
3126:Cuckoo hashing is used in
2502:
2392:
2073:
1963:
1822:
65:
3475:10.1007/s00453-013-9840-x
3394:10.1016/j.tcs.2007.02.054
3023:67 replaces 75 in cell 6
3015:50 replaces 45 in cell 4
3012:105 replaces 50 in cell 6
3004:67 replaces 100 in cell 1
2999:75 replaces 67 in cell 6
2991:45 replaces 53 in cell 4
2988:100 replaces 45 in cell 1
2980:50 replaces 105 in cell 6
2975:53 replaces 50 in cell 4
2967:67 replaces 75 in cell 6
2467:
2432:
2397:
2390:
2038:
2003:
1968:
1961:
1792:{\displaystyle O(\log n)}
1710:
750:Deletion is performed in
117:
3518:Mitzenmacher, Michael D.
3216:10.1007/3-540-44676-1_10
3062:skewed-associative cache
3020:45 replaces 67 in cell 1
2996:53 replaces 75 in cell 9
2972:75 replaces 53 in cell 9
2964:45 replaces 67 in cell 1
2811:
1817:real-time response rates
840:{\displaystyle h_{1}(x)}
448:{\displaystyle h_{2}(x)}
385:{\displaystyle h_{1}(x)}
3531:10.1145/2674005.2674994
3356:Proceedings of ESA 2009
1611:{\displaystyle T_{1,2}}
996:is inserted into table
3279:: CS1 maint: others (
3048:blocked cuckoo hashing
2944:
2868:
1943:
1873:
1793:
1701:
1681:
1658:
1632:
1612:
1534:
1477: := x 13
1471:
1416:
1396:
1341:
1284: := x 8
1278:
1223:
1203:
1101:
1074:
1043:
1017:
990:
965:
913:
893:
868:
841:
805:
773:
736:
707:
680:
653:
633:
600:
476:
449:
413:
386:
350:
330:
310:
281:
190:
170:
143:
76:Flemming Friche Rodler
25:
3755:Cuckoo hashing for Go
3345:Mitzenmacher, Michael
3198:Algorithms — ESA 2001
3093:locality of reference
2945:
2869:
1944:
1874:
1794:
1762:k-independent hashing
1702:
1682:
1659:
1633:
1613:
1535:
1472:
1470:{\displaystyle T_{2}}
1417:
1415:{\displaystyle \bot }
1397:
1395:{\displaystyle T_{2}}
1342:
1279:
1277:{\displaystyle T_{1}}
1224:
1222:{\displaystyle \bot }
1204:
1202:{\displaystyle T_{1}}
1102:
1100:{\displaystyle T_{2}}
1075:
1073:{\displaystyle T_{1}}
1044:
1018:
1016:{\displaystyle T_{2}}
991:
966:
964:{\displaystyle T_{1}}
914:
894:
869:
867:{\displaystyle T_{1}}
842:
806:
787:When inserting a new
774:
737:
708:
706:{\displaystyle T_{2}}
681:
679:{\displaystyle T_{1}}
654:
634:
632:{\displaystyle \vee }
601:
477:
475:{\displaystyle T_{2}}
450:
414:
412:{\displaystyle T_{1}}
387:
351:
331:
311:
282:
191:
171:
169:{\displaystyle T_{2}}
144:
142:{\displaystyle T_{1}}
22:
3710:. Reykjavik, Iceland
3504:"Micro-Architecture"
3381:Theoret. Comput. Sci
2878:
2822:
2386:Table 2: uses h′(k)
1883:
1833:
1768:
1738:connected components
1691:
1671:
1642:
1622:
1558:
1489:
1429:
1406:
1354:
1296:
1236:
1213:
1161:
1084:
1057:
1031:
1000:
975:
923:
903:
878:
851:
815:
795:
772:{\displaystyle O(1)}
754:
735:{\displaystyle O(1)}
717:
690:
663:
643:
623:
502:
459:
423:
396:
360:
340:
320:
291:
200:
180:
153:
126:
33:computer programming
3246:. Award committee:
2387:
1958:
1957:Table 1: uses h(k)
1750:connected component
659:is found in either
3674:2019-04-07 at the
3524:, pp. 75–88,
2940:
2864:
2504:Hash table entries
2385:
2075:Hash table entries
1956:
1939:
1869:
1801:tabulation hashing
1789:
1727:: one may form an
1697:
1677:
1654:
1628:
1608:
1530:
1467:
1412:
1392:
1337:
1274:
1219:
1199:
1097:
1070:
1039:
1013:
989:{\displaystyle x'}
986:
961:
909:
892:{\displaystyle x'}
889:
864:
837:
801:
769:
732:
703:
676:
649:
629:
596:
472:
445:
409:
382:
346:
326:
306:
277:
186:
166:
139:
26:
3770:Search algorithms
3613:978-1-920682-72-9
3430:10.1137/080728743
3244:esa-symposium.org
3225:978-3-540-42493-2
3155:Hopscotch hashing
3150:Quadratic probing
3027:
3026:
2915:
2808:
2807:
2381:
2380:
1920:
1746:Erdős–Rényi model
1700:{\displaystyle y}
1680:{\displaystyle x}
1631:{\displaystyle x}
1552:
1551:
1037:
912:{\displaystyle x}
804:{\displaystyle x}
652:{\displaystyle x}
613:
612:
548:
542:
349:{\displaystyle S}
329:{\displaystyle x}
237:
231:
218:
189:{\displaystyle r}
3782:
3718:
3716:
3715:
3684:, R. Pagh, 2006.
3656:
3655:
3653:
3652:
3638:
3632:
3631:
3629:
3628:
3622:
3616:. Archived from
3605:
3594:
3588:
3587:
3585:
3584:
3578:
3569:
3563:
3562:
3560:
3559:
3550:
3541:
3535:
3534:
3533:
3513:
3507:
3501:
3495:
3494:
3468:
3448:
3442:
3441:
3424:(4): 1543–1561.
3413:
3407:
3406:
3396:
3372:
3366:
3365:
3363:
3362:
3353:
3341:
3332:
3329:
3323:
3320:
3314:
3311:
3305:
3304:
3302:
3291:
3285:
3284:
3278:
3270:
3268:
3267:
3258:. Archived from
3236:
3230:
3229:
3209:
3190:
2953:
2952:
2949:
2947:
2946:
2941:
2930:
2929:
2920:
2916:
2908:
2899:
2888:
2873:
2871:
2870:
2865:
2854:
2853:
2838:
2388:
2384:
1959:
1955:
1948:
1946:
1945:
1940:
1935:
1934:
1925:
1921:
1913:
1904:
1893:
1878:
1876:
1875:
1870:
1865:
1864:
1849:
1798:
1796:
1795:
1790:
1729:undirected graph
1706:
1704:
1703:
1698:
1686:
1684:
1683:
1678:
1663:
1661:
1660:
1655:
1637:
1635:
1634:
1629:
1617:
1615:
1614:
1609:
1595:
1594:
1576:
1575:
1539:
1537:
1536:
1531:
1517:
1516:
1504:
1503:
1476:
1474:
1473:
1468:
1454:
1453:
1441:
1440:
1421:
1419:
1418:
1413:
1401:
1399:
1398:
1393:
1379:
1378:
1366:
1365:
1346:
1344:
1343:
1338:
1324:
1323:
1311:
1310:
1283:
1281:
1280:
1275:
1261:
1260:
1248:
1247:
1228:
1226:
1225:
1220:
1208:
1206:
1205:
1200:
1186:
1185:
1173:
1172:
1118:
1117:
1106:
1104:
1103:
1098:
1096:
1095:
1079:
1077:
1076:
1071:
1069:
1068:
1048:
1046:
1045:
1040:
1038:
1035:
1022:
1020:
1019:
1014:
1012:
1011:
995:
993:
992:
987:
985:
970:
968:
967:
962:
948:
947:
935:
934:
918:
916:
915:
910:
898:
896:
895:
890:
888:
873:
871:
870:
865:
863:
862:
846:
844:
843:
838:
827:
826:
810:
808:
807:
802:
778:
776:
775:
770:
741:
739:
738:
733:
712:
710:
709:
704:
702:
701:
685:
683:
682:
677:
675:
674:
658:
656:
655:
650:
638:
636:
635:
630:
605:
603:
602:
597:
577:
576:
564:
563:
546:
540:
527:
526:
514:
513:
485:
484:
481:
479:
478:
473:
471:
470:
454:
452:
451:
446:
435:
434:
418:
416:
415:
410:
408:
407:
391:
389:
388:
383:
372:
371:
355:
353:
352:
347:
335:
333:
332:
327:
315:
313:
312:
307:
286:
284:
283:
278:
235:
229:
228:
227:
216:
212:
211:
195:
193:
192:
187:
175:
173:
172:
167:
165:
164:
148:
146:
145:
140:
138:
137:
60:brood parasitism
3790:
3789:
3785:
3784:
3783:
3781:
3780:
3779:
3760:
3759:
3731:
3713:
3711:
3676:Wayback Machine
3665:
3660:
3659:
3650:
3648:
3640:
3639:
3635:
3626:
3624:
3620:
3614:
3603:
3595:
3591:
3582:
3580:
3576:
3570:
3566:
3557:
3555:
3548:
3542:
3538:
3514:
3510:
3502:
3498:
3449:
3445:
3414:
3410:
3373:
3369:
3360:
3358:
3351:
3342:
3335:
3330:
3326:
3321:
3317:
3312:
3308:
3300:
3292:
3288:
3272:
3271:
3265:
3263:
3238:
3237:
3233:
3226:
3191:
3168:
3163:
3140:Perfect hashing
3136:
3124:
3105:chained hashing
3101:
3089:false negatives
3085:false positives
3032:
2950:
2925:
2921:
2907:
2903:
2889:
2881:
2879:
2876:
2875:
2874:
2849:
2845:
2828:
2823:
2820:
2819:
2814:
2809:
2505:
2382:
2076:
1930:
1926:
1912:
1908:
1894:
1886:
1884:
1881:
1880:
1879:
1860:
1856:
1839:
1834:
1831:
1830:
1825:
1809:
1769:
1766:
1765:
1754:giant component
1713:
1692:
1689:
1688:
1672:
1669:
1668:
1643:
1640:
1639:
1623:
1620:
1619:
1584:
1580:
1565:
1561:
1559:
1556:
1555:
1548:
1512:
1508:
1499:
1495:
1490:
1487:
1486:
1449:
1445:
1436:
1432:
1430:
1427:
1426:
1407:
1404:
1403:
1374:
1370:
1361:
1357:
1355:
1352:
1351:
1319:
1315:
1306:
1302:
1297:
1294:
1293:
1256:
1252:
1243:
1239:
1237:
1234:
1233:
1214:
1211:
1210:
1181:
1177:
1168:
1164:
1162:
1159:
1158:
1115:for insertion:
1091:
1087:
1085:
1082:
1081:
1064:
1060:
1058:
1055:
1054:
1034:
1032:
1029:
1028:
1007:
1003:
1001:
998:
997:
978:
976:
973:
972:
943:
939:
930:
926:
924:
921:
920:
919:is inserted at
904:
901:
900:
899:is removed and
881:
879:
876:
875:
858:
854:
852:
849:
848:
822:
818:
816:
813:
812:
796:
793:
792:
785:
755:
752:
751:
748:
742:in worst case.
718:
715:
714:
697:
693:
691:
688:
687:
670:
666:
664:
661:
660:
644:
641:
640:
624:
621:
620:
609:
572:
568:
559:
555:
522:
518:
509:
505:
503:
500:
499:
466:
462:
460:
457:
456:
430:
426:
424:
421:
420:
403:
399:
397:
394:
393:
367:
363:
361:
358:
357:
341:
338:
337:
336:is the key and
321:
318:
317:
292:
289:
288:
223:
219:
207:
203:
201:
198:
197:
181:
178:
177:
160:
156:
154:
151:
150:
133:
129:
127:
124:
123:
120:
92:open addressing
88:
68:
37:hash collisions
31:is a scheme in
17:
12:
11:
5:
3788:
3778:
3777:
3772:
3758:
3757:
3752:
3747:
3742:
3737:
3730:
3727:
3726:
3725:
3719:
3699:
3685:
3679:
3664:
3663:External links
3661:
3658:
3657:
3633:
3612:
3589:
3564:
3536:
3508:
3496:
3459:(3): 428–456.
3443:
3418:SIAM J. Comput
3408:
3387:(1–2): 47–68.
3367:
3347:(2009-09-09).
3333:
3324:
3315:
3306:
3286:
3231:
3224:
3207:10.1.1.25.4189
3165:
3164:
3162:
3159:
3158:
3157:
3152:
3147:
3145:Double hashing
3142:
3135:
3132:
3123:
3120:
3100:
3097:
3031:
3028:
3025:
3024:
3021:
3017:
3016:
3013:
3009:
3008:
3005:
3001:
3000:
2997:
2993:
2992:
2989:
2985:
2984:
2981:
2977:
2976:
2973:
2969:
2968:
2965:
2961:
2960:
2957:
2939:
2936:
2933:
2928:
2924:
2919:
2914:
2911:
2906:
2902:
2898:
2895:
2892:
2887:
2884:
2863:
2860:
2857:
2852:
2848:
2844:
2841:
2837:
2834:
2831:
2827:
2813:
2810:
2806:
2805:
2803:
2801:
2799:
2797:
2795:
2793:
2791:
2789:
2787:
2785:
2781:
2780:
2777:
2774:
2771:
2768:
2765:
2763:
2761:
2759:
2757:
2755:
2751:
2750:
2748:
2746:
2744:
2742:
2740:
2738:
2736:
2734:
2732:
2730:
2726:
2725:
2723:
2721:
2719:
2717:
2715:
2713:
2711:
2709:
2707:
2705:
2701:
2700:
2697:
2694:
2691:
2688:
2686:
2684:
2682:
2680:
2678:
2676:
2672:
2671:
2669:
2667:
2665:
2663:
2661:
2659:
2657:
2655:
2653:
2651:
2647:
2646:
2643:
2640:
2637:
2634:
2631:
2628:
2625:
2622:
2620:
2618:
2614:
2613:
2611:
2609:
2607:
2605:
2603:
2601:
2599:
2597:
2595:
2593:
2589:
2588:
2586:
2584:
2582:
2580:
2578:
2576:
2574:
2572:
2570:
2568:
2564:
2563:
2560:
2557:
2554:
2551:
2548:
2545:
2542:
2540:
2538:
2536:
2532:
2531:
2528:
2525:
2523:
2521:
2519:
2517:
2515:
2513:
2511:
2509:
2506:
2503:
2500:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2478:
2475:
2472:
2469:
2465:
2464:
2461:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2437:
2434:
2430:
2429:
2426:
2423:
2420:
2417:
2414:
2411:
2408:
2405:
2402:
2399:
2395:
2394:
2391:
2383:
2379:
2378:
2376:
2374:
2372:
2370:
2368:
2366:
2364:
2362:
2360:
2358:
2354:
2353:
2350:
2347:
2344:
2341:
2338:
2335:
2332:
2329:
2326:
2323:
2319:
2318:
2316:
2314:
2312:
2310:
2308:
2306:
2304:
2302:
2300:
2298:
2294:
2293:
2291:
2289:
2287:
2285:
2283:
2281:
2279:
2277:
2275:
2273:
2269:
2268:
2265:
2262:
2259:
2256:
2253:
2250:
2247:
2244:
2241:
2239:
2235:
2234:
2232:
2230:
2228:
2226:
2224:
2222:
2220:
2218:
2216:
2214:
2210:
2209:
2207:
2205:
2203:
2201:
2199:
2197:
2195:
2193:
2191:
2189:
2185:
2184:
2181:
2178:
2175:
2173:
2171:
2169:
2167:
2165:
2163:
2161:
2157:
2156:
2154:
2152:
2150:
2148:
2146:
2144:
2142:
2140:
2138:
2136:
2132:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2111:
2109:
2107:
2105:
2101:
2100:
2098:
2096:
2094:
2092:
2090:
2088:
2086:
2084:
2082:
2080:
2077:
2074:
2071:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2036:
2035:
2032:
2029:
2026:
2023:
2020:
2017:
2014:
2011:
2008:
2005:
2001:
2000:
1997:
1994:
1991:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1966:
1965:
1962:
1954:
1938:
1933:
1929:
1924:
1919:
1916:
1911:
1907:
1903:
1900:
1897:
1892:
1889:
1868:
1863:
1859:
1855:
1852:
1848:
1845:
1842:
1838:
1824:
1821:
1819:are required.
1813:linear probing
1808:
1805:
1788:
1785:
1782:
1779:
1776:
1773:
1720:is below 50%.
1712:
1709:
1696:
1676:
1653:
1650:
1647:
1627:
1607:
1604:
1601:
1598:
1593:
1590:
1587:
1583:
1579:
1574:
1571:
1568:
1564:
1550:
1549:
1529:
1526:
1523:
1520:
1515:
1511:
1507:
1502:
1498:
1494:
1466:
1463:
1460:
1457:
1452:
1448:
1444:
1439:
1435:
1411:
1391:
1388:
1385:
1382:
1377:
1373:
1369:
1364:
1360:
1336:
1333:
1330:
1327:
1322:
1318:
1314:
1309:
1305:
1301:
1273:
1270:
1267:
1264:
1259:
1255:
1251:
1246:
1242:
1218:
1198:
1195:
1192:
1189:
1184:
1180:
1176:
1171:
1167:
1121:
1094:
1090:
1067:
1063:
1027:, a threshold
1010:
1006:
984:
981:
960:
957:
954:
951:
946:
942:
938:
933:
929:
908:
887:
884:
861:
857:
836:
833:
830:
825:
821:
800:
784:
781:
768:
765:
762:
759:
747:
744:
731:
728:
725:
722:
700:
696:
673:
669:
648:
628:
611:
610:
595:
592:
589:
586:
583:
580:
575:
571:
567:
562:
558:
554:
551:
545:
539:
536:
533:
530:
525:
521:
517:
512:
508:
488:
469:
465:
444:
441:
438:
433:
429:
406:
402:
381:
378:
375:
370:
366:
345:
325:
305:
302:
299:
296:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
240:
234:
226:
222:
215:
210:
206:
185:
163:
159:
136:
132:
119:
116:
104:key–value pair
87:
84:
67:
64:
41:hash functions
35:for resolving
29:Cuckoo hashing
15:
9:
6:
4:
3:
2:
3787:
3776:
3773:
3771:
3768:
3767:
3765:
3756:
3753:
3751:
3748:
3746:
3743:
3741:
3738:
3736:
3733:
3732:
3723:
3720:
3709:
3705:
3700:
3697:
3693:
3689:
3686:
3683:
3680:
3677:
3673:
3670:
3667:
3666:
3647:
3643:
3637:
3623:on 2011-02-16
3619:
3615:
3609:
3602:
3601:
3593:
3575:
3568:
3554:
3547:
3540:
3532:
3527:
3523:
3519:
3512:
3505:
3500:
3492:
3488:
3484:
3480:
3476:
3472:
3467:
3462:
3458:
3454:
3447:
3439:
3435:
3431:
3427:
3423:
3419:
3412:
3404:
3400:
3395:
3390:
3386:
3382:
3378:
3371:
3357:
3350:
3346:
3340:
3338:
3328:
3319:
3310:
3299:
3298:
3290:
3282:
3276:
3262:on 2021-05-22
3261:
3257:
3253:
3252:Samir Khuller
3249:
3245:
3241:
3235:
3227:
3221:
3217:
3213:
3208:
3203:
3199:
3195:
3189:
3187:
3185:
3183:
3181:
3179:
3177:
3175:
3173:
3171:
3166:
3156:
3153:
3151:
3148:
3146:
3143:
3141:
3138:
3137:
3131:
3129:
3119:
3117:
3112:
3110:
3106:
3096:
3094:
3090:
3086:
3082:
3078:
3074:
3073:cuckoo filter
3069:
3067:
3063:
3058:
3056:
3051:
3049:
3044:
3040:
3037:
3022:
3019:
3018:
3014:
3011:
3010:
3006:
3003:
3002:
2998:
2995:
2994:
2990:
2987:
2986:
2982:
2979:
2978:
2974:
2971:
2970:
2966:
2963:
2962:
2958:
2955:
2954:
2951:
2937:
2934:
2931:
2926:
2917:
2912:
2909:
2904:
2900:
2896:
2893:
2890:
2885:
2882:
2861:
2858:
2855:
2850:
2842:
2839:
2835:
2832:
2829:
2825:
2817:
2804:
2802:
2800:
2798:
2796:
2794:
2792:
2790:
2788:
2786:
2783:
2782:
2778:
2775:
2772:
2766:
2762:
2760:
2758:
2756:
2753:
2752:
2749:
2747:
2745:
2743:
2741:
2739:
2737:
2735:
2733:
2731:
2728:
2727:
2724:
2722:
2720:
2718:
2716:
2714:
2712:
2710:
2708:
2706:
2703:
2702:
2698:
2695:
2692:
2689:
2685:
2681:
2679:
2677:
2674:
2673:
2670:
2668:
2666:
2664:
2662:
2660:
2658:
2656:
2654:
2652:
2649:
2648:
2641:
2638:
2635:
2632:
2629:
2626:
2623:
2616:
2615:
2612:
2608:
2606:
2604:
2602:
2600:
2598:
2596:
2594:
2591:
2590:
2587:
2585:
2583:
2581:
2579:
2577:
2575:
2573:
2571:
2569:
2566:
2565:
2561:
2558:
2555:
2552:
2549:
2546:
2543:
2539:
2537:
2534:
2533:
2529:
2526:
2522:
2520:
2518:
2516:
2514:
2512:
2510:
2507:
2501:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2473:
2470:
2466:
2462:
2459:
2456:
2453:
2450:
2447:
2444:
2441:
2438:
2435:
2433:Key inserted
2431:
2427:
2424:
2421:
2418:
2415:
2412:
2409:
2406:
2403:
2400:
2396:
2389:
2377:
2375:
2373:
2371:
2369:
2367:
2365:
2363:
2361:
2359:
2356:
2355:
2351:
2348:
2345:
2342:
2339:
2336:
2327:
2321:
2320:
2317:
2315:
2313:
2311:
2309:
2307:
2305:
2303:
2301:
2299:
2296:
2295:
2292:
2290:
2288:
2286:
2284:
2282:
2280:
2278:
2276:
2274:
2271:
2270:
2266:
2263:
2260:
2254:
2251:
2248:
2245:
2240:
2237:
2236:
2233:
2231:
2229:
2227:
2225:
2223:
2221:
2219:
2217:
2215:
2212:
2211:
2208:
2206:
2204:
2202:
2200:
2198:
2196:
2194:
2192:
2190:
2187:
2186:
2182:
2174:
2172:
2170:
2168:
2166:
2164:
2162:
2159:
2158:
2155:
2153:
2151:
2149:
2147:
2145:
2143:
2141:
2139:
2137:
2134:
2133:
2126:
2123:
2120:
2112:
2110:
2108:
2106:
2103:
2102:
2099:
2097:
2095:
2093:
2091:
2089:
2087:
2085:
2083:
2081:
2078:
2072:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2041:
2037:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2004:Key inserted
2002:
1998:
1995:
1992:
1989:
1986:
1983:
1980:
1977:
1974:
1971:
1967:
1960:
1953:
1949:
1936:
1931:
1922:
1917:
1914:
1909:
1905:
1901:
1898:
1895:
1890:
1887:
1866:
1861:
1853:
1850:
1846:
1843:
1840:
1836:
1828:
1820:
1818:
1814:
1804:
1802:
1783:
1780:
1777:
1771:
1763:
1757:
1755:
1751:
1747:
1743:
1739:
1735:
1730:
1726:
1725:random graphs
1721:
1719:
1708:
1694:
1674:
1667:
1651:
1645:
1625:
1599:
1591:
1588:
1585:
1581:
1572:
1569:
1566:
1562:
1547:
1543:
1521:
1513:
1509:
1500:
1496:
1484:
1480:
1458:
1450:
1446:
1437:
1433:
1424:
1383:
1375:
1371:
1362:
1358:
1350:
1328:
1320:
1316:
1307:
1303:
1291:
1287:
1265:
1257:
1253:
1244:
1240:
1231:
1190:
1182:
1178:
1169:
1165:
1157:
1153:
1149:
1145:
1141:
1137:
1133:
1129:
1125:
1120:
1119:
1116:
1114:
1110:
1092:
1088:
1065:
1061:
1052:
1026:
1025:infinite loop
1008:
1004:
982:
979:
952:
944:
940:
931:
927:
906:
885:
882:
859:
855:
831:
823:
819:
798:
790:
780:
763:
757:
743:
726:
720:
698:
694:
671:
667:
646:
626:
618:
608:
593:
590:
581:
573:
569:
560:
556:
552:
549:
543:
531:
523:
519:
510:
506:
498:
495:
491:
487:
486:
483:
467:
463:
439:
431:
427:
404:
400:
376:
368:
364:
343:
323:
303:
300:
297:
271:
268:
265:
262:
259:
256:
253:
250:
247:
238:
232:
224:
220:
213:
208:
204:
183:
161:
157:
134:
130:
115:
113:
109:
108:hash function
105:
101:
97:
93:
83:
81:
77:
73:
63:
61:
57:
53:
50:
46:
42:
39:of values of
38:
34:
30:
21:
3712:. Retrieved
3707:
3649:. Retrieved
3645:
3636:
3625:. Retrieved
3618:the original
3599:
3592:
3581:. Retrieved
3567:
3556:. Retrieved
3552:
3539:
3521:
3511:
3499:
3456:
3453:Algorithmica
3452:
3446:
3421:
3417:
3411:
3384:
3380:
3370:
3359:. Retrieved
3355:
3327:
3318:
3309:
3296:
3289:
3264:. Retrieved
3260:the original
3243:
3234:
3197:
3194:Pagh, Rasmus
3125:
3116:Mitzenmacher
3114:A survey by
3113:
3102:
3081:Bloom filter
3077:exclusive or
3070:
3059:
3054:
3052:
3047:
3045:
3041:
3033:
2818:
2815:
2398:Step number
1969:Step number
1950:
1829:
1826:
1810:
1758:
1742:random graph
1734:pseudoforest
1722:
1714:
1553:
1546:end function
1545:
1541:
1482:
1478:
1422:
1348:
1289:
1285:
1229:
1155:
1151:
1147:
1143:
1139:
1135:
1131:
1127:
1123:
786:
749:
614:
607:end function
606:
496:
493:
489:
121:
89:
69:
28:
27:
3256:Edith Cohen
3122:Known users
3107:for small,
3036:load factor
1718:load factor
1485:15 x
1425:12
1292:10 x
1232:7
713:, which is
176:. Assuming
98:contains a
72:Rasmus Pagh
3764:Categories
3714:2008-07-21
3651:2023-05-30
3627:2010-06-13
3583:2008-10-16
3558:2008-10-16
3361:2010-11-10
3266:2021-05-22
3161:References
3066:CPU caches
3030:Variations
1664:expresses
1134:lookup(x)
1126:insert(x)
1113:pseudocode
1051:iterations
617:logical or
492:lookup(x)
112:collisions
96:hash table
86:Operations
49:worst-case
3690:(Part 1,
3646:gantry.io
3466:1204.4431
3248:Uri Zwick
3202:CiteSeerX
1781:
1649:↔
1493:↔
1481:14
1410:⊥
1347:11
1300:↔
1288:9
1217:⊥
1154:6
1150:Max-Loop
1138:3
847:of table
791:with key
783:Insertion
627:∨
553:∨
301:∈
295:∀
269:−
242:→
239:∪
3729:Examples
3672:Archived
3275:cite web
3134:See also
3064:in some
2959:Table 2
2956:Table 1
2918:⌋
2905:⌊
2886:′
1923:⌋
1910:⌊
1891:′
1807:Practice
1666:swapping
1542:end loop
1124:function
1109:rehashed
1036:Max-Loop
983:′
971:. Then,
886:′
746:Deletion
490:function
52:constant
3775:Hashing
3491:1888828
3483:3247374
3438:2580539
3403:2330641
1823:Example
1744:in the
1540:16
1146:5
1142:4
1130:2
66:History
47:, with
3696:Part 3
3692:Part 2
3610:
3489:
3481:
3436:
3401:
3222:
3204:
3128:TikTok
2468:h′(k)
2393:Steps
1964:Steps
1711:Theory
1483:end if
1479:return
1290:end if
1286:return
1144:end if
1140:return
547:
541:
497:return
316:where
236:
230:
217:
118:Lookup
56:cuckoo
3621:(PDF)
3604:(PDF)
3577:(PDF)
3549:(PDF)
3487:S2CID
3461:arXiv
3352:(PDF)
3301:(PDF)
3109:cache
2812:Cycle
2039:h(k)
1152:times
1122:1
45:table
43:in a
3694:and
3608:ISBN
3281:link
3220:ISBN
2779:100
2267:105
1687:and
1423:then
1230:then
1148:loop
1136:then
1107:are
1080:and
789:item
615:The
287:and
149:and
106:. A
74:and
3526:doi
3471:doi
3426:doi
3389:doi
3385:380
3212:doi
2923:mod
2847:mod
2784:10
2776:100
2773:100
2770:100
2767:100
2699:75
2645:50
2562:20
2463:45
2454:105
2448:100
2428:10
2357:10
2352:53
2264:105
2261:105
2258:105
2183:36
2130:45
2115:100
2034:45
2025:105
2019:100
1999:10
1928:mod
1858:mod
1778:log
686:or
455:of
419:or
392:of
102:or
100:key
3766::
3706:.
3644:.
3551:.
3485:.
3479:MR
3477:.
3469:.
3457:70
3455:.
3434:MR
3432:.
3422:39
3420:.
3399:MR
3397:.
3383:.
3379:.
3354:.
3336:^
3277:}}
3273:{{
3254:,
3250:,
3242:.
3218:.
3210:.
3169:^
3068:.
2913:11
2910:45
2894:45
2843:45
2833:45
2754:9
2729:8
2704:7
2696:75
2693:75
2690:75
2675:6
2650:5
2642:50
2639:50
2636:50
2633:53
2630:53
2627:53
2624:53
2617:4
2592:3
2567:2
2559:20
2556:20
2553:20
2550:20
2547:20
2544:20
2535:1
2530:3
2508:0
2498:4
2460:36
2451:67
2445:75
2442:20
2439:50
2436:53
2349:53
2346:53
2343:53
2340:75
2337:75
2334:75
2331:20
2328:53
2325:53
2322:9
2297:8
2272:7
2255:50
2252:50
2249:50
2246:50
2243:50
2238:6
2213:5
2188:4
2180:36
2160:3
2135:2
2127:67
2124:67
2121:67
2118:67
2104:1
2079:0
2069:1
2031:36
2022:67
2016:75
2013:20
2010:50
2007:53
1918:11
1707:.
1402:=
1349:if
1209:=
1156:if
1132:if
1128:is
494:is
3717:.
3654:.
3630:.
3586:.
3561:.
3528::
3506:.
3493:.
3473::
3463::
3440:.
3428::
3405:.
3391::
3364:.
3283:)
3269:.
3228:.
3214::
2938:4
2935:=
2932:1
2927:1
2901:=
2897:)
2891:(
2883:h
2862:1
2859:=
2856:1
2851:1
2840:=
2836:)
2830:(
2826:h
2527:3
2495:3
2492:0
2489:9
2486:6
2483:9
2480:6
2477:1
2474:4
2471:4
2457:3
2425:9
2422:8
2419:7
2416:6
2413:5
2410:4
2407:3
2404:2
2401:1
2177:3
2066:3
2063:3
2060:6
2057:1
2054:1
2051:9
2048:9
2045:6
2042:9
2028:3
1996:9
1993:8
1990:7
1987:6
1984:5
1981:4
1978:3
1975:2
1972:1
1937:1
1932:1
1915:k
1906:=
1902:)
1899:k
1896:(
1888:h
1867:1
1862:1
1854:k
1851:=
1847:)
1844:k
1841:(
1837:h
1787:)
1784:n
1775:(
1772:O
1695:y
1675:x
1652:y
1646:x
1626:x
1606:]
1603:)
1600:x
1597:(
1592:2
1589:,
1586:1
1582:h
1578:[
1573:2
1570:,
1567:1
1563:T
1528:]
1525:)
1522:x
1519:(
1514:2
1510:h
1506:[
1501:2
1497:T
1465:]
1462:)
1459:x
1456:(
1451:2
1447:h
1443:[
1438:2
1434:T
1390:]
1387:)
1384:x
1381:(
1376:2
1372:h
1368:[
1363:2
1359:T
1335:]
1332:)
1329:x
1326:(
1321:1
1317:h
1313:[
1308:1
1304:T
1272:]
1269:)
1266:x
1263:(
1258:1
1254:h
1250:[
1245:1
1241:T
1197:]
1194:)
1191:x
1188:(
1183:1
1179:h
1175:[
1170:1
1166:T
1093:2
1089:T
1066:1
1062:T
1009:2
1005:T
980:x
959:]
956:)
953:x
950:(
945:1
941:h
937:[
932:1
928:T
907:x
883:x
860:1
856:T
835:)
832:x
829:(
824:1
820:h
799:x
767:)
764:1
761:(
758:O
730:)
727:1
724:(
721:O
699:2
695:T
672:1
668:T
647:x
619:(
594:x
591:=
588:]
585:)
582:x
579:(
574:2
570:h
566:[
561:2
557:T
550:x
544:=
538:]
535:)
532:x
529:(
524:1
520:h
516:[
511:1
507:T
468:2
464:T
443:)
440:x
437:(
432:2
428:h
405:1
401:T
380:)
377:x
374:(
369:1
365:h
344:S
324:x
304:S
298:x
275:}
272:1
266:r
263:,
260:.
257:.
254:.
251:,
248:0
245:{
233::
225:2
221:h
214:,
209:1
205:h
184:r
162:2
158:T
135:1
131:T
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
