66:
was first solved in general by
Fredman, Komlós and Szemerédi. In their 1984 paper, they detail a two-tiered hash table scheme in which each bucket of the (first-level) hash table corresponds to a separate second-level hash table. Keys are hashed twice—the first hash value maps to a certain bucket in
607:
space of the table is to prompt a full reconstruction when a sufficient number of insertions and deletions have occurred. By results due to
Dietzfelbinger et al., as long as the total number of insertions or deletions exceeds the number of elements at the time of last construction, the amortized
480:
In the dynamic case, when a key is inserted into the hash table, if its entry in its respective subtable is occupied, then a collision is said to occur and the subtable is rebuilt based on its new total entry count and randomly selected hash function. Because the
221:) and stored alongside the hash table. If the hash function randomly selected creates a table with collisions, a new hash function is randomly selected until a collision-free table can be guaranteed. Finally, with the collision-free hash, the
1584:
1990:
386:
Dietzfelbinger et al. present a dynamic dictionary algorithm that, when a set of n items is incrementally added to the dictionary, membership queries always run in constant time and therefore
38:. While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements.
67:
the first-level hash table; the second hash value gives the position of that entry in that bucket's second-level hash table. The second-level table is guaranteed to be collision-free (i.e.
372:
1987:
482:
176:
124:
259:, providing linear amortized construction time. Although each second-level table requires quadratic space, if the keys inserted into the first-level hash table are
253:
207:
635:
605:
573:
544:
471:
442:
413:
334:
290:
511:
578:
Additionally, the ultimate sizes of the top-level table or any of the subtables is unknowable in the dynamic case. One method for maintaining expected
1483:
1959:
Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544
85:
entries, each one with a unique key, ahead of time. Fredman, Komlós and Szemerédi pick a first-level hash table with size
260:
1986:
Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
2017:
255:
space ensures that randomly creating a table with collisions is infrequent and independent of the size of
2068:
2031:
640:
The implementation of dynamic perfect hashing by
Dietzfelbinger et al. uses these concepts, as well as
339:
1447:
first starts by removing all elements marked as deleted and then setting the next threshold value
474:
214:
140:
88:
218:
75:
231:
185:
57:
611:
581:
549:
520:
447:
418:
389:
310:
266:
8:
488:
16:
Programming technique for resolving duplicate hash values in a hash table data structure
514:
1347:)" is a representation of an element which is not in the set of all possible elements
299:
The first-level hash function is specifically chosen so that, for the specific set of
375:
2063:
2001:
20:
1994:
1935:
68:
1998:
378:
family of hash functions, at least half of those functions have that property.
72:
63:
35:
28:
2005:
1960:
2057:
1579:{\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}
641:
210:
2020:. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.
1343:
refers to the time between full rebuilds. Note that here the -1 in "Delete(
783:, and is not marked as deleted, then a collision is said to occur and the
881:
is marked deleted) remove the delete marker;
293:
71:) upon construction. Consequently, the look-up cost is guaranteed to be
32:
1335:
is some constant multiple of the size of S at the start of a new
794:
is rebuilt with a different randomly selected hash function
546:. Similarly, the amortized expected cost of deletions is
1623:. The expected time for a full rebuild of the table of
81:
In the static case, we are given a set with a total of
765:, but is marked as deleted, then the mark is removed.
307:
used by all the second-level hash tables has expected
1486:
614:
584:
552:
523:
491:
450:
421:
392:
342:
313:
269:
234:
188:
143:
91:
374:. Fredman, Komlós and Szemerédi showed that given a
1323:. In the case of both insertions and deletions, if
1165:; Put all unmarked elements of
1578:
629:
599:
567:
538:
505:
465:
436:
407:
366:
328:
284:
247:
201:
170:
118:
1988:"Dynamic Perfect Hashing: Upper and Lower Bounds"
137:buckets by the top-level hashing function, where
2055:
1982:
1980:
1978:
1976:
1974:
1972:
1970:
1968:
473:expected amortized insertion and deletion time (
225:entries are hashed into the second-level table.
182:entries, a second-level table is allocated with
608:expected cost of insertion and deletion remain
415:worst-case time, the total storage required is
1997:. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
637:with full rehashing taken into consideration.
292:space, since bucket sizes are small with high
1965:
263:, the structure as a whole occupies expected
1999:http://portal.acm.org/citation.cfm?id=182370
647:
2032:"Universal Construction for the FKS Scheme"
1961:http://portal.acm.org/citation.cfm?id=1884#
1955:
1953:
1951:
1319:as deleted without removal and increments
1451:to some constant multiple of the size of
217:set so that it is collision-free (i.e. a
27:is a programming technique for resolving
1948:
1478:, is repeatedly randomly chosen until:
2056:
485:of the second-level table is kept low
1874:is injective on the elements of list
1467:) subsets, where the size of subset
1455:. A hash function, which partitions
943:is empty store
742:During the insertion of a new entry
644:, and is shown in pseudocode below.
513:, rebuilding is infrequent, and the
1602:is repeatedly randomly chosen from
1331:the entire table is rebuilt, where
303:unique key values, the total space
13:
14:
2080:
750:, the global operations counter,
58:static hashing § FKS Hashing
1704:h = randomly chosen function in
1616:is injective on the elements of
1231:is injective on the elements of
1037:is injective on the elements of
2029:
2018:6.897: Advanced Data Structures
1443:A full rebuild of the table of
1438:
517:expected cost of insertions is
381:
367:{\displaystyle T<s+4\cdot x}
2023:
2010:
1857:= randomly chosen function in
1558:
1552:
1513:
1507:
1429:) FullRehash(-1);
1414:(x is not a member of S);
1214:= randomly chosen function in
1020:= randomly chosen function in
624:
618:
594:
588:
562:
556:
533:
527:
460:
454:
431:
425:
402:
396:
323:
317:
279:
273:
165:
153:
113:
101:
46:
1:
1941:
1649:Put all unmarked elements of
1179:; Append
985:; Append
971:Put all unmarked elements of
336:space, and more specifically
213:is selected at random from a
51:
787:bucket's second-level table
178:. Then for each bucket with
7:
1929:
1727:) form a list
1588:Finally, for each subtable
133:entries are separated into
10:
2085:
1833:) Allocate space
228:The quadratic size of the
55:
41:
2016:Erik Demaine, Jeff Lind.
2006:10.1137/S0097539791194094
1306:
737:
652:
648:Pseudocode implementation
171:{\displaystyle s=2(x-1)}
119:{\displaystyle s=2(x-1)}
698:(not deleted))
475:amortized constant time
215:universal hash function
62:The problem of optimal
25:dynamic perfect hashing
1798:the sum total of all s
1580:
1274:;
1238:;
1221:;
1204:;
1190:;
1131:the sum total of all s
1127:- 1);
1080:;
1044:;
1027:;
1010:;
996:;
834:) FullRehash(
631:
601:
569:
540:
507:
467:
438:
409:
368:
330:
286:
249:
203:
172:
120:
2038:. New York University
1581:
632:
602:
570:
541:
508:
468:
439:
410:
369:
331:
287:
261:uniformly distributed
250:
248:{\displaystyle k^{2}}
219:perfect hash function
204:
202:{\displaystyle k^{2}}
173:
121:
1484:
1327:reaches a threshold
630:{\displaystyle O(1)}
612:
600:{\displaystyle O(n)}
582:
568:{\displaystyle O(1)}
550:
539:{\displaystyle O(1)}
521:
489:
466:{\displaystyle O(1)}
448:
437:{\displaystyle O(n)}
419:
408:{\displaystyle O(1)}
390:
340:
329:{\displaystyle O(n)}
311:
285:{\displaystyle O(n)}
267:
232:
186:
141:
89:
2036:New York University
1288:);
1106:};
922:)
776:or at the subtable
506:{\displaystyle 1/k}
1993:2016-03-04 at the
1669:) append
1576:
1517:
964:;
754:, is incremented.
627:
597:
565:
536:
503:
463:
434:
405:
364:
326:
282:
245:
199:
168:
116:
2069:Search algorithms
1684:= length of list
1562:
1487:
904:+ 1;
376:universal hashing
76:in the worst-case
2076:
2048:
2047:
2045:
2043:
2027:
2021:
2014:
2008:
1984:
1963:
1957:
1595:a hash function
1585:
1583:
1582:
1577:
1563:
1561:
1547:
1546:
1545:
1532:
1527:
1526:
1516:
1404:as deleted;
862:(x) of subtable
636:
634:
633:
628:
606:
604:
603:
598:
574:
572:
571:
566:
545:
543:
542:
537:
512:
510:
509:
504:
499:
472:
470:
469:
464:
443:
441:
440:
435:
414:
412:
411:
406:
373:
371:
370:
365:
335:
333:
332:
327:
306:
302:
291:
289:
288:
283:
258:
254:
252:
251:
246:
244:
243:
224:
208:
206:
205:
200:
198:
197:
181:
177:
175:
174:
169:
136:
132:
125:
123:
122:
117:
84:
21:computer science
2084:
2083:
2079:
2078:
2077:
2075:
2074:
2073:
2054:
2053:
2052:
2051:
2041:
2039:
2028:
2024:
2015:
2011:
1995:Wayback Machine
1985:
1966:
1958:
1949:
1944:
1936:Perfect hashing
1932:
1927:
1918:
1908:
1897:
1879:
1872:
1862:
1855:
1845:
1838:
1801:
1789:
1782:
1775:
1770:;
1768:
1761:
1756:;
1754:
1747:
1732:
1709:
1621:
1614:
1607:
1600:
1593:
1548:
1541:
1537:
1533:
1531:
1522:
1518:
1491:
1485:
1482:
1481:
1476:
1441:
1436:
1387:
1309:
1304:
1272:
1262:
1251:
1236:
1229:
1219:
1212:
1202:
1195:
1188:
1177:
1170:
1163:
1156:
1134:
1125:
1118:
1111:
1104:
1097:
1078:
1068:
1057:
1042:
1035:
1025:
1018:
1008:
1001:
994:
983:
976:
962:
952:
941:
931:
920:
913:
902:
895:
867:
861:
799:
792:
781:
740:
735:
692:
682:
655:
650:
613:
610:
609:
583:
580:
579:
551:
548:
547:
522:
519:
518:
495:
490:
487:
486:
449:
446:
445:
420:
417:
416:
391:
388:
387:
384:
341:
338:
337:
312:
309:
308:
304:
300:
268:
265:
264:
256:
239:
235:
233:
230:
229:
222:
209:slots, and its
193:
189:
187:
184:
183:
179:
142:
139:
138:
134:
130:
90:
87:
86:
82:
69:perfect hashing
60:
54:
49:
44:
17:
12:
11:
5:
2082:
2072:
2071:
2066:
2050:
2049:
2022:
2009:
1964:
1946:
1945:
1943:
1940:
1939:
1938:
1931:
1928:
1916:
1904:
1895:
1877:
1870:
1860:
1853:
1843:
1836:
1799:
1791:- 1);
1787:
1780:
1773:
1766:
1759:
1752:
1745:
1742:;
1730:
1707:
1637:
1619:
1612:
1605:
1598:
1591:
1575:
1572:
1569:
1566:
1560:
1557:
1554:
1551:
1544:
1540:
1536:
1530:
1525:
1521:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1490:
1474:
1440:
1437:
1392:) of subtable
1385:
1353:
1308:
1305:
1270:
1258:
1249:
1234:
1227:
1217:
1210:
1200:
1193:
1186:
1175:
1168:
1161:
1154:
1132:
1123:
1116:
1109:
1102:
1095:
1076:
1064:
1055:
1040:
1033:
1023:
1016:
1006:
999:
992:
981:
974:
960:
948:
939:
927:
918:
911:
900:
893:
873:)
865:
857:
803:
797:
790:
779:
739:
736:
690:
687:) of subtable
680:
656:
654:
651:
649:
646:
626:
623:
620:
617:
596:
593:
590:
587:
564:
561:
558:
555:
535:
532:
529:
526:
502:
498:
494:
462:
459:
456:
453:
444:(linear), and
433:
430:
427:
424:
404:
401:
398:
395:
383:
380:
363:
360:
357:
354:
351:
348:
345:
325:
322:
319:
316:
281:
278:
275:
272:
242:
238:
196:
192:
167:
164:
161:
158:
155:
152:
149:
146:
129:To construct,
115:
112:
109:
106:
103:
100:
97:
94:
64:static hashing
56:Main article:
53:
50:
48:
45:
43:
40:
36:data structure
15:
9:
6:
4:
3:
2:
2081:
2070:
2067:
2065:
2062:
2061:
2059:
2037:
2033:
2026:
2019:
2013:
2007:
2003:
2000:
1996:
1992:
1989:
1983:
1981:
1979:
1977:
1975:
1973:
1971:
1969:
1962:
1956:
1954:
1952:
1947:
1937:
1934:
1933:
1926:
1923:
1919:
1912:
1907:
1903:in position h
1902:
1898:
1891:
1887:
1884:
1880:
1873:
1867:
1863:
1856:
1850:
1846:
1840:for subtable
1839:
1832:
1828:
1824:
1820:
1817:
1813:
1809:
1805:
1797:
1794:
1790:
1783:
1776:
1769:
1762:
1755:
1748:
1741:
1737:
1733:
1726:
1722:
1718:
1714:
1710:
1703:
1699:
1695:
1691:
1687:
1683:
1680:
1676:
1672:
1668:
1664:
1660:
1656:
1652:
1648:
1644:
1640:
1636:
1634:
1630:
1626:
1622:
1615:
1608:
1601:
1594:
1586:
1573:
1570:
1567:
1564:
1555:
1549:
1542:
1538:
1534:
1528:
1523:
1519:
1510:
1504:
1501:
1498:
1495:
1492:
1488:
1479:
1477:
1470:
1466:
1462:
1458:
1454:
1450:
1446:
1435:
1432:
1428:
1424:
1420:
1417:
1413:
1410:
1407:
1403:
1399:
1395:
1391:
1383:
1379:
1375:
1371:
1367:
1364:
1360:
1356:
1352:
1350:
1346:
1342:
1338:
1334:
1330:
1326:
1322:
1318:
1315:simply flags
1314:
1303:
1300:
1297:
1294:
1291:
1287:
1283:
1280:
1277:
1273:
1266:
1261:
1257:in position h
1256:
1252:
1245:
1241:
1237:
1230:
1224:
1220:
1213:
1207:
1203:
1196:
1189:
1182:
1178:
1171:
1164:
1157:
1150:
1146:
1142:
1138:
1130:
1126:
1119:
1112:
1105:
1099:= 2 * max{1,
1098:
1092:
1089:
1086:
1083:
1079:
1072:
1067:
1063:in position h
1062:
1058:
1051:
1047:
1043:
1036:
1030:
1026:
1019:
1013:
1009:
1002:
995:
988:
984:
977:
970:
967:
963:
956:
951:
947:in position h
946:
942:
935:
930:
925:
921:
914:
907:
903:
896:
890:
887:
884:
880:
876:
872:
868:
860:
855:
851:
847:
844:
841:
837:
833:
829:
825:
821:
817:
814:
810:
806:
802:
800:
793:
786:
782:
775:
771:
766:
764:
760:
755:
753:
749:
745:
734:
731:
727:
723:
719:
716:
713:
709:
705:
701:
697:
693:
686:
678:
674:
670:
667:
663:
659:
645:
643:
642:lazy deletion
638:
621:
615:
591:
585:
576:
559:
553:
530:
524:
516:
500:
496:
492:
484:
478:
476:
457:
451:
428:
422:
399:
393:
379:
377:
361:
358:
355:
352:
349:
346:
343:
320:
314:
297:
295:
276:
270:
262:
240:
236:
226:
220:
216:
212:
211:hash function
194:
190:
162:
159:
156:
150:
147:
144:
127:
110:
107:
104:
98:
95:
92:
79:
77:
74:
70:
65:
59:
39:
37:
34:
30:
26:
22:
2040:. Retrieved
2035:
2025:
2012:
1924:
1921:
1914:
1910:
1905:
1900:
1893:
1889:
1885:
1882:
1875:
1868:
1865:
1858:
1851:
1848:
1841:
1834:
1830:
1826:
1822:
1818:
1815:
1811:
1807:
1803:
1795:
1792:
1785:
1778:
1771:
1764:
1757:
1750:
1749:= length of
1743:
1739:
1735:
1728:
1724:
1720:
1716:
1712:
1705:
1701:
1697:
1693:
1689:
1685:
1681:
1678:
1674:
1670:
1666:
1662:
1658:
1654:
1650:
1646:
1642:
1638:
1632:
1628:
1624:
1617:
1610:
1603:
1596:
1589:
1587:
1480:
1472:
1468:
1464:
1460:
1456:
1452:
1448:
1444:
1442:
1439:Full rebuild
1433:
1430:
1426:
1422:
1418:
1415:
1411:
1408:
1405:
1401:
1397:
1393:
1389:
1381:
1377:
1373:
1369:
1365:
1362:
1358:
1354:
1348:
1344:
1340:
1336:
1332:
1328:
1324:
1320:
1316:
1312:
1311:Deletion of
1310:
1301:
1298:
1295:
1292:
1289:
1285:
1281:
1278:
1275:
1268:
1264:
1259:
1254:
1247:
1243:
1239:
1232:
1225:
1222:
1215:
1208:
1205:
1198:
1197:= length of
1191:
1184:
1180:
1173:
1166:
1159:
1152:
1148:
1144:
1140:
1136:
1128:
1121:
1114:
1107:
1100:
1093:
1090:
1087:
1084:
1081:
1074:
1070:
1065:
1060:
1053:
1049:
1045:
1038:
1031:
1028:
1021:
1014:
1011:
1004:
1003:= length of
997:
990:
986:
979:
972:
968:
965:
958:
954:
949:
944:
937:
933:
928:
923:
916:
909:
905:
898:
891:
888:
885:
882:
878:
874:
870:
863:
858:
853:
849:
845:
842:
839:
835:
831:
827:
823:
819:
815:
812:
808:
804:
795:
788:
784:
777:
773:
769:
767:
762:
758:
756:
751:
747:
743:
741:
732:
729:
725:
721:
717:
714:
711:
707:
703:
699:
695:
688:
684:
676:
672:
668:
665:
661:
657:
639:
577:
479:
385:
382:Dynamic case
298:
227:
128:
80:
61:
24:
18:
2042:15 February
2030:Yap, Chee.
1641:FullRehash(
1284:FullRehash(
856:(Position h
852:);
679:(position h
671: := h(
483:load factor
294:probability
47:Static case
2058:Categories
1942:References
1864:;
1847:;
1711:;
1700:, 4};
1627:with size
1384:position h
1158:cells for
926:position h
772:exists at
761:exists at
724:is not in
52:FKS Scheme
33:hash table
29:collisions
1529:≤
1502:≤
1496:≤
1489:∑
1396:contains
1372:+ 1;
1151:Allocate
869:contains
822:+ 1;
694:contains
515:amortized
359:⋅
160:−
126:buckets.
108:−
1991:Archived
1930:See also
1892:on list
1814:) + 4 *
1696:) * max{
1653:in list
1639:function
1416:end else
1355:function
1299:end else
1296:end else
1293:end else
1290:end else
1246:on list
1183:to list
1172:in list
1147:) + 4 *
1085:end else
1052:on list
989:to list
978:in list
805:function
730:end else
658:function
2064:Hashing
1922:end for
1883:end for
1802:≤ 32 *
1793:end for
1692:= (1 +
1380:);
1357:Delete(
1339:. Here
1276:end for
1135:≤ 32 *
1082:end for
838:);
807:Insert(
660:Locate(
42:Details
1920:;
1899:store
1881:;
1849:repeat
1777:= 2 *
1763:= 2 *
1734:for h(
1702:repeat
1688:;
1679:end if
1677:;
1665:is in
1657:;
1609:until
1431:end if
1425:>=
1412:return
1406:end if
1307:Delete
1279:end if
1253:store
1206:repeat
1113:= 2 *
1088:end if
1059:store
1012:repeat
966:end if
915:<=
886:end if
883:end if
840:end if
738:Insert
728:)
718:return
712:end if
710:)
706:is in
700:return
675:)
653:Locate
1913:) of
1866:until
1825:<
1796:until
1719:<
1698:count
1682:count
1631:is O(
1459:into
1423:count
1400:mark
1370:count
1366:count
1341:phase
1337:phase
1325:count
1321:count
1267:) of
1223:until
1073:) of
1029:until
957:) of
936:) of
830:>
828:count
820:count
816:count
752:count
31:in a
2044:2015
1888:all
1821:all
1738:) =
1715:all
1708:s(M)
1409:else
1376:= h(
1282:else
1242:all
1091:else
1048:all
969:else
889:else
848:= h(
843:else
715:else
347:<
73:O(1)
2002:doi
1925:end
1886:for
1819:for
1784:* (
1713:for
1673:to
1635:).
1471:is
1434:end
1302:end
1240:for
1120:* (
1046:for
768:If
757:If
746:at
733:end
477:).
19:In
2060::
2034:.
1967:^
1950:^
1861:sj
1806:/
1659:if
1647:is
1645:)
1606:sj
1535:32
1419:if
1394:Tj
1382:if
1368:=
1363:is
1361:)
1351:.
1218:sj
1139:/
1129:if
1024:sj
924:if
906:if
897:=
875:if
854:if
824:if
818:=
813:is
811:)
801:.
677:if
666:is
664:)
575:.
296:.
78:.
23:,
2046:.
2004::
1917:j
1915:T
1911:x
1909:(
1906:j
1901:x
1896:j
1894:L
1890:x
1878:j
1876:L
1871:j
1869:h
1859:H
1854:j
1852:h
1844:j
1842:T
1837:j
1835:s
1831:M
1829:(
1827:s
1823:j
1816:M
1812:M
1810:(
1808:s
1804:M
1800:j
1788:j
1786:m
1781:j
1779:m
1774:j
1772:s
1767:j
1765:b
1760:j
1758:m
1753:j
1751:L
1746:j
1744:b
1740:j
1736:x
1731:j
1729:L
1725:M
1723:(
1721:s
1717:j
1706:H
1694:c
1690:M
1686:L
1675:L
1671:x
1667:U
1663:x
1661:(
1655:L
1651:T
1643:x
1633:n
1629:n
1625:S
1620:j
1618:T
1613:j
1611:h
1604:H
1599:j
1597:h
1592:j
1590:T
1574:.
1571:M
1568:4
1565:+
1559:)
1556:M
1553:(
1550:s
1543:2
1539:M
1524:j
1520:s
1514:)
1511:M
1508:(
1505:s
1499:j
1493:0
1475:j
1473:s
1469:j
1465:M
1463:(
1461:s
1457:S
1453:S
1449:M
1445:S
1427:M
1421:(
1402:x
1398:x
1390:x
1388:(
1386:j
1378:x
1374:j
1359:x
1349:U
1345:x
1333:M
1329:M
1317:x
1313:x
1286:x
1271:j
1269:T
1265:y
1263:(
1260:j
1255:y
1250:j
1248:L
1244:y
1235:j
1233:L
1228:j
1226:h
1216:H
1211:j
1209:h
1201:j
1199:L
1194:j
1192:b
1187:j
1185:L
1181:x
1176:j
1174:L
1169:j
1167:T
1162:j
1160:T
1155:j
1153:s
1149:M
1145:M
1143:(
1141:s
1137:M
1133:j
1124:j
1122:m
1117:j
1115:m
1110:j
1108:s
1103:j
1101:m
1096:j
1094:m
1077:j
1075:T
1071:y
1069:(
1066:j
1061:y
1056:j
1054:L
1050:y
1041:j
1039:L
1034:j
1032:h
1022:H
1017:j
1015:h
1007:j
1005:L
1000:j
998:b
993:j
991:L
987:x
982:j
980:L
975:j
973:T
961:j
959:T
955:x
953:(
950:j
945:x
940:j
938:T
934:x
932:(
929:j
919:j
917:m
912:j
910:b
908:(
901:j
899:b
894:j
892:b
879:x
877:(
871:x
866:j
864:T
859:j
850:x
846:j
836:x
832:M
826:(
809:x
798:j
796:h
791:j
789:T
785:j
780:j
778:T
774:j
770:x
763:j
759:x
748:j
744:x
726:S
722:x
720:(
708:S
704:x
702:(
696:x
691:j
689:T
685:x
683:(
681:j
673:x
669:j
662:x
625:)
622:1
619:(
616:O
595:)
592:n
589:(
586:O
563:)
560:1
557:(
554:O
534:)
531:1
528:(
525:O
501:k
497:/
493:1
461:)
458:1
455:(
452:O
432:)
429:n
426:(
423:O
403:)
400:1
397:(
394:O
362:x
356:4
353:+
350:s
344:T
324:)
321:n
318:(
315:O
305:T
301:x
280:)
277:n
274:(
271:O
257:k
241:2
237:k
223:k
195:2
191:k
180:k
166:)
163:1
157:x
154:(
151:2
148:=
145:s
135:s
131:x
114:)
111:1
105:x
102:(
99:2
96:=
93:s
83:x
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.