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