654:) time complexity. In addition, and like all binary search trees, self-balancing binary search trees keep their elements in order. Thus, traversing its elements follows a least-to-greatest pattern, whereas traversing a hash table can result in elements being in seemingly random order. Because they are in order, tree-based maps can also satisfy range queries (find all values between two bounds) whereas a hashmap can only find exact values. However, hash tables have a much better average-case time complexity than self-balancing binary search trees of O(1), and their worst-case performance is highly unlikely when a good
698:, though the relative performance of these implementations varies. For instance, Judy trees have been found to perform less efficiently than hash tables, while carefully selected hash tables generally perform more efficiently than adaptive radix trees, with potentially greater restrictions on the data types they can handle. The advantages of these alternative structures come from their ability to handle additional associative array operations, such as finding the mapping whose key is the closest to a queried key when the query is absent in the set of mappings.
544:
1178:, which produces a text or binary representation of the original objects that can be written directly to a file. This is most commonly implemented in the underlying object model, like .Net or Cocoa, which includes standard functions that convert the internal data into text. The program can create a complete text representation of any group of objects by calling these methods, which are almost always already implemented in the base associative array class.
1217:
382:
Suppose that the set of loans made by a library is represented in a data structure. Each book in a library may be checked out by one patron at a time. However, a single patron may be able to check out multiple books. Therefore, the information about which books are checked out to which patrons may be
606:
ratio than separate chaining when the table is mostly empty. However, as the table becomes filled with more elements, open addressing's performance degrades exponentially. Additionally, separate chaining uses less memory in most cases, unless the entries are very small (less than four times the size
575:
that separates each key into a separate "bucket" of the array. The basic idea behind a hash table is that accessing an element of an array via its index is a simple, constant-time operation. Therefore, the average overhead of an operation for a hash table is only the computation of the key's hash,
937:
Associative arrays can be implemented in any programming language as a package and many language systems provide them as part of their standard library. In some languages, they are not only built into the standard system, but have special syntax, often using array-like subscripting.
1204:
and more closely matching the internal structure of the programs using them led to a renaissance in the key–value store market. These systems can store and retrieve associative arrays in a native fashion, which can greatly improve performance in common web-related workflows.
517:
that indicates the lack of a mapping. This technique is simple and fast, with each dictionary operation taking constant time. However, the space requirement for this structure is the size of the entire keyspace, making it impractical unless the keyspace is small.
599:, that stores all the values matching the hash. By contrast, in open addressing, if a hash collision is found, the table seeks an empty spot in an array to store the value in a deterministic manner, usually by looking at the next immediate position in the array.
1185:(DB) is required. Some DB systems natively store associative arrays by serializing the data and then storing that serialized data and the key. Individual arrays can then be loaded or saved from the database using the key to refer to them. These
315:
is a related abstract data type in which the mappings operate in both directions: each value must be associated with a unique key, and a second lookup operation takes a value as an argument and looks up the key associated with that value.
437:
A lookup operation on the key "Great
Expectations" would return "John". If John returns his book, that would cause a deletion operation, and if Pat checks out a book, that would cause an insertion operation, leading to a different state:
666:). However, this introduces extra complexity into the implementation and may cause even worse performance for smaller hash tables, where the time spent inserting into and balancing the tree is greater than the time needed to perform a
497:
of mappings. With this implementation, the time to perform the basic dictionary operations is linear in the total number of mappings. However, it is easy to implement and the constant factors in its running time are small.
1193:(RDBs), but a lack of standardization, among other reasons, limited their use to certain niche roles. RDBs were used for these roles in most cases, although saving objects to a RDB can be complicated, a problem known as
641:
Compared to hash tables, these structures have both strengths and weaknesses. The worst-case performance of self-balancing binary search trees is significantly better than that of a hash table, with a time complexity in
1138:), all objects behave as associative arrays with string-valued keys, while the Map and WeakMap types take arbitrary objects as keys. In Lua, they are used as the primitive building block for all data structures. In
887:
The basic definition of a dictionary does not mandate an order. To guarantee a fixed order of enumeration, ordered versions of the associative array are often used. There are two senses of an ordered dictionary:
1456:
661:
A self-balancing binary search tree can be used to implement the buckets for a hash table that uses separate chaining. This allows for average-case constant lookup, but assures a worst-case performance of O(log
1576:. Quote: "The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of
292:
find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation. If no value is found, some lookup functions raise an
1807:
576:
combined with accessing the corresponding bucket within the array. As such, hash tables usually perform in O(1) time, and usually outperform alternative implementations.
284:
228:
1453:
892:
The order of enumeration is always deterministic for a given set of keys by sorting. This is the case for tree-based implementations, one representative being the
501:
Another very simple implementation technique, usable when the keys are restricted to a narrow range, is direct addressing into an array: the value for a given key
932:
230:
pair to the collection, mapping the key to its new value. Any existing mapping is overwritten. The arguments to this operation are the key and the value.
1706:
1005:, support associative arrays as a primary container type. In many more languages, they are available as library functions without special syntax.
583:: the mapping by the hash function of two different keys to the same bucket of the array. The two most widespread approaches to this problem are
1554:
1376:
899:
The order of enumeration is key-independent and is instead based on the order of insertion. This is the case for the "ordered dictionary" in
2174:
1550:
923:
on top of a normal dictionary, or by moving the actual data out of the sparse (unordered) array and into a dense insertion-ordered one.
2341:
1850:
304:
to loop over all the mappings. For such operations, the order in which the mappings are returned is usually implementation-defined.
1647:
Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (April 2015). "A comparison of adaptive radix trees and hash tables".
650:). This is in contrast to hash tables, whose worst-case performance involves all elements sharing a single bucket, resulting in O(
2712:
2346:
2336:
2331:
2144:
1664:
1305:
1272:
1770:
1724:
2319:
2220:
1194:
383:
represented by an associative array, in which the books are the keys and the patrons are the values. Using notation from
40:"Associative table" redirects here. For the relation used in database systems to resolve many-to-many relationship, see
1363:
79:, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a
2497:
2083:
1610:
1434:
767:
627:
170:
is often known as a "mapping"; the same word may also be used to refer to the process of creating a new association.
1134:, all arrays can be associative, except that the keys are limited to integers and strings. In JavaScript (see also
300:
Associative arrays may also include other operations such as determining the number of mappings or constructing an
1106:
2470:
1873:
72:
154:
known in mathematics. Rather, it arises from the association of values with keys. It is not to be confused with
2587:
2392:
2324:
2286:
1878:
1738:
1089:
1065:
957:
supported them as one possible implementation of sets and maps. Most modern scripting languages, starting with
592:
155:
27:
2773:
1843:
1037:
1033:
1021:
986:
908:
551:
misses required to look up elements in large hash tables (far exceeding size of the cache) with chaining and
384:
1952:
1452:
Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
2763:
2487:
2417:
2265:
1181:
For programs that use very large data sets, this sort of individual file storage is not appropriate, and a
1081:
1029:
1573:
296:, while others return a default value (such as zero, null, or a specific value passed to the constructor).
286:
pair from the collection, unmapping a given key from its value. The argument to this operation is the key.
2768:
2742:
2377:
1957:
1940:
1222:
1069:
1049:
990:
904:
34:
1164:
Many programs using associative arrays will need to store that data in a more permanent form, such as a
2365:
2156:
1923:
1918:
1417:
1182:
1002:
129:
2675:
2627:
2539:
2517:
2512:
2440:
2306:
2260:
1913:
1073:
998:
1367:
2549:
2213:
1947:
1906:
1836:
1627:
1147:
845:
311:
generalizes an associative array by allowing multiple values to be associated with a single key. A
167:
76:
2702:
2617:
2187:
2164:
239:
183:
136:
489:
For dictionaries with very few mappings, it may make sense to implement the dictionary using an
2445:
2301:
2255:
2169:
1969:
1235:
1186:
80:
2435:
2410:
2095:
2050:
2012:
1101:
556:
2237:
2035:
1404:
568:
151:
110:
87:
953:
made multi-dimensional associative arrays, optionally persistent, its key data structure.
563:
The most frequently used general-purpose implementation of an associative array is with a
8:
2778:
2707:
2685:
2612:
2465:
2457:
2206:
1536:
1330:
1190:
1159:
121:
101:
that implement associative arrays. The two major solutions to the dictionary problem are
1756:
344:
remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))
2690:
2670:
2622:
2597:
2382:
2351:
2078:
2063:
1928:
1888:
1670:
1292:. Lecture Notes in Computer Science. Vol. 401. Springer Verlag. pp. 106–114.
1115:
920:
806:
695:
679:
635:
293:
114:
68:
41:
2577:
2507:
2296:
2291:
1997:
1660:
1606:
1430:
1301:
1268:
584:
312:
144:
1823:
1674:
1499:
1189:
have been used for many years and have a history as long as that of the more common
543:
2722:
2607:
2405:
2020:
1652:
1467:
1400:
1334:
1293:
1260:
1123:
994:
982:
916:
850:
596:
490:
125:
48:
1688:
2727:
2592:
2544:
2477:
2040:
1982:
1460:
1201:
915:
The latter is more common. Such ordered dictionaries can be implemented using an
588:
20:
2680:
2502:
2492:
2400:
2132:
2110:
1935:
1859:
1464:
1412:
1200:
After approximately 2010, the need for high-performance databases suitable for
1017:
946:
900:
643:
591:. In separate chaining, the array does not store the value itself but stores a
580:
552:
514:
98:
1656:
1471:
109:. It is sometimes also possible to solve the problem using directly addressed
2757:
2602:
2105:
2002:
1987:
1359:
1297:
1264:
1174:
1165:
1139:
667:
655:
572:
941:
Built-in syntactic support for associative arrays was introduced in 1969 by
33:"Map (computer science)" redirects here. For the higher-order function, see
2559:
2534:
1594:
324:
The operations of the associative array should satisfy various properties:
26:"Associative container" redirects here. For their C++ implementation, see
2737:
2732:
2582:
2529:
2356:
2100:
2025:
1426:
1111:
1097:
1013:
616:
526:
494:
140:
106:
1771:"System.Generics.Collections.TDictionary - RAD Studio API Documentation"
2642:
2637:
2554:
2522:
2427:
2370:
2088:
1992:
1408:
978:
737:
691:
683:
682:
or in data structures specialized to a particular type of keys such as
603:
564:
538:
522:
102:
1824:
NIST's
Dictionary of Algorithms and Data Structures: Associative Array
1259:. Lecture Notes in Computer Science. Vol. 971. pp. 122–137.
1168:. A common solution to this problem is a generalized concept known as
559:, though as the table gets full, its performance degrades drastically.
173:
The operations that are usually defined for an associative array are:
19:"Dictionary (data structure)" redirects here. Not to be confused with
2717:
2695:
2652:
2647:
2314:
2270:
2229:
2030:
1977:
1422:
1025:
1009:
548:
135:
Associative arrays have many applications including such fundamental
1288:
Andersson, Arne (1989). "Optimal Bounds on the
Dictionary Problem".
1216:
626:
Another common approach is to implement an associative array with a
2632:
2127:
2073:
1901:
631:
308:
301:
132:
is a form of direct hardware-level support for associative arrays.
1828:
1739:"collections — Container datatypes — Python 3.9.0a3 documentation"
2122:
2068:
1794:
1255:
Collins, Graham; Syme, Donald (1995). "A theory of finite maps".
1077:
1537:"When should I use a hash table instead of an association list?"
2117:
2058:
942:
329:
lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)
2198:
1230:
1085:
1061:
1053:
950:
521:
The two major approaches for implementing dictionaries are a
670:
on all elements of a linked list or similar data structure.
90:. It supports 'lookup', 'remove', and 'insert' operations.
2250:
2139:
1649:
1135:
1045:
966:
962:
954:
687:
388:
1707:"OrderedDictionary Class (System.Collections.Specialized)"
1646:
1399:
2245:
1131:
974:
970:
958:
120:
Many programming languages include associative arrays as
1257:
Higher Order Logic
Theorem Proving and Its Applications
933:
Comparison of programming languages (associative array)
621:
242:
186:
1212:
949:
offered tables with string keys and integer values.
678:
Associative arrays may also be stored in unbalanced
1122:(since both typically use this implementation); in
1605:(2nd ed.). Addison-Wesley. pp. 513–558.
278:
222:
1454:"Dynamic Perfect Hashing: Upper and Lower Bounds"
1369:Algorithms and Data Structures: The Basic Toolbox
166:In an associative array, the association between
2755:
1795:"Associative Arrays, the D programming language"
1651:. Seoul, South Korea: IEEE. pp. 1227–1238.
1549:
1523:
1498:Black, Paul E.; Stewart, Rob (2 November 2020).
1482:
1448:
1446:
1366:(2008), "4 Hash Tables and Associative Arrays",
1329:
1808:"Archives and Serializations Programming Guide"
1358:
555:. Linear probing performs better due to better
16:Data structure that associates keys with values
1463:. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
97:is the classic problem of designing efficient
2214:
1844:
1443:
532:
1557:(2006), "Pathfinders for associative maps",
1504:Dictionary of Algorithms and Data Structures
1497:
1465:http://portal.acm.org/citation.cfm?id=182370
1254:
2221:
2207:
1851:
1837:
1337:(2006), "9.1 The Map Abstract Data Type",
547:This graph compares the average number of
1287:
1476:
1339:Data Structures & Algorithms in Java
542:
374:creates a new, empty associative array.
117:, or other more specialized structures.
1493:
1491:
1341:(4th ed.), Wiley, pp. 368–371
610:
2756:
1757:"Dictionary<TKey, TValue> Class"
1625:
1395:
1393:
1391:
1389:
2202:
1832:
1593:
1587:
1290:Proc. Symposium on Optimal Algorithms
882:
124:, while many other languages provide
1543:
1488:
1354:
1352:
1350:
1348:
1325:
1323:
1321:
1319:
1317:
1195:object-relational impedance mismatch
1153:
1858:
1386:
926:
579:Hash tables must be able to handle
13:
1150:also supports associative arrays.
622:Self-balancing binary search trees
458:"The Brothers Karamazov"
14:
2790:
1817:
1578:self-balancing binary search tree
1345:
1314:
768:Self-balancing binary search tree
628:self-balancing binary search tree
595:to another container, usually an
484:
128:that support associative arrays.
1215:
509:, or if there is no mapping for
340:is an exception or default value
150:The name does not come from the
1801:
1787:
1763:
1749:
1731:
1717:
1699:
1681:
1640:
1619:
1599:The Art of Computer Programming
1566:
1529:
1382:from the original on 2014-08-02
893:
513:then the cell stores a special
446:"Pride and Prejudice"
399:"Pride and Prejudice"
391:, the data structure would be:
2228:
1524:Goodrich & Tamassia (2006)
1517:
1483:Goodrich & Tamassia (2006)
1281:
1248:
673:
423:"Great Expectations"
273:
243:
217:
187:
1:
2287:Arbitrary-precision or bignum
1572:Joel Adams and Larry Nyhoff.
1539:. lisp-faq/part2. 1996-02-20.
1241:
701:
470:"Wuthering Heights"
411:"Wuthering Heights"
370:is an associative array, and
319:
161:
1375:, Springer, pp. 81–98,
602:Open addressing has a lower
505:is stored at the array cell
28:associative containers (C++)
7:
2175:Directed acyclic word graph
1941:Double-ended priority queue
1626:Probst, Mark (2010-04-30).
1223:Computer programming portal
1208:
279:{\displaystyle (key,value)}
223:{\displaystyle (key,value)}
35:Map (higher-order function)
10:
2795:
1418:Introduction to Algorithms
1415:(2001), "11 Hash Tables",
1183:database management system
1157:
945:, under the name "table".
930:
709:Underlying data structure
614:
536:
533:Hash table implementations
377:
130:Content-addressable memory
39:
32:
25:
18:
2661:
2628:Strongly typed identifier
2570:
2456:
2426:
2391:
2279:
2236:
2183:
2155:
2049:
2011:
1968:
1887:
1866:
1657:10.1109/ICDE.2015.7113370
1628:"Linear vs Binary Search"
1559:Ext. Abstracts GIS-l 2006
1472:10.1137/S0097539791194094
1126:and Lua, they are called
717:
714:
711:
708:
1907:Retrieval Data Structure
1298:10.1007/3-540-51859-2_10
1265:10.1007/3-540-60275-5_61
844:Sequential container of
440:
393:
349:remove(k, new()) = new()
2703:Parametric polymorphism
2188:List of data structures
2165:Binary decision diagram
1775:docwiki.embarcadero.com
1561:, GIS-I, pp. 71–74
903:, the LinkedHashMap of
334:lookup(k, new()) = fail
2170:Directed acyclic graph
1236:Function (mathematics)
560:
280:
224:
156:associative processors
1603:Sorting and Searching
1405:Leiserson, Charles E.
557:locality of reference
546:
281:
225:
2774:Composite data types
2036:Unrolled linked list
1429:, pp. 221–252,
1331:Goodrich, Michael T.
611:Tree implementations
289:Lookup, find, or get
240:
184:
152:associative property
137:programming patterns
122:primitive data types
2764:Abstract data types
2708:Primitive data type
2613:Recursive data type
2466:Algebraic data type
2342:Quadruple precision
2084:Self-balancing tree
1693:en.cppreference.com
1191:relational database
1102:unordered_map (C++)
696:van Emde Boas trees
680:binary search trees
115:binary search trees
2769:Associative arrays
2671:Abstract data type
2352:Extended precision
2311:Reduced precision
2064:Binary search tree
1929:Double-ended queue
1810:, Apple Inc., 2012
1459:2016-03-04 at the
1142:, they are called
1118:, they are called
1116:Windows PowerShell
921:doubly linked list
919:, by overlaying a
883:Ordered dictionary
807:binary search tree
712:Lookup or Removal
561:
276:
220:
126:software libraries
95:dictionary problem
77:(key, value) pairs
69:abstract data type
42:Associative entity
2751:
2750:
2483:Associative array
2347:Octuple precision
2196:
2195:
1998:Hashed array tree
1897:Associative array
1666:978-1-4799-7964-6
1409:Rivest, Ronald L.
1401:Cormen, Thomas H.
1335:Tamassia, Roberto
1307:978-3-540-51859-4
1274:978-3-540-60275-0
1154:Permanent storage
896:container of C++.
880:
879:
585:separate chaining
476:"Alice"
452:"Alice"
417:"Alice"
405:"Alice"
313:bidirectional map
168:a key and a value
145:decorator pattern
53:associative array
2786:
2723:Type constructor
2608:Opaque data type
2540:Record or Struct
2337:Double precision
2332:Single precision
2223:
2216:
2209:
2200:
2199:
2021:Association list
1853:
1846:
1839:
1830:
1829:
1811:
1805:
1799:
1798:
1791:
1785:
1784:
1782:
1781:
1767:
1761:
1760:
1753:
1747:
1746:
1735:
1729:
1728:
1721:
1715:
1714:
1703:
1697:
1696:
1685:
1679:
1678:
1644:
1638:
1637:
1635:
1634:
1623:
1617:
1616:
1591:
1585:
1570:
1564:
1562:
1547:
1541:
1540:
1533:
1527:
1521:
1515:
1514:
1512:
1510:
1495:
1486:
1480:
1474:
1450:
1441:
1439:
1421:(2nd ed.),
1397:
1384:
1383:
1381:
1374:
1356:
1343:
1342:
1327:
1312:
1311:
1285:
1279:
1278:
1252:
1225:
1220:
1219:
1187:key–value stores
1109:
1092:they are called
1056:they are called
1040:they are called
995:Wolfram Language
927:Language support
917:association list
895:
851:association list
706:
705:
597:association list
571:combined with a
491:association list
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
433:
430:
429:"John"
427:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
373:
369:
365:
361:
357:
350:
345:
339:
335:
330:
285:
283:
282:
277:
233:Remove or delete
229:
227:
226:
221:
49:computer science
2794:
2793:
2789:
2788:
2787:
2785:
2784:
2783:
2754:
2753:
2752:
2747:
2728:Type conversion
2663:
2657:
2593:Enumerated type
2566:
2452:
2446:null-terminated
2422:
2387:
2275:
2232:
2227:
2197:
2192:
2179:
2151:
2045:
2041:XOR linked list
2007:
1983:Circular buffer
1964:
1883:
1862:
1860:Data structures
1857:
1820:
1815:
1814:
1806:
1802:
1797:. Digital Mars.
1793:
1792:
1788:
1779:
1777:
1769:
1768:
1764:
1755:
1754:
1750:
1743:docs.python.org
1737:
1736:
1732:
1725:"LinkedHashMap"
1723:
1722:
1718:
1705:
1704:
1700:
1687:
1686:
1682:
1667:
1645:
1641:
1632:
1630:
1624:
1620:
1613:
1601:. Vol. 3:
1592:
1588:
1571:
1567:
1548:
1544:
1535:
1534:
1530:
1522:
1518:
1508:
1506:
1496:
1489:
1481:
1477:
1461:Wayback Machine
1451:
1444:
1437:
1413:Stein, Clifford
1398:
1387:
1379:
1372:
1357:
1346:
1328:
1315:
1308:
1286:
1282:
1275:
1253:
1249:
1244:
1221:
1214:
1211:
1202:cloud computing
1162:
1160:Key–value store
1156:
1105:
935:
929:
885:
848:
846:key–value pairs
704:
676:
624:
619:
613:
607:of a pointer).
589:open addressing
541:
535:
487:
482:
481:
478:
475:
472:
469:
466:
464:"Pat"
463:
460:
457:
454:
451:
448:
445:
442:
435:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
380:
371:
367:
363:
359:
355:
348:
343:
337:
333:
328:
322:
241:
238:
237:
185:
182:
181:
164:
99:data structures
45:
38:
31:
24:
21:data dictionary
17:
12:
11:
5:
2792:
2782:
2781:
2776:
2771:
2766:
2749:
2748:
2746:
2745:
2740:
2735:
2730:
2725:
2720:
2715:
2710:
2705:
2700:
2699:
2698:
2688:
2683:
2681:Data structure
2678:
2673:
2667:
2665:
2659:
2658:
2656:
2655:
2650:
2645:
2640:
2635:
2630:
2625:
2620:
2615:
2610:
2605:
2600:
2595:
2590:
2585:
2580:
2574:
2572:
2568:
2567:
2565:
2564:
2563:
2562:
2552:
2547:
2542:
2537:
2532:
2527:
2526:
2525:
2515:
2510:
2505:
2500:
2495:
2490:
2485:
2480:
2475:
2474:
2473:
2462:
2460:
2454:
2453:
2451:
2450:
2449:
2448:
2438:
2432:
2430:
2424:
2423:
2421:
2420:
2415:
2414:
2413:
2408:
2397:
2395:
2389:
2388:
2386:
2385:
2380:
2375:
2374:
2373:
2363:
2362:
2361:
2360:
2359:
2349:
2344:
2339:
2334:
2329:
2328:
2327:
2322:
2320:Half precision
2317:
2307:Floating point
2304:
2299:
2294:
2289:
2283:
2281:
2277:
2276:
2274:
2273:
2268:
2263:
2258:
2253:
2248:
2242:
2240:
2234:
2233:
2226:
2225:
2218:
2211:
2203:
2194:
2193:
2191:
2190:
2184:
2181:
2180:
2178:
2177:
2172:
2167:
2161:
2159:
2153:
2152:
2150:
2149:
2148:
2147:
2137:
2136:
2135:
2133:Hilbert R-tree
2130:
2125:
2115:
2114:
2113:
2111:Fibonacci heap
2108:
2103:
2093:
2092:
2091:
2086:
2081:
2079:Red–black tree
2076:
2071:
2061:
2055:
2053:
2047:
2046:
2044:
2043:
2038:
2033:
2028:
2023:
2017:
2015:
2009:
2008:
2006:
2005:
2000:
1995:
1990:
1985:
1980:
1974:
1972:
1966:
1965:
1963:
1962:
1961:
1960:
1955:
1945:
1944:
1943:
1936:Priority queue
1933:
1932:
1931:
1921:
1916:
1911:
1910:
1909:
1904:
1893:
1891:
1885:
1884:
1882:
1881:
1876:
1870:
1868:
1864:
1863:
1856:
1855:
1848:
1841:
1833:
1827:
1826:
1819:
1818:External links
1816:
1813:
1812:
1800:
1786:
1762:
1748:
1730:
1716:
1698:
1680:
1665:
1639:
1618:
1611:
1586:
1582:red–black tree
1574:"Trees in STL"
1565:
1542:
1528:
1526:, pp. 389–397.
1516:
1487:
1485:, pp. 597–599.
1475:
1442:
1435:
1385:
1364:Sanders, Peter
1360:Mehlhorn, Kurt
1344:
1313:
1306:
1280:
1273:
1246:
1245:
1243:
1240:
1239:
1238:
1233:
1227:
1226:
1210:
1207:
1158:Main article:
1155:
1152:
961:and including
931:Main article:
928:
925:
913:
912:
901:.NET Framework
897:
884:
881:
878:
877:
874:
871:
868:
861:
854:
841:
840:
837:
830:
823:
816:
809:
802:
801:
798:
791:
784:
777:
770:
764:
763:
760:
753:
750:
743:
740:
734:
733:
730:
727:
724:
720:
719:
716:
713:
710:
703:
700:
675:
672:
644:big O notation
636:red–black tree
623:
620:
615:Main article:
612:
609:
553:linear probing
537:Main article:
534:
531:
515:sentinel value
486:
485:Implementation
483:
441:
394:
379:
376:
352:
351:
346:
341:
331:
321:
318:
298:
297:
290:
287:
275:
272:
269:
266:
263:
260:
257:
254:
251:
248:
245:
234:
231:
219:
216:
213:
210:
207:
204:
201:
198:
195:
192:
189:
178:
163:
160:
71:that stores a
15:
9:
6:
4:
3:
2:
2791:
2780:
2777:
2775:
2772:
2770:
2767:
2765:
2762:
2761:
2759:
2744:
2741:
2739:
2736:
2734:
2731:
2729:
2726:
2724:
2721:
2719:
2716:
2714:
2711:
2709:
2706:
2704:
2701:
2697:
2694:
2693:
2692:
2689:
2687:
2684:
2682:
2679:
2677:
2674:
2672:
2669:
2668:
2666:
2660:
2654:
2651:
2649:
2646:
2644:
2641:
2639:
2636:
2634:
2631:
2629:
2626:
2624:
2621:
2619:
2616:
2614:
2611:
2609:
2606:
2604:
2603:Function type
2601:
2599:
2596:
2594:
2591:
2589:
2586:
2584:
2581:
2579:
2576:
2575:
2573:
2569:
2561:
2558:
2557:
2556:
2553:
2551:
2548:
2546:
2543:
2541:
2538:
2536:
2533:
2531:
2528:
2524:
2521:
2520:
2519:
2516:
2514:
2511:
2509:
2506:
2504:
2501:
2499:
2496:
2494:
2491:
2489:
2486:
2484:
2481:
2479:
2476:
2472:
2469:
2468:
2467:
2464:
2463:
2461:
2459:
2455:
2447:
2444:
2443:
2442:
2439:
2437:
2434:
2433:
2431:
2429:
2425:
2419:
2416:
2412:
2409:
2407:
2404:
2403:
2402:
2399:
2398:
2396:
2394:
2390:
2384:
2381:
2379:
2376:
2372:
2369:
2368:
2367:
2364:
2358:
2355:
2354:
2353:
2350:
2348:
2345:
2343:
2340:
2338:
2335:
2333:
2330:
2326:
2323:
2321:
2318:
2316:
2313:
2312:
2310:
2309:
2308:
2305:
2303:
2300:
2298:
2295:
2293:
2290:
2288:
2285:
2284:
2282:
2278:
2272:
2269:
2267:
2264:
2262:
2259:
2257:
2254:
2252:
2249:
2247:
2244:
2243:
2241:
2239:
2238:Uninterpreted
2235:
2231:
2224:
2219:
2217:
2212:
2210:
2205:
2204:
2201:
2189:
2186:
2185:
2182:
2176:
2173:
2171:
2168:
2166:
2163:
2162:
2160:
2158:
2154:
2146:
2143:
2142:
2141:
2138:
2134:
2131:
2129:
2126:
2124:
2121:
2120:
2119:
2116:
2112:
2109:
2107:
2106:Binomial heap
2104:
2102:
2099:
2098:
2097:
2094:
2090:
2087:
2085:
2082:
2080:
2077:
2075:
2072:
2070:
2067:
2066:
2065:
2062:
2060:
2057:
2056:
2054:
2052:
2048:
2042:
2039:
2037:
2034:
2032:
2029:
2027:
2024:
2022:
2019:
2018:
2016:
2014:
2010:
2004:
2003:Sparse matrix
2001:
1999:
1996:
1994:
1991:
1989:
1988:Dynamic array
1986:
1984:
1981:
1979:
1976:
1975:
1973:
1971:
1967:
1959:
1956:
1954:
1951:
1950:
1949:
1946:
1942:
1939:
1938:
1937:
1934:
1930:
1927:
1926:
1925:
1922:
1920:
1917:
1915:
1912:
1908:
1905:
1903:
1900:
1899:
1898:
1895:
1894:
1892:
1890:
1886:
1880:
1877:
1875:
1872:
1871:
1869:
1865:
1861:
1854:
1849:
1847:
1842:
1840:
1835:
1834:
1831:
1825:
1822:
1821:
1809:
1804:
1796:
1790:
1776:
1772:
1766:
1758:
1752:
1744:
1740:
1734:
1726:
1720:
1712:
1708:
1702:
1694:
1690:
1684:
1676:
1672:
1668:
1662:
1658:
1654:
1650:
1643:
1629:
1622:
1614:
1612:0-201-89685-0
1608:
1604:
1600:
1596:
1595:Knuth, Donald
1590:
1583:
1579:
1575:
1569:
1560:
1556:
1555:Mazzolini, L.
1552:
1546:
1538:
1532:
1525:
1520:
1505:
1501:
1494:
1492:
1484:
1479:
1473:
1469:
1466:
1462:
1458:
1455:
1449:
1447:
1438:
1436:0-262-03293-7
1432:
1428:
1424:
1420:
1419:
1414:
1410:
1406:
1402:
1396:
1394:
1392:
1390:
1378:
1371:
1370:
1365:
1361:
1355:
1353:
1351:
1349:
1340:
1336:
1332:
1326:
1324:
1322:
1320:
1318:
1309:
1303:
1299:
1295:
1291:
1284:
1276:
1270:
1266:
1262:
1258:
1251:
1247:
1237:
1234:
1232:
1229:
1228:
1224:
1218:
1213:
1206:
1203:
1198:
1196:
1192:
1188:
1184:
1179:
1177:
1176:
1175:serialization
1171:
1167:
1166:computer file
1161:
1151:
1149:
1145:
1141:
1140:Visual FoxPro
1137:
1133:
1129:
1125:
1121:
1117:
1113:
1108:
1103:
1099:
1095:
1091:
1087:
1083:
1079:
1075:
1071:
1067:
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1031:
1027:
1023:
1019:
1015:
1011:
1006:
1004:
1000:
996:
992:
988:
984:
980:
976:
972:
968:
964:
960:
956:
952:
948:
944:
939:
934:
924:
922:
918:
910:
906:
902:
898:
891:
890:
889:
875:
872:
869:
866:
862:
859:
855:
852:
847:
843:
842:
838:
835:
831:
828:
824:
821:
817:
814:
810:
808:
804:
803:
799:
796:
792:
789:
785:
782:
778:
775:
771:
769:
766:
765:
761:
758:
754:
751:
748:
744:
741:
739:
736:
735:
731:
728:
725:
722:
721:
707:
699:
697:
693:
689:
685:
681:
671:
669:
668:linear search
665:
659:
657:
656:hash function
653:
649:
645:
639:
637:
633:
630:, such as an
629:
618:
608:
605:
600:
598:
594:
590:
586:
582:
577:
574:
573:hash function
570:
566:
558:
554:
550:
545:
540:
530:
528:
524:
519:
516:
512:
508:
504:
499:
496:
493:, which is a
492:
439:
392:
390:
386:
375:
347:
342:
332:
327:
326:
325:
317:
314:
310:
305:
303:
295:
291:
288:
270:
267:
264:
261:
258:
255:
252:
249:
246:
235:
232:
214:
211:
208:
205:
202:
199:
196:
193:
190:
179:
177:Insert or put
176:
175:
174:
171:
169:
159:
157:
153:
148:
146:
142:
138:
133:
131:
127:
123:
118:
116:
112:
108:
104:
100:
96:
91:
89:
86:
82:
78:
74:
70:
66:
62:
58:
54:
50:
43:
36:
29:
22:
2508:Intersection
2482:
1958:Disjoint-set
1896:
1803:
1789:
1778:. Retrieved
1774:
1765:
1751:
1742:
1733:
1719:
1710:
1701:
1692:
1683:
1648:
1642:
1631:. Retrieved
1621:
1602:
1598:
1589:
1581:
1577:
1568:
1558:
1545:
1531:
1519:
1507:. Retrieved
1503:
1500:"dictionary"
1478:
1416:
1368:
1338:
1289:
1283:
1256:
1250:
1199:
1180:
1173:
1169:
1163:
1143:
1127:
1119:
1093:
1057:
1042:dictionaries
1041:
1007:
940:
936:
914:
886:
864:
857:
833:
826:
819:
812:
794:
787:
780:
773:
756:
746:
677:
663:
660:
651:
647:
640:
625:
601:
578:
562:
520:
510:
506:
502:
500:
488:
436:
381:
366:is a value,
353:
323:
306:
299:
172:
165:
149:
134:
119:
107:search trees
94:
92:
84:
64:
61:symbol table
60:
56:
52:
46:
2738:Type theory
2733:Type system
2583:Bottom type
2530:Option type
2471:generalized
2357:Long double
2302:Fixed point
2101:Binary heap
2026:Linked list
1551:Klammer, F.
1427:McGraw-Hill
1144:Collections
1120:hash tables
1112:Common Lisp
1014:Objective-C
894:<map>
805:unbalanced
732:worst case
726:worst case
692:Judy arrays
684:radix trees
674:Other trees
617:Search tree
527:search tree
495:linked list
141:memoization
103:hash tables
2779:Data types
2758:Categories
2643:Empty type
2638:Type class
2588:Collection
2545:Refinement
2523:metaobject
2371:signedness
2230:Data types
2089:Splay tree
1993:Hash table
1874:Collection
1780:2017-04-18
1689:"std::map"
1633:2016-11-20
1509:26 January
1242:References
1148:D language
979:JavaScript
738:Hash table
715:Insertion
702:Comparison
604:cache miss
581:collisions
565:hash table
539:Hash table
523:hash table
362:are keys,
320:Properties
180:add a new
162:Operations
73:collection
65:dictionary
2718:Subtyping
2713:Interface
2696:metaclass
2648:Unit type
2618:Semaphore
2598:Exception
2503:Inductive
2493:Dependent
2458:Composite
2436:Character
2418:Reference
2315:Minifloat
2271:Bit array
2145:Hash tree
2031:Skip list
1978:Bit array
1879:Container
1580:called a
1423:MIT Press
1170:archiving
1098:map (C++)
1026:REALbasic
1010:Smalltalk
658:is used.
646:of O(log
549:CPU cache
294:exception
236:remove a
2743:Variable
2633:Top type
2498:Equality
2406:physical
2383:Rational
2378:Interval
2325:bfloat16
2074:AVL tree
1953:Multiset
1902:Multimap
1889:Abstract
1675:17170456
1597:(1998).
1457:Archived
1377:archived
1209:See also
729:average
723:average
718:Ordered
632:AVL tree
336:, where
309:multimap
302:iterator
143:and the
81:function
2686:Generic
2662:Related
2578:Boolean
2535:Product
2411:virtual
2401:Address
2393:Pointer
2366:Integer
2297:Decimal
2292:Complex
2280:Numeric
2128:R+ tree
2123:R* tree
2069:AA tree
1759:. MSDN.
1711:MS Docs
1090:Haskell
1078:Clojure
943:SNOBOL4
593:pointer
378:Example
2676:Boxing
2664:topics
2623:Stream
2560:tagged
2518:Object
2441:String
2157:Graphs
2118:R-tree
2059:B-tree
2013:Linked
1970:Arrays
1673:
1663:
1609:
1433:
1304:
1271:
1146:. The
1128:tables
1110:); in
1104:, and
1058:hashes
1038:Delphi
1022:Python
1001:, and
987:Python
909:Python
849:(e.g.
825:O(log
811:O(log
793:O(log
786:O(log
779:O(log
772:O(log
385:Python
354:where
111:arrays
88:domain
85:finite
67:is an
2571:Other
2555:Union
2488:Class
2478:Array
2261:Tryte
2051:Trees
1924:Queue
1919:Stack
1867:Types
1671:S2CID
1380:(PDF)
1373:(PDF)
1231:Tuple
1130:. In
1124:Maple
1096:(see
1086:OCaml
1082:Scala
1060:; in
1054:Seed7
1044:; in
1030:Swift
983:Maple
951:MUMPS
873:O(1)
870:O(1)
752:O(1)
742:O(1)
694:, or
688:tries
634:or a
569:array
567:: an
525:or a
372:new()
83:with
63:, or
51:, an
2691:Kind
2653:Void
2513:List
2428:Text
2266:Word
2256:Trit
2251:Byte
2140:Trie
2096:Heap
1914:List
1661:ISBN
1607:ISBN
1511:2022
1431:ISBN
1425:and
1302:ISBN
1269:ISBN
1136:JSON
1114:and
1094:maps
1070:Java
1052:and
1050:Ruby
1046:Perl
1036:and
1018:.NET
991:Ruby
967:Perl
963:Rexx
955:SETL
907:and
905:Java
839:Yes
800:Yes
587:and
389:JSON
358:and
338:fail
105:and
93:The
2550:Set
2246:Bit
1948:Set
1653:doi
1468:doi
1294:doi
1261:doi
1172:or
1132:PHP
1107:Map
1062:C++
1034:VBA
1008:In
1003:Lua
975:Tcl
971:PHP
959:AWK
947:TMG
876:No
762:No
387:or
139:as
75:of
57:map
47:In
2760::
1773:.
1741:.
1709:.
1691:.
1669:.
1659:.
1584:."
1553:;
1502:.
1490:^
1445:^
1411:;
1407:;
1403:;
1388:^
1362:;
1347:^
1333:;
1316:^
1300:.
1267:.
1197:.
1100:,
1088:,
1084:,
1080:,
1076:,
1074:Go
1072:,
1068:,
1066:C#
1064:,
1048:,
1032:,
1028:,
1024:,
1020:,
1016:,
1012:,
999:Go
997:,
993:,
989:,
985:,
981:,
977:,
973:,
969:,
965:,
867:)
863:O(
860:)
856:O(
853:)
836:)
832:O(
829:)
822:)
818:O(
815:)
797:)
790:)
783:)
776:)
759:)
755:O(
749:)
745:O(
690:,
686:,
638:.
529:.
307:A
158:.
147:.
113:,
59:,
55:,
2222:e
2215:t
2208:v
1852:e
1845:t
1838:v
1783:.
1745:.
1727:.
1713:.
1695:.
1677:.
1655::
1636:.
1615:.
1563:.
1513:.
1470::
1440:.
1310:.
1296::
1277:.
1263::
911:.
865:n
858:n
834:n
827:n
820:n
813:n
795:n
788:n
781:n
774:n
757:n
747:n
664:n
652:n
648:n
511:k
507:A
503:k
479:}
473::
467:,
461::
455:,
449::
443:{
432:}
426::
420:,
414::
408:,
402::
396:{
368:D
364:v
360:j
356:k
274:)
271:e
268:u
265:l
262:a
259:v
256:,
253:y
250:e
247:k
244:(
218:)
215:e
212:u
209:l
206:a
203:v
200:,
197:y
194:e
191:k
188:(
44:.
37:.
30:.
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.