2215:
1848:
2206:
1840:
190:
3892:, auxiliary data tables that are used to speed up the access to data that is primarily stored in slower media. In this application, hash collisions can be handled by discarding one of the two colliding entries—usually erasing the old item that is currently stored in the table and overwriting it with the new item, so every item in the table has a unique hash value.
2439:. The neighbourhood characteristic of hopscotch hashing guarantees a property that, the cost of finding the desired item from any given buckets within the neighbourhood is very close to the cost of finding it in the bucket itself; the algorithm attempts to be an item into its neighbourhood—with a possible cost involved in displacing other items.
1831:. The ideal case is such that no two search keys hashes to the same array index. However, this is not always the case and is impossible to guarantee for unseen given data. Hence the second part of the algorithm is collision resolution. The two common methods for collision resolution are separate chaining and open addressing.
2396:
worst-case lookup complexity and constant amortized time for insertions. The collision is resolved through maintaining two hash tables, each having its own hashing function, and collided slot gets replaced with the given item, and the preoccupied element of the slot gets displaced into the other hash
3070:
caused by the old hash table. In such case, the rehashing operation is done incrementally through extending prior memory block allocated for the old hash table such that the buckets of the hash table remain unaltered. A common approach for amortized rehashing involves maintaining two hash functions
1808:
offers a way to prove a certain hash function does not have bad keysets for a given type of hashtable. A number of K-independence results are known for collision resolution schemes such as linear probing and cuckoo hashing. Since K-independence can prove a hash function works, one can then focus on
3058:, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. If one cannot avoid dynamic resizing, a solution is to perform the resizing gradually to avoid storage blip—typically at 50% of new table's size—during rehashing and to avoid
1772:
of the hash values is a fundamental requirement of a hash function. A non-uniform distribution increases the number of collisions and the cost of resolving them. Uniformity is sometimes difficult to ensure by design, but may be evaluated empirically using statistical tests, e.g., a
1863:
for each search array index. The collided items are chained together through a single linked list, which can be traversed to access the item with a unique search key. Collision resolution through chaining with linked list is a common method of implementation of hash tables. Let
2350:. The collision in coalesced hashing is resolved by identifying the largest-indexed empty slot on the hash table, then the colliding value is inserted into that slot. The bucket is also linked to the inserted node's slot which contains its colliding hash address.
1802:, the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash is claimed to have particularly poor clustering behavior.
1780:
The distribution needs to be uniform only for table sizes that occur in the application. In particular, if one uses dynamic resizing with exact doubling and halving of the table size, then the hash function needs to be uniform only when the size is a
2430:
of buckets—the subsequent buckets around any given occupied bucket, also called a "virtual" bucket. The algorithm is designed to deliver better performance when the load factor of the hash table grows beyond 90%; it also provides high throughput in
2238:, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates an unsuccessful search.
2132:
slots providing constant worst-case lookup time, and low amortized time for insertion. A study shows array-based separate chaining to be 97% more performant when compared to the standard linked list method under heavy load.
2218:
This graph compares the average number of CPU cache misses required to look up elements in large hash tables (far exceeding size of the cache) with chaining and linear probing. Linear probing performs better due to better
3045:
privately and every item in the original hash table gets moved to the newly allocated one by computing the hash values of the items followed by the insertion operation. Rehashing is simple, but computationally expensive.
6440:
283:
is infinite, the entire key can be used directly as an index to locate its value with a single memory access. On the other hand, if infinite time is available, values can be stored without regard for their keys, and a
1667:
263:
In a well-dimensioned hash table, the average time complexity for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of
3337:
6434:
702:
2501:
be the key to be inserted and bucket to which the key is hashed into respectively; several cases are involved in the insertion procedure such that the neighbourhood property of the algorithm is vowed: if
2209:
Hash collision resolved by open addressing with linear probing (interval=1). Note that "Ted Baker" has a unique hash, but nevertheless collided with "Sandra Dee", that had previously collided with "John
3773:
245:, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored. A map implemented by a hash table is called a
4762:"On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling"
2529:
to 1; if not empty, linear probing is used for finding an empty slot in the table, the bitmap of the bucket gets updated followed by the insertion; if the empty slot is not within the range of the
3947:, an "object" is a mutable collection of key-value pairs (called "properties"), where each key is either a string or a guaranteed-unique "symbol"; any other value, when used as a key, is first
3275:
3221:
3176:
1089:
5781:
2549:
Robin Hood hashing is an open addressing based collision resolution algorithm; the collisions are resolved through favouring the displacement of the element that is farthest—or longest
1516:
3660:
5881:
Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (February 2020). "Cache hit ratio maximization in device-to-device communications overlaying cellular networks".
2748:
1170:
2816:
903:
3481:
3411:
1256:
1016:
944:
868:
821:
3123:
3096:
3910:, which can store unique values without any particular order; set is typically used in testing the membership of a value in the collection, rather than element retrieval.
2043:
1431:
3808:) of the operation in a hash table is presupposed on the condition that the hash function doesn't generate colliding indices; thus, the performance of the hash table is
610:
3680:
3538:
2981:
2930:
2282:
986:
841:
794:
771:
652:
497:
1562:
1385:
1196:
2619:
2130:
3806:
3607:
3019:
2394:
2254:, in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the value given by the original hash computation.
2079:
2956:
2523:
2499:
3578:
3558:
2905:
2876:
2856:
2836:
2679:
2659:
2639:
2587:
2476:
2099:
1902:
1882:
1751:
1731:
1711:
1687:
1582:
1536:
1359:
1335:
1311:
1280:
1109:
747:
725:
575:
555:
517:
471:
451:
431:
916:
Separate chaining hash tables suffer gradually declining performance as the load factor grows, and no fixed point beyond which resizing is absolutely needed.
6223:
1595:
954:
With open addressing, each slot of the bucket array holds exactly one item. Therefore an open-addressed hash table cannot have a load factor greater than 1.
6141:
5977:
5855:
2180:
5471:
Poblete, P. V.; Viola, A. (July 2019). "Analysis of Robin Hood and Other
Hashing Algorithms Under the Random Probing Model, With and Without Deletions".
2230:
is another collision resolution technique in which every entry record is stored in the bucket array itself, and the hash resolution is performed through
389:, who discussed the idea of using remainder modulo a prime as a hash function. The word "hashing" was first published in an article by Robert Morris. A
2401:—which is identified through maintaining a threshold loop counter—both hash tables get rehashed with newer hash functions and the procedure continues.
4939:
5549:
5515:
1785:. Here the index can be computed as some range of bits of the hash function. On the other hand, some hashing algorithms prefer to have the size be a
657:
2346:
is a hybrid of both separate chaining and open addressing in which the buckets or nodes link within the table. The algorithm is ideally suited for
2992:
Repeated insertions cause the number of entries in a hash table to grow, which consequently increases the load factor; to maintain the amortized
4509:
623:
Hash tables are also commonly used to implement sets, by omitting the stored value for each key and merely tracking whether the key is present.
6079:
6072:
5766:
2569:
formation in the hash table. Each node within the hash table that uses Robin Hood hashing should be augmented to store an extra PSL value. Let
5948:
3025:
into the buckets of the new hash table, since the items cannot be copied over as varying table sizes results in different hash value due to
6792:
5736:
1774:
5655:
3280:
2264:
The performance of open addressing may be slower compared to separate chaining since the probe sequence increases when the load factor
823:. This helps maintain good performance. Therefore, a common approach is to resize or "rehash" the hash table whenever the load factor
6468:
5588:
6297:
3809:
5446:
4261:
352:
5999:
4833:
2553:(PSL)—from its "home location" i.e. the bucket to which the item was hashed into. Although Robin Hood hashing does not change the
6271:
3951:
to a string. Aside from the seven "primitive" data types, every value in JavaScript is an object. ECMAScript 2015 also added the
260:, where the hash function generates the same index for more than one key, therefore typically must be accommodated in some way.
4121:
2397:
table. The process continues until every key has its own spot in the empty buckets of the tables; if the procedure enters into
1468:
6762:
6361:
6169:
5693:
5651:
5432:
5395:
5351:
5301:
5208:
5159:
5119:
5104:
5087:
4986:
4911:
4741:
4733:
4471:
4413:
4367:
4342:
4296:
4233:
4186:
3685:
2160:—when the nodes of the linked list are scattered across memory, thus the list traversal during insert and search may entail
6826:
2537:-1, subsequent swap and hop-info bit array manipulation of each bucket is performed in accordance with its neighbourhood
2234:. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some
3021:
performance of the lookup and insertion operations, a hash table is dynamically resized and the items of the tables are
6046:
5925:
5724:
4206:
3226:
356:
6249:
5825:
5005:(2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree".
6701:
5263:
5043:
Askitis, Nikolas; Sinha, Ranjan (October 2010). "Engineering scalable, cache and space efficient tries for strings".
4668:
4632:
2001:
617:
17:
3181:
3136:
3508:
is an implementation of the hash table which enables dynamic growths or shrinks of the table one bucket at a time.
6425:
6215:
6021:
1032:
6491:
6133:
3029:. If a hash table becomes "too empty" after deleting some elements, resizing may be performed to avoid excessive
2554:
2297:
1769:
6496:
4064:
913:
With separate chaining hash tables, each slot of the bucket array stores a pointer to a list or array of data.
5070:
Askitis, Nikolas; Zobel, Justin (October 2005). "Cache-conscious
Collision Resolution in String Hash Tables".
2179:
is used in the place where a linked list or self-balancing binary search trees is usually deployed, since the
6461:
4013:
3612:
6570:
5538:
4928:
2188:
1283:
5507:
5072:
Proceedings of the 12th
International Conference, String Processing and Information Retrieval (SPIRE 2005)
4665:
Algorithms—ESA 2009: 17th Annual
European Symposium, Copenhagen, Denmark, September 7–9, 2009, Proceedings
6575:
6558:
4037:
4027:
3988:
3936:
Many programming languages provide hash table functionality, either as built-in associative arrays or as
2688:
1114:
2756:
2312:
Since the slots are located in successive locations, linear probing could lead to better utilization of
6831:
6774:
6541:
6536:
5777:
5246:
4969:
Culpepper, J. Shane; Moffat, Alistair (2005). "Enhanced Byte Codes with
Restricted Prefix Properties".
4727:
4328:
4176:
1997:
873:
35:
4534:
4501:
3846:
Hash tables are commonly used to implement many types of in-memory tables. They are used to implement
3419:
3349:
6531:
5007:
4210:
3974:
3059:
3042:
2451:
2168:
2149:
1205:
994:
922:
846:
799:
6083:
3101:
3074:
6565:
6524:
6454:
6353:
5614:
5334:
5191:
4677:
4334:
3517:
2562:
2293:
406:
320:
222:
3125:. The process of rehashing a bucket's items in accordance with the new hash function is termed as
409:
of (key, value) pairs and allows insertion, deletion, and lookup (search), with the constraint of
6805:
6782:
5751:
5293:
2538:
2289:
2049:
2011:
1450:
1390:
62:
5713:
6787:
6587:
5955:
5424:
5329:
5186:
4672:
4101:
4091:
3813:
3067:
3063:
580:
390:
367:
6713:
6668:
6630:
5644:
4126:
3963:
3665:
3523:
2436:
2317:
2267:
2220:
2157:
2102:
2005:
1805:
1314:
1287:
971:
826:
779:
756:
637:
476:
253:
6345:
4936:
6.897: Advanced Data
Structures. MIT Computer Science and Artificial Intelligence Laboratory
3928:
to a complex Hash Table which stores information about each section that has been searched.
1541:
1364:
1175:
6653:
6178:
5821:
5233:
5028:
4715:
4694:
4377:
4316:
4249:
4164:
2592:
2432:
2108:
6191:
6164:
5575:
3782:
3583:
3516:
The performance of a hash table is dependent on the hash function's ability in generating
2995:
2370:
2055:
1823:
A search algorithm that uses hashing consists of two parts. The first part is computing a
8:
6371:
McKenzie, B. J.; Harries, R.; Bell, T. (February 1990). "Selecting a hashing algorithm".
6346:
4136:
4021:
3982:
3925:
3919:
3342:
such that each element in the bucket gets rehashed and its procedure involve as follows:
2935:
1977:
382:
276:
265:
46:
6182:
5415:
5286:
4837:
4253:
2961:
2910:
2505:
2481:
2140:
for each buckets also result in constant time for all operations with high probability.
6696:
6681:
6546:
6506:
6398:
6344:
Tamassia, Roberto; Goodrich, Michael T. (2006). "Chapter Nine: Maps and
Dictionaries".
6196:
5991:
5898:
5670:
5621:
5584:
5545:
5511:
5488:
4811:
4638:
4564:
4505:
4096:
4086:
3907:
3901:
3563:
3543:
2881:
2861:
2841:
2821:
2664:
2644:
2624:
2572:
2461:
2084:
1887:
1867:
1860:
1798:
1736:
1716:
1696:
1672:
1567:
1521:
1344:
1338:
1320:
1296:
1265:
1094:
957:
The performance of open addressing becomes very bad when the load factor approaches 1.
732:
710:
560:
522:
502:
456:
436:
416:
375:
269:
214:
4598:
6615:
6514:
6357:
6200:
5971:
5902:
5689:
5492:
5438:
5428:
5391:
5347:
5297:
5259:
5204:
5155:
5115:
5083:
4982:
4907:
4877:
4860:
4737:
4628:
4467:
4409:
4338:
4292:
4229:
4182:
3889:
3883:
3847:
3841:
2526:
2415:
2410:
2343:
2338:
2251:
2184:
2052:, two-level hash tables are used to reduce the look-up complexity to be a guaranteed
1446:
402:
316:
308:
300:
210:
68:
6402:
4568:
3041:
Generally, a new hash table with a size double that of the original hash table gets
2214:
1713:
is the size of the table. An advantage of the hashing by multiplication is that the
6638:
6388:
6380:
6186:
5890:
5728:
5480:
5383:
5339:
5229:
5196:
5075:
5052:
5016:
4974:
4872:
4803:
4773:
4719:
4711:
4682:
4642:
4620:
4594:
4556:
4459:
4401:
4320:
4312:
4221:
4168:
4160:
4007:
3968:
3937:
3863:
3339:
3055:
3030:
3026:
2566:
2301:
2153:
1818:
348:
158:
5125:
1433:. A perfect hash function can be created if all the keys are known ahead of time.
303:
lookup structure. For this reason, they are widely used in many kinds of computer
6658:
6600:
6420:
5859:
5387:
5024:
4897:
4690:
4686:
4585:
Owolabi, Olumide (February 2003). "Empirical studies of some hashing functions".
4111:
3948:
3867:
3130:
2327:
2227:
2200:
1793:
613:
343:
was proposed by A. D. Linh, building on Luhn's memorandum. Around the same time,
340:
332:
280:
87:
4225:
2260:, in which the interval between probes is computed by a secondary hash function.
1904:
be the hash table and the node respectively, the operation involves as follows:
6750:
6728:
6553:
6477:
5241:
4791:
4723:
4657:
4619:. 2006 IEEE International Symposium on Information Theory. pp. 2774–2778.
4324:
4172:
4131:
3505:
3500:
2750:: the iteration goes into the next bucket without attempting an external probe.
2454:
of the item which was originally hashed into the current virtual bucket within
2423:
2419:
2364:
2359:
2321:
2257:
2245:
1454:
312:
257:
206:
91:
5484:
5056:
5020:
4777:
2442:
Each bucket within the hash table includes an additional "hop-information"—an
2205:
1847:
1839:
753:
The performance of the hash table deteriorates in relation to the load factor
331:
The idea of hashing arose independently in different places. In
January 1953,
295:
In many situations, hash tables turn out to be on average more efficient than
189:
6820:
6723:
6620:
6605:
5921:
5894:
5343:
5200:
4624:
4202:
4106:
2398:
2367:
is a form of open addressing collision resolution technique which guarantees
2285:
2172:
1824:
1027:
371:
289:
285:
226:
6348:
Data structures and algorithms in Java : [updated for Java 5.0]
6322:
5917:
5810:
5442:
5112:
Proceedings of the 32nd
Australasian Computer Science Conference (ACSC 2009)
2288:
if the load factor reaches 1, in the case of a completely filled table. The
1973:
6384:
6245:
5378:
Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch
Hashing".
4757:
4280:
4081:
1786:
1782:
1758:
1754:
386:
360:
4560:
4463:
4405:
3779:, which is dealt with in a variety of ways. The constant time complexity (
1851:
Hash collision by separate chaining with head records in the bucket array.
374:
independently had the same idea. The term "open addressing" was coined by
6718:
6643:
5851:
5817:
5712:
Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (March 18, 2003).
5321:
5307:
5255:
5178:
5002:
4656:
Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009).
4181:(3rd ed.). Massachusetts Institute of Technology. pp. 253–280.
3817:
2347:
2137:
1993:
1981:
1856:
1828:
1690:
870:. Similarly the table may also be resized if the load factor drops below
344:
296:
6216:"Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding"
5079:
4901:
6706:
5382:. Lecture Notes in Computer Science. Vol. 5218. pp. 350–364.
5328:. Lecture Notes in Computer Science. Vol. 2161. pp. 121–133.
5237:
5185:. Lecture Notes in Computer Science. Vol. 2161. pp. 121–133.
4978:
4815:
3944:
3859:
1662:{\displaystyle h(x)=\lfloor m{\bigl (}(MA){\bmod {1}}{\bigr )}\rfloor }
1259:
410:
218:
6393:
2223:, though as the table gets full, its performance degrades drastically.
1198:. The conventional implementations of hash functions are based on the
370:. Open addressing with linear probing is credited to Amdahl, although
6648:
6595:
6429:
5732:
5251:
5150:
Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990).
4861:"New hash functions and their use in authentication and set equality"
2525:
is empty, the element is inserted, and the leftmost bit of bitmap is
2447:
2418:
is an open addressing based algorithm which combines the elements of
2313:
2304:, since formation of clusters would result in increased search time.
2176:
2161:
378:
on his article which discusses the problem of search in large files.
213:, also called a dictionary or simply map; an associative array is an
198:
31:
6108:
4973:. Lecture Notes in Computer Science. Vol. 3772. pp. 1–12.
4807:
4761:
4376:. Vol. 1 (4 ed.). Addison-Wesley Professional – via
4254:"Lecture 13: Amortized Algorithms, Table Doubling, Potential Method"
654:
is a critical statistic of a hash table, and is defined as follows:
6745:
6691:
6519:
4116:
3821:
3609:
denotes the key, number of buckets and the hash function such that
2558:
413:. In the hash table implementation of associative arrays, an array
304:
6446:
4371:
3332:{\displaystyle \mathrm {Lookup} (\mathrm {key} ,{\text{command}})}
339:
memorandum that used hashing with chaining. The first example of
6740:
6686:
3958:
1984:, it results in faster termination of the unsuccessful searches.
616:
bounds on search, delete, and insert operations in comparison to
393:
of linear probing was submitted originally by Konheim and Weiss.
364:
6134:"Lesson: Implementations (The Java™ Tutorials > Collections)"
4903:
The Art of Computer Programming: Volume 3: Sorting and Searching
4655:
4547:
Maurer, W. D.; Lewis, T. G. (March 1975). "Hash Table Methods".
4454:
Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj, eds. (2004).
6735:
6676:
4068:
3871:
2148:
The linked list of separate chaining implementation may not be
697:{\displaystyle {\text{load factor}}\ (\alpha )={\frac {n}{m}},}
6022:"JavaScript data types and data structures - JavaScript | MDN"
3816:
the indices. However, construction of such a hash function is
2328:
Other collision resolution techniques based on open addressing
1987:
1640:
1498:
2292:
of linear probing depends on the hash function's ability to
2248:, in which the interval between probes is fixed (usually 1).
1457:. However, hashing by division is the commonly used scheme.
991:
With open addressing, acceptable figures of max load factor
6757:
6416:
4052:
5767:"Linear hashing: A new tool for file and table addressing"
5711:
5228:
5149:
4710:
4311:
4159:
2191:—resulting in reduced access time and memory consumption.
946:
that gives best performance is typically between 1 and 3.
336:
3955:
data structure, which accepts arbitrary values as keys.
3049:
1445:
include hashing by division, hashing by multiplication,
612:. Under reasonable assumptions, hash tables have better
3967:
in its standard library for storing keys and values of
3768:{\displaystyle K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})}
2983:; repeat the procedure until every element is inserted.
1592:
The scheme in hashing by multiplication is as follows:
1111:
of keys to indices or slots within the table, that is,
5539:"JavaHyperText and Data Structure: Robin Hood Hashing"
4671:. Vol. 5757. Berlin: Springer. pp. 682–693.
4034:
uses the open addressing model from Ruby 2.4 onwards.
2307:
1855:
In separate chaining, the process involves building a
1202:
that all elements of the table stem from the universe
6165:"Redis rehash optimization based on machine learning"
3785:
3688:
3668:
3615:
3586:
3566:
3546:
3526:
3422:
3352:
3283:
3229:
3184:
3139:
3104:
3077:
2998:
2964:
2938:
2913:
2884:
2864:
2844:
2824:
2759:
2691:
2681:
be the index, the insertion procedure is as follows:
2667:
2647:
2627:
2595:
2575:
2508:
2484:
2464:
2373:
2270:
2171:
of collision resolution through separate chaining, a
2111:
2087:
2081:
in the worst case. In this technique, the buckets of
2058:
2014:
1890:
1870:
1739:
1719:
1699:
1675:
1598:
1570:
1544:
1524:
1471:
1393:
1367:
1347:
1323:
1299:
1268:
1208:
1178:
1117:
1097:
1035:
997:
974:
925:
876:
849:
829:
802:
782:
759:
735:
713:
660:
640:
583:
563:
525:
505:
479:
459:
439:
419:
6073:"Programming language C++ - Technical Specification"
5377:
5324:; Rodler, Flemming Friche (2001). "Cuckoo Hashing".
5181:; Rodler, Flemming Friche (2001). "Cuckoo Hashing".
4333:(2nd ed.). MIT Press and McGraw-Hill. pp.
4258:
course MIT 6.046J/18.410J Introduction to Algorithms
2143:
908:
776:
The software typically ensures that the load factor
727:
is the number of entries occupied in the hash table.
6370:
5643:Devadas, Srini; Demaine, Erik (February 25, 2011).
5285:
4615:Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006).
4291:(2nd ed.). Addison-Wesley. pp. 513–558.
3800:
3767:
3674:
3654:
3601:
3572:
3552:
3532:
3475:
3405:
3331:
3269:
3215:
3170:
3117:
3090:
3013:
2975:
2950:
2924:
2899:
2870:
2850:
2830:
2810:
2742:
2673:
2653:
2633:
2613:
2581:
2517:
2493:
2470:
2388:
2276:
2124:
2093:
2073:
2045:, although it introduces additional complexities.
2037:
1896:
1876:
1745:
1725:
1705:
1681:
1661:
1576:
1556:
1530:
1510:
1425:
1379:
1353:
1329:
1305:
1274:
1250:
1190:
1164:
1103:
1083:
1010:
980:
949:
938:
897:
862:
835:
815:
788:
765:
741:
719:
696:
646:
604:
569:
549:
511:
491:
465:
445:
425:
5880:
5856:pl:Polsko-Japońska Akademia Technik Komputerowych
4859:Wegman, Mark N.; Carter, J.Lawrence (June 1981).
4794:(1983). "Karl Pearson and the Chi-Squared Test".
4614:
3906:Hash tables can be used in the implementation of
3270:{\displaystyle \mathrm {Delete} (\mathrm {key} )}
3036:
1809:finding the fastest possible such hash function.
1465:The scheme in hashing by division is as follows:
960:Therefore a hash table that uses open addressing
6818:
6343:
5976:: CS1 maint: bot: original URL status unknown (
5811:"Analysing and Improving Hash Table Performance"
5714:"Hash Tables for Embedded and Real-time systems"
5684:Thareja, Reema (2014). "Hashing and Collision".
1980:, and inserted into the list by maintaining the
1003:
931:
882:
855:
808:
6298:"Dictionary Class (System.Collections.Generic)"
6213:
5105:"Fast and Compact Hash Tables for Integer Keys"
4968:
4896:
4706:
4704:
4453:
4201:
2565:of the items on the buckets, i.e. dealing with
6426:Open Data Structures – Chapter 5 – Hash Tables
6080:International Organization for Standardization
5642:
4366:
4155:
4153:
3216:{\displaystyle \mathrm {Get} (\mathrm {key} )}
3171:{\displaystyle \mathrm {Add} (\mathrm {key} )}
2435:, thus well suited for implementing resizable
1436:
6462:
6352:(4th ed.). Hoboken, NJ: Wiley. pp.
5992:"Transposition Table - Chessprogramming wiki"
5958:. Archived from the original on April 1, 2022
5721:All Computer Science and Engineering Research
5688:. Oxford University Press. pp. 464–488.
5409:
5407:
1796:schemes, the hash function should also avoid
1651:
1622:
385:work on hashing with chaining is credited to
27:Associative array for storing key-value pairs
6272:"HashSet Class (System.Collections.Generic)"
5849:
5774:Proc. 6th Conference on Very Large Databases
5470:
5288:The design and analysis of coalesced hashing
5069:
5042:
4858:
4701:
4502:"CS 312: Hash tables and amortized analysis"
4456:Handbook of Data Structures and Applications
3054:Some hash table implementations, notably in
2183:pattern of the array could be exploited by
1843:Hash collision resolved by separate chaining
1656:
1614:
1587:
1245:
1215:
1084:{\displaystyle h:U\rightarrow \{0,...,m-1\}}
1078:
1048:
6441:MIT's Introduction to Algorithms: Hashing 2
6435:MIT's Introduction to Algorithms: Hashing 1
6109:"The Go Programming Language Specification"
5946:
5645:"Intro to Algorithms: Resizing Hash Tables"
5284:Vitter, Jeffery S.; Chen, Wen-Chin (1987).
5154:. Prentice Hall. pp. 456–461, p. 472.
5143:
4971:String Processing and Information Retrieval
4926:
4546:
4495:
4493:
4491:
4489:
4487:
4485:
4483:
4449:
4447:
4445:
4150:
4063:, so it can be used from languages such as
3820:, that being so, implementations depend on
1988:Other data structures for separate chaining
1764:
6469:
6455:
5915:
5707:
5705:
5583:(Technical report). Bloomington, Indiana:
5404:
5320:
5283:
5177:
4892:
4890:
4888:
4443:
4441:
4439:
4437:
4435:
4433:
4431:
4429:
4427:
4425:
4362:
4360:
4358:
4356:
4354:
3662:. If the hash function generates the same
6392:
6190:
5804:
5802:
5567:
5499:
5333:
5279:
5277:
5275:
5190:
5173:
5171:
4964:
4962:
4960:
4927:Demaine, Erik; Lind, Jeff (Spring 2003).
4876:
4676:
4391:
4389:
4387:
4248:
4020:implements a hash table in the form of a
3981:implements a hash table in the form of a
3824:
3812:to the chosen hash function's ability to
1511:{\displaystyle h(x)\ =\ x\,{\bmod {\,}}m}
1502:
1496:
6162:
5505:
5473:Combinatorics, Probability and Computing
5373:
5371:
5369:
5367:
5365:
5363:
5074:. Vol. 3772/2005. pp. 91–102.
4790:
4784:
4750:
4617:Perfect Hashing for Network Applications
4580:
4578:
4529:
4527:
4480:
3874:are more popular in these applications.
3133:by encapsulating the operations such as
2284:approaches 1. The probing results in an
2213:
2204:
1846:
1838:
1827:which transforms the search key into an
188:
5702:
5683:
5612:
5587:, Department of Computer Science. 246.
5224:
5222:
5220:
5102:
5001:
4885:
4865:Journal of Computer and System Sciences
4756:
4610:
4608:
4584:
4533:James S. Plank and Brad Vander Zanden.
4422:
4395:
4351:
4275:
4273:
4271:
3655:{\displaystyle \sigma \ =\ h(K)\ \%\ n}
1812:
14:
6819:
6295:
6002:from the original on February 14, 2021
5799:
5764:
5272:
5168:
4957:
4499:
4384:
4048:as part of the Rust Standard Library.
3913:
3540:) for entries in the hash table where
1460:
6450:
6252:from the original on December 8, 2022
6214:Jonan Scheffler (December 25, 2016).
6170:Journal of Physics: Conference Series
6144:from the original on January 18, 2017
5928:from the original on December 4, 2020
5916:Bottommley, James (January 1, 2004).
5831:from the original on November 6, 2021
5652:Massachusetts Institute of Technology
5594:from the original on November 3, 2021
5573:
5536:
5452:from the original on November 1, 2021
5413:
5360:
4827:
4825:
4734:Massachusetts Institute of Technology
4575:
4524:
4305:
4279:
4242:
3888:Hash tables can be used to implement
3835:
3050:Alternatives to all-at-once rehashing
2544:
2426:and chaining through the notion of a
919:With separate chaining, the value of
292:can be used to retrieve the element.
272:constant average cost per operation.
5808:
5518:from the original on October 7, 2021
5217:
4831:
4605:
4268:
4264:from the original on August 7, 2009.
4211:"Hash Tables and Associative Arrays"
3853:
2404:
2332:
2241:Well-known probe sequences include:
1972:If the element is comparable either
1834:
1777:for discrete uniform distributions.
1733:is not critical. Although any value
6476:
5555:from the original on April 26, 2021
4726:(2001). "Chapter 11: Hash Tables".
4649:
4587:Information and Software Technology
4512:from the original on April 26, 2021
4327:(2001). "Chapter 11: Hash Tables".
2987:
2743:{\displaystyle x.psl\ \leq \ T.psl}
2621:be the (incremental) PSL length of
1165:{\displaystyle h(x)\in {0,...,m-1}}
24:
6337:
6082:. pp. 812–813. Archived from
5725:Washington University in St. Louis
5654:, Department of Computer Science.
5548:, Department of Computer Science.
5514:, Department of Computer Science.
5114:. Vol. 91. pp. 113–122.
4945:from the original on June 15, 2010
4822:
4508:, Department of Computer Science.
4122:Rabin–Karp string search algorithm
3991:programming language includes the
3931:
3643:
3463:
3460:
3457:
3436:
3433:
3430:
3427:
3424:
3393:
3390:
3387:
3366:
3363:
3360:
3357:
3354:
3314:
3311:
3308:
3300:
3297:
3294:
3291:
3288:
3285:
3260:
3257:
3254:
3246:
3243:
3240:
3237:
3234:
3231:
3206:
3203:
3200:
3192:
3189:
3186:
3161:
3158:
3155:
3147:
3144:
3141:
2811:{\displaystyle x.psl\ >\ T.psl}
2194:
796:remains below a certain constant,
618:self-balancing binary search trees
252:Most hash table designs employ an
193:A small phone book as a hash table
25:
6843:
6410:
6373:Software: Practice and Experience
6226:from the original on July 3, 2019
6163:Zhang, Juan; Jia, Yunwei (2020).
5754:, Department of Computer Science.
5742:from the original on June 9, 2021
4669:Lecture Notes in Computer Science
4380:, Department of Computer Science.
4195:
3827:in achieving higher performance.
3494:
2353:
2308:Caching and locality of reference
2144:Caching and locality of reference
2002:self-balancing binary search tree
1018:should range around 0.6 to 0.75.
909:Load factor for separate chaining
898:{\displaystyle \alpha _{\max }/4}
519:gets stored at an index location
41:"Rehash" redirects here. For the
5787:from the original on May 6, 2021
5661:from the original on May 7, 2021
4796:International Statistical Review
4535:"CS140 Lecture notes -- Hashing"
3858:Hash tables may also be used as
3476:{\displaystyle \mathrm {Table} }
3406:{\displaystyle \mathrm {Table} }
1996:, it could be efficient to use "
1021:
6315:
6289:
6264:
6238:
6207:
6192:10.1088/1742-6596/1453/1/012048
6156:
6126:
6101:
6065:
6039:
6014:
5984:
5940:
5909:
5874:
5843:
5758:
5677:
5636:
5606:
5574:Celis, Pedro (March 28, 1988).
5530:
5464:
5314:
5096:
5063:
5036:
4995:
4920:
4906:. Addison-Wesley Professional.
4852:
4540:
4285:The Art of Computer Programming
3830:
3825:collision resolution techniques
3129:, which is implemented through
2557:, it significantly affects the
1441:The schemes of hashing used in
1251:{\displaystyle U=\{0,...,u-1\}}
1011:{\displaystyle \alpha _{\max }}
950:Load factor for open addressing
939:{\displaystyle \alpha _{\max }}
863:{\displaystyle \alpha _{\max }}
816:{\displaystyle \alpha _{\max }}
5852:"Indexes and external sorting"
4658:"Hash, displace, and compress"
4218:Algorithms and Data Structures
4040:programming language includes
3795:
3789:
3762:
3749:
3734:
3721:
3637:
3631:
3596:
3590:
3511:
3470:
3467:
3453:
3440:
3400:
3397:
3383:
3370:
3326:
3304:
3264:
3250:
3210:
3196:
3165:
3151:
3118:{\displaystyle h_{\text{new}}}
3091:{\displaystyle h_{\text{old}}}
3037:Resizing by moving all entries
3008:
3002:
2932:; continue the probe from the
2894:
2888:
2793:
2787:
2725:
2719:
2383:
2377:
2300:throughout the table to avoid
2068:
2062:
2032:
2018:
1938:search for an element with key
1636:
1627:
1608:
1602:
1481:
1475:
1127:
1121:
1045:
675:
669:
626:
593:
587:
544:
541:
535:
529:
13:
1:
5427:, Dept. of Computer Science.
4599:10.1016/S0950-5849(02)00174-X
4143:
3066:due to deallocation of large
1387:maps to a different value in
5388:10.1007/978-3-540-87779-0_24
4878:10.1016/0022-0000(81)90033-7
4687:10.1007/978-3-642-04128-0_61
4220:. Springer. pp. 81–98.
2189:translation lookaside buffer
363:implemented hashing for the
7:
6793:Directed acyclic word graph
6559:Double-ended priority queue
5577:External Robin Hood Hashing
5563:– via cs.cornell.edu.
5526:– via cs.cornell.edu.
5292:. New York, United States:
4832:Wang, Thomas (March 1997).
4520:– via cs.cornell.edu.
4398:Hashing in Computer Science
4226:10.1007/978-3-540-77978-0_4
4074:
3862:-based data structures and
2589:be the key to be inserted,
2038:{\displaystyle O(\log {n})}
2000:" concepts such as using a
1443:integer universe assumption
1437:Integer universe assumption
1426:{\displaystyle {0,...,m-1}}
1361:, that is, if each element
1200:integer universe assumption
396:
275:Hashing is an example of a
10:
6848:
6827:Hash-based data structures
5778:Carnegie Mellon University
5506:Clarkson, Michael (2014).
5247:Introduction to Algorithms
5244:(2001), "11 Hash Tables",
4729:Introduction to Algorithms
4330:Introduction to Algorithms
4178:Introduction to Algorithms
4055:standard library includes
3917:
3899:
3881:
3839:
3498:
2408:
2357:
2336:
2198:
2185:hardware-cache prefetchers
1923:at the head of linked list
1816:
1775:Pearson's chi-squared test
1753:produces a hash function,
1584:is the size of the table.
326:
40:
29:
6801:
6773:
6667:
6629:
6586:
6505:
6484:
5615:"Chapter C5: Hash Tables"
5508:"Lecture 13: Hash tables"
5485:10.1017/S0963548318000408
5103:Askitis, Nikolas (2009).
5057:10.1007/s00778-010-0183-9
5021:10.1137/S0097539797322425
5008:SIAM Journal on Computing
4834:"Prime Double Hash Table"
4778:10.1080/14786440009463897
4396:Konheim, Alan G. (2010).
3877:
2136:Techniques such as using
2101:entries are organized as
2008:could be brought down to
1588:Hashing by multiplication
749:is the number of buckets.
605:{\displaystyle h(x)<m}
453:is partially filled with
164:
157:
142:
127:
112:
97:
86:
82:
74:
61:
56:
6525:Retrieval Data Structure
6323:"VB.NET HashSet Example"
6047:"Map - JavaScript | MDN"
5895:10.23919/jcc.2020.02.018
5344:10.1007/3-540-44676-1_10
5201:10.1007/3-540-44676-1_10
4625:10.1109/ISIT.2006.261567
2169:cache-conscious variants
1765:Choosing a hash function
577:is a hash function, and
30:Not to be confused with
6806:List of data structures
6783:Binary decision diagram
5949:"Set & Hash Tables"
5918:"Understanding Caching"
5795:– via cs.cmu.edu.
5765:Litwin, Witold (1980).
5752:Northwestern University
5686:Data Structures Using C
5613:Goddard, Wayne (2021).
5294:Oxford University Press
5152:Data Structures Using C
4500:Mayers, Andrew (2008).
4370:; Wayne, Kevin (2011).
3895:
3675:{\displaystyle \sigma }
3533:{\displaystyle \sigma }
2555:theoretical search cost
2348:fixed memory allocation
2277:{\displaystyle \alpha }
2050:dynamic perfect hashing
1451:dynamic perfect hashing
1282:is confined within the
981:{\displaystyle \alpha }
836:{\displaystyle \alpha }
789:{\displaystyle \alpha }
766:{\displaystyle \alpha }
647:{\displaystyle \alpha }
492:{\displaystyle m\geq n}
254:imperfect hash function
6788:Directed acyclic graph
6385:10.1002/spe.4380200207
5956:Texas State University
5809:Dijk, Tom Van (2010).
5425:University of Waterloo
4766:Philosophical Magazine
4102:Hash array mapped trie
4092:Distributed hash table
3818:practically infeasible
3802:
3769:
3676:
3656:
3603:
3574:
3554:
3534:
3477:
3407:
3333:
3271:
3217:
3172:
3119:
3092:
3015:
2977:
2952:
2926:
2901:
2872:
2852:
2832:
2812:
2744:
2675:
2661:be the hash table and
2655:
2635:
2615:
2583:
2519:
2495:
2472:
2390:
2318:locality of references
2278:
2224:
2211:
2126:
2095:
2075:
2039:
2006:theoretical worst case
1898:
1878:
1852:
1844:
1747:
1727:
1707:
1683:
1663:
1578:
1558:
1557:{\displaystyle x\in S}
1538:is the hash digest of
1532:
1512:
1455:static perfect hashing
1427:
1381:
1380:{\displaystyle x\in S}
1355:
1331:
1307:
1276:
1252:
1192:
1191:{\displaystyle x\in U}
1166:
1105:
1085:
1012:
982:
940:
899:
864:
837:
817:
790:
767:
743:
721:
698:
648:
606:
571:
551:
513:
493:
467:
447:
427:
225:. A hash table uses a
194:
6443:MIT OCW lecture Video
6437:MIT OCW lecture Video
6051:developer.mozilla.org
6026:developer.mozilla.org
5537:Gries, David (2017).
5414:Celis, Pedro (1986).
5380:Distributed Computing
5326:Algorithms — ESA 2001
5234:Leiserson, Charles E.
5183:Algorithms — ESA 2001
4716:Leiserson, Charles E.
4561:10.1145/356643.356645
4549:ACM Computing Surveys
4464:10.1201/9781420035179
4406:10.1002/9780470630617
4317:Leiserson, Charles E.
4289:Sorting and Searching
4250:Leiserson, Charles E.
4165:Leiserson, Charles E.
4127:Search data structure
3810:directly proportional
3803:
3770:
3677:
3657:
3604:
3575:
3555:
3535:
3478:
3408:
3334:
3272:
3218:
3173:
3120:
3093:
3016:
2978:
2953:
2927:
2902:
2873:
2853:
2833:
2813:
2745:
2676:
2656:
2636:
2616:
2614:{\displaystyle x.psl}
2584:
2551:probe sequence length
2520:
2496:
2473:
2437:concurrent hash table
2391:
2320:resulting in reduced
2279:
2221:locality of reference
2217:
2208:
2181:contiguous allocation
2158:locality of reference
2127:
2125:{\displaystyle k^{2}}
2096:
2076:
2040:
1899:
1879:
1850:
1842:
1806:K-independent hashing
1748:
1728:
1708:
1684:
1664:
1579:
1559:
1533:
1513:
1428:
1382:
1356:
1332:
1308:
1288:computer architecture
1277:
1253:
1193:
1167:
1106:
1086:
1013:
983:
941:
900:
865:
838:
818:
791:
768:
744:
722:
699:
649:
607:
572:
552:
514:
494:
468:
448:
428:
192:
6654:Unrolled linked list
5996:chessprogramming.org
5947:Jill Seaman (2014).
5883:China Communications
5822:University of Twente
5780:. pp. 212–223.
5258:, pp. 221–252,
5131:on February 16, 2011
4840:on September 3, 1999
4378:Princeton University
3801:{\displaystyle O(1)}
3783:
3686:
3666:
3613:
3602:{\displaystyle h(x)}
3584:
3564:
3544:
3524:
3518:quasi-random numbers
3420:
3350:
3281:
3227:
3182:
3137:
3102:
3075:
3060:memory fragmentation
3014:{\displaystyle O(1)}
2996:
2962:
2958:st bucket to insert
2936:
2911:
2882:
2862:
2842:
2822:
2757:
2689:
2665:
2645:
2625:
2593:
2573:
2539:invariant properties
2506:
2482:
2462:
2389:{\displaystyle O(1)}
2371:
2268:
2109:
2085:
2074:{\displaystyle O(1)}
2056:
2012:
2004:, through which the
1965:from the linked list
1949:Chained-Hash-Delete(
1928:Chained-Hash-Search(
1907:Chained-Hash-Insert(
1888:
1868:
1813:Collision resolution
1770:Uniform distribution
1737:
1717:
1697:
1691:real-valued constant
1673:
1596:
1568:
1542:
1522:
1469:
1391:
1365:
1345:
1321:
1297:
1266:
1206:
1176:
1115:
1095:
1033:
995:
972:
923:
874:
847:
827:
800:
780:
757:
733:
711:
658:
638:
581:
561:
523:
503:
477:
457:
437:
417:
391:theoretical analysis
6702:Self-balancing tree
6302:learn.microsoft.com
6276:learn.microsoft.com
6246:"doc.rust-lang.org"
6183:2020JPhCS1453a2048Z
6089:on January 21, 2022
5423:. Ontario, Canada:
5080:10.1007/11575832_11
4137:Succinct hash table
3926:transposition table
3920:Transposition table
3914:Transposition table
3775:), this results in
3682:for distinct keys (
2951:{\displaystyle j+1}
2450:for indicating the
2433:concurrent settings
2103:perfect hash tables
1757:suggests using the
1461:Hashing by division
968:if the load factor
353:Nathaniel Rochester
307:, particularly for
277:space-time tradeoff
237:, into an array of
209:that implements an
47:Rehash (South Park)
6682:Binary search tree
6547:Double-ended queue
5850:Lech Banachowski.
5671:MIT OpenCourseWare
5622:Clemson University
5585:Indiana University
5546:Cornell University
5512:Cornell University
5417:Robin Hood Hashing
4979:10.1007/11575832_1
4900:(April 24, 1998).
4506:Cornell University
4097:Extendible hashing
4087:Consistent hashing
3908:set data structure
3902:Set data structure
3848:associative arrays
3836:Associative arrays
3798:
3765:
3672:
3652:
3599:
3570:
3550:
3530:
3473:
3403:
3329:
3267:
3213:
3168:
3115:
3088:
3011:
2976:{\displaystyle x'}
2973:
2948:
2925:{\displaystyle x'}
2922:
2897:
2868:
2848:
2828:
2818:: insert the item
2808:
2740:
2671:
2651:
2631:
2611:
2579:
2545:Robin Hood hashing
2518:{\displaystyle Bk}
2515:
2494:{\displaystyle Bk}
2491:
2468:
2386:
2274:
2225:
2212:
2122:
2091:
2071:
2035:
1894:
1874:
1853:
1845:
1743:
1723:
1703:
1679:
1659:
1574:
1554:
1528:
1508:
1423:
1377:
1351:
1327:
1303:
1272:
1248:
1188:
1162:
1101:
1091:maps the universe
1081:
1008:
978:
936:
895:
860:
833:
813:
786:
763:
739:
717:
694:
644:
602:
567:
547:
509:
489:
463:
443:
423:
376:W. Wesley Peterson
335:wrote an internal
309:associative arrays
215:abstract data type
195:
6832:1953 in computing
6814:
6813:
6616:Hashed array tree
6515:Associative array
6363:978-0-471-73884-8
5862:on March 26, 2022
5695:978-0-19-809930-7
5434:978-0-315-29700-5
5397:978-3-540-87778-3
5353:978-3-540-42493-2
5303:978-0-19-504182-8
5238:Rivest, Ronald L.
5230:Cormen, Thomas H.
5210:978-3-540-42493-2
5161:978-0-13-199746-2
5121:978-1-920682-72-9
5089:978-3-540-29740-6
4988:978-3-540-29740-6
4913:978-0-201-89685-5
4743:978-0-262-53196-2
4720:Rivest, Ronald L.
4712:Cormen, Thomas H.
4473:978-0-429-14701-2
4415:978-0-470-34473-6
4368:Sedgewick, Robert
4344:978-0-262-53196-2
4321:Rivest, Ronald L.
4313:Cormen, Thomas H.
4298:978-0-201-89685-5
4235:978-3-540-77977-3
4188:978-0-262-03384-8
4169:Rivest, Ronald L.
4161:Cormen, Thomas H.
3884:Cache (computing)
3854:Database indexing
3842:Associative array
3745:
3739:
3717:
3648:
3642:
3627:
3621:
3573:{\displaystyle n}
3553:{\displaystyle K}
3450:
3380:
3324:
3112:
3085:
3056:real-time systems
2900:{\displaystyle T}
2871:{\displaystyle x}
2851:{\displaystyle j}
2831:{\displaystyle x}
2783:
2777:
2715:
2709:
2674:{\displaystyle j}
2654:{\displaystyle T}
2634:{\displaystyle x}
2582:{\displaystyle x}
2471:{\displaystyle k}
2452:relative distance
2416:Hopscotch hashing
2411:Hopscotch hashing
2405:Hopscotch hashing
2344:Coalesced hashing
2339:Coalesced hashing
2333:Coalesced hashing
2252:Quadratic probing
2175:found to be more
2094:{\displaystyle k}
1897:{\displaystyle x}
1877:{\displaystyle T}
1835:Separate chaining
1746:{\displaystyle A}
1726:{\displaystyle m}
1706:{\displaystyle m}
1682:{\displaystyle A}
1577:{\displaystyle m}
1531:{\displaystyle M}
1492:
1486:
1447:universal hashing
1354:{\displaystyle S}
1330:{\displaystyle S}
1306:{\displaystyle h}
1275:{\displaystyle u}
1104:{\displaystyle U}
742:{\displaystyle m}
720:{\displaystyle n}
689:
668:
664:
570:{\displaystyle h}
550:{\displaystyle A}
512:{\displaystyle x}
466:{\displaystyle n}
446:{\displaystyle m}
426:{\displaystyle A}
403:associative array
313:database indexing
211:associative array
187:
186:
183:
182:
69:associative array
18:Separate chaining
16:(Redirected from
6839:
6639:Association list
6471:
6464:
6457:
6448:
6447:
6406:
6396:
6367:
6351:
6331:
6330:
6319:
6313:
6312:
6310:
6308:
6293:
6287:
6286:
6284:
6282:
6268:
6262:
6261:
6259:
6257:
6242:
6236:
6235:
6233:
6231:
6211:
6205:
6204:
6194:
6160:
6154:
6153:
6151:
6149:
6130:
6124:
6123:
6121:
6119:
6105:
6099:
6098:
6096:
6094:
6088:
6077:
6069:
6063:
6062:
6060:
6058:
6043:
6037:
6036:
6034:
6032:
6018:
6012:
6011:
6009:
6007:
5988:
5982:
5981:
5975:
5967:
5965:
5963:
5953:
5944:
5938:
5937:
5935:
5933:
5913:
5907:
5906:
5878:
5872:
5871:
5869:
5867:
5858:. Archived from
5847:
5841:
5840:
5838:
5836:
5830:
5815:
5806:
5797:
5796:
5794:
5792:
5786:
5771:
5762:
5756:
5755:
5749:
5747:
5741:
5733:10.7936/K7WD3XXV
5718:
5709:
5700:
5699:
5681:
5675:
5674:
5668:
5666:
5660:
5649:
5640:
5634:
5633:
5631:
5629:
5624:. pp. 15–16
5619:
5610:
5604:
5603:
5601:
5599:
5593:
5582:
5571:
5565:
5564:
5562:
5560:
5554:
5543:
5534:
5528:
5527:
5525:
5523:
5503:
5497:
5496:
5468:
5462:
5461:
5459:
5457:
5451:
5422:
5411:
5402:
5401:
5375:
5358:
5357:
5337:
5318:
5312:
5311:
5291:
5281:
5270:
5268:
5250:(2nd ed.),
5226:
5215:
5214:
5194:
5175:
5166:
5165:
5147:
5141:
5140:
5138:
5136:
5130:
5124:. Archived from
5109:
5100:
5094:
5093:
5067:
5061:
5060:
5045:The VLDB Journal
5040:
5034:
5032:
5015:(3): 1030–1049.
4999:
4993:
4992:
4966:
4955:
4954:
4952:
4950:
4944:
4933:
4924:
4918:
4917:
4894:
4883:
4882:
4880:
4856:
4850:
4849:
4847:
4845:
4836:. Archived from
4829:
4820:
4819:
4788:
4782:
4781:
4772:(302): 157–175.
4754:
4748:
4747:
4732:(2nd ed.).
4708:
4699:
4698:
4680:
4662:
4653:
4647:
4646:
4612:
4603:
4602:
4582:
4573:
4572:
4544:
4538:
4531:
4522:
4521:
4519:
4517:
4497:
4478:
4477:
4451:
4420:
4419:
4393:
4382:
4381:
4364:
4349:
4348:
4309:
4303:
4302:
4277:
4266:
4265:
4246:
4240:
4239:
4215:
4199:
4193:
4192:
4157:
4062:
4058:
4047:
4043:
4033:
4019:
4006:
4002:
3998:
3994:
3980:
3966:
3954:
3938:standard library
3864:database indices
3807:
3805:
3804:
3799:
3774:
3772:
3771:
3766:
3761:
3760:
3743:
3737:
3733:
3732:
3715:
3711:
3710:
3698:
3697:
3681:
3679:
3678:
3673:
3661:
3659:
3658:
3653:
3646:
3640:
3625:
3619:
3608:
3606:
3605:
3600:
3579:
3577:
3576:
3571:
3559:
3557:
3556:
3551:
3539:
3537:
3536:
3531:
3482:
3480:
3479:
3474:
3466:
3452:
3451:
3448:
3439:
3412:
3410:
3409:
3404:
3396:
3382:
3381:
3378:
3369:
3338:
3336:
3335:
3330:
3325:
3322:
3317:
3303:
3276:
3274:
3273:
3268:
3263:
3249:
3222:
3220:
3219:
3214:
3209:
3195:
3177:
3175:
3174:
3169:
3164:
3150:
3124:
3122:
3121:
3116:
3114:
3113:
3110:
3097:
3095:
3094:
3089:
3087:
3086:
3083:
3027:modulo operation
3020:
3018:
3017:
3012:
2988:Dynamic resizing
2982:
2980:
2979:
2974:
2972:
2957:
2955:
2954:
2949:
2931:
2929:
2928:
2923:
2921:
2906:
2904:
2903:
2898:
2877:
2875:
2874:
2869:
2857:
2855:
2854:
2849:
2838:into the bucket
2837:
2835:
2834:
2829:
2817:
2815:
2814:
2809:
2781:
2775:
2749:
2747:
2746:
2741:
2713:
2707:
2680:
2678:
2677:
2672:
2660:
2658:
2657:
2652:
2640:
2638:
2637:
2632:
2620:
2618:
2617:
2612:
2588:
2586:
2585:
2580:
2524:
2522:
2521:
2516:
2500:
2498:
2497:
2492:
2477:
2475:
2474:
2469:
2458:-1 entries. Let
2395:
2393:
2392:
2387:
2283:
2281:
2280:
2275:
2164:inefficiencies.
2154:spatial locality
2131:
2129:
2128:
2123:
2121:
2120:
2100:
2098:
2097:
2092:
2080:
2078:
2077:
2072:
2044:
2042:
2041:
2036:
2031:
1992:If the keys are
1903:
1901:
1900:
1895:
1883:
1881:
1880:
1875:
1819:2-choice hashing
1752:
1750:
1749:
1744:
1732:
1730:
1729:
1724:
1712:
1710:
1709:
1704:
1688:
1686:
1685:
1680:
1668:
1666:
1665:
1660:
1655:
1654:
1648:
1647:
1626:
1625:
1583:
1581:
1580:
1575:
1563:
1561:
1560:
1555:
1537:
1535:
1534:
1529:
1517:
1515:
1514:
1509:
1504:
1503:
1490:
1484:
1432:
1430:
1429:
1424:
1422:
1386:
1384:
1383:
1378:
1360:
1358:
1357:
1352:
1336:
1334:
1333:
1328:
1317:for a given set
1312:
1310:
1309:
1304:
1293:A hash function
1281:
1279:
1278:
1273:
1257:
1255:
1254:
1249:
1197:
1195:
1194:
1189:
1171:
1169:
1168:
1163:
1161:
1110:
1108:
1107:
1102:
1090:
1088:
1087:
1082:
1017:
1015:
1014:
1009:
1007:
1006:
987:
985:
984:
979:
945:
943:
942:
937:
935:
934:
904:
902:
901:
896:
891:
886:
885:
869:
867:
866:
861:
859:
858:
842:
840:
839:
834:
822:
820:
819:
814:
812:
811:
795:
793:
792:
787:
772:
770:
769:
764:
748:
746:
745:
740:
726:
724:
723:
718:
703:
701:
700:
695:
690:
682:
666:
665:
662:
653:
651:
650:
645:
611:
609:
608:
603:
576:
574:
573:
568:
556:
554:
553:
548:
518:
516:
515:
510:
498:
496:
495:
490:
473:elements, where
472:
470:
469:
464:
452:
450:
449:
444:
432:
430:
429:
424:
349:Elaine M. McGraw
233:, also called a
159:Space complexity
84:
83:
54:
53:
21:
6847:
6846:
6842:
6841:
6840:
6838:
6837:
6836:
6817:
6816:
6815:
6810:
6797:
6769:
6663:
6659:XOR linked list
6625:
6601:Circular buffer
6582:
6501:
6480:
6478:Data structures
6475:
6413:
6364:
6340:
6338:Further reading
6335:
6334:
6321:
6320:
6316:
6306:
6304:
6294:
6290:
6280:
6278:
6270:
6269:
6265:
6255:
6253:
6244:
6243:
6239:
6229:
6227:
6212:
6208:
6161:
6157:
6147:
6145:
6138:docs.oracle.com
6132:
6131:
6127:
6117:
6115:
6107:
6106:
6102:
6092:
6090:
6086:
6075:
6071:
6070:
6066:
6056:
6054:
6053:. June 20, 2023
6045:
6044:
6040:
6030:
6028:
6020:
6019:
6015:
6005:
6003:
5990:
5989:
5985:
5969:
5968:
5961:
5959:
5951:
5945:
5941:
5931:
5929:
5914:
5910:
5879:
5875:
5865:
5863:
5848:
5844:
5834:
5832:
5828:
5813:
5807:
5800:
5790:
5788:
5784:
5769:
5763:
5759:
5745:
5743:
5739:
5716:
5710:
5703:
5696:
5682:
5678:
5664:
5662:
5658:
5647:
5641:
5637:
5627:
5625:
5617:
5611:
5607:
5597:
5595:
5591:
5580:
5572:
5568:
5558:
5556:
5552:
5541:
5535:
5531:
5521:
5519:
5504:
5500:
5469:
5465:
5455:
5453:
5449:
5435:
5420:
5412:
5405:
5398:
5376:
5361:
5354:
5319:
5315:
5304:
5282:
5273:
5266:
5242:Stein, Clifford
5227:
5218:
5211:
5176:
5169:
5162:
5148:
5144:
5134:
5132:
5128:
5122:
5107:
5101:
5097:
5090:
5068:
5064:
5041:
5037:
5003:Willard, Dan E.
5000:
4996:
4989:
4967:
4958:
4948:
4946:
4942:
4931:
4925:
4921:
4914:
4898:Donald E. Knuth
4895:
4886:
4857:
4853:
4843:
4841:
4830:
4823:
4808:10.2307/1402731
4792:Plackett, Robin
4789:
4785:
4755:
4751:
4744:
4724:Stein, Clifford
4709:
4702:
4660:
4654:
4650:
4635:
4613:
4606:
4583:
4576:
4545:
4541:
4532:
4525:
4515:
4513:
4498:
4481:
4474:
4452:
4423:
4416:
4394:
4385:
4365:
4352:
4345:
4325:Stein, Clifford
4310:
4306:
4299:
4287:. Vol. 3:
4278:
4269:
4247:
4243:
4236:
4213:
4200:
4196:
4189:
4173:Stein, Clifford
4158:
4151:
4146:
4141:
4112:Pearson hashing
4077:
4060:
4056:
4045:
4041:
4031:
4017:
4004:
4000:
3996:
3992:
3978:
3969:arbitrary types
3962:
3952:
3934:
3932:Implementations
3922:
3916:
3904:
3898:
3886:
3880:
3856:
3844:
3838:
3833:
3784:
3781:
3780:
3756:
3752:
3728:
3724:
3706:
3702:
3693:
3689:
3687:
3684:
3683:
3667:
3664:
3663:
3614:
3611:
3610:
3585:
3582:
3581:
3565:
3562:
3561:
3545:
3542:
3541:
3525:
3522:
3521:
3514:
3503:
3497:
3456:
3447:
3443:
3423:
3421:
3418:
3417:
3386:
3377:
3373:
3353:
3351:
3348:
3347:
3321:
3307:
3284:
3282:
3279:
3278:
3253:
3230:
3228:
3225:
3224:
3199:
3185:
3183:
3180:
3179:
3154:
3140:
3138:
3135:
3134:
3131:command pattern
3109:
3105:
3103:
3100:
3099:
3082:
3078:
3076:
3073:
3072:
3064:heap compaction
3052:
3039:
2997:
2994:
2993:
2990:
2965:
2963:
2960:
2959:
2937:
2934:
2933:
2914:
2912:
2909:
2908:
2883:
2880:
2879:
2863:
2860:
2859:
2843:
2840:
2839:
2823:
2820:
2819:
2758:
2755:
2754:
2690:
2687:
2686:
2666:
2663:
2662:
2646:
2643:
2642:
2626:
2623:
2622:
2594:
2591:
2590:
2574:
2571:
2570:
2547:
2507:
2504:
2503:
2483:
2480:
2479:
2463:
2460:
2459:
2413:
2407:
2372:
2369:
2368:
2362:
2356:
2341:
2335:
2330:
2310:
2269:
2266:
2265:
2228:Open addressing
2203:
2201:Open addressing
2197:
2195:Open addressing
2150:cache-conscious
2146:
2116:
2112:
2110:
2107:
2106:
2086:
2083:
2082:
2057:
2054:
2053:
2027:
2013:
2010:
2009:
1998:self-organizing
1990:
1970:
1889:
1886:
1885:
1869:
1866:
1865:
1837:
1821:
1815:
1794:open addressing
1767:
1738:
1735:
1734:
1718:
1715:
1714:
1698:
1695:
1694:
1674:
1671:
1670:
1650:
1649:
1643:
1639:
1621:
1620:
1597:
1594:
1593:
1590:
1569:
1566:
1565:
1543:
1540:
1539:
1523:
1520:
1519:
1501:
1497:
1470:
1467:
1466:
1463:
1439:
1394:
1392:
1389:
1388:
1366:
1363:
1362:
1346:
1343:
1342:
1322:
1319:
1318:
1298:
1295:
1294:
1267:
1264:
1263:
1207:
1204:
1203:
1177:
1174:
1173:
1133:
1116:
1113:
1112:
1096:
1093:
1092:
1034:
1031:
1030:
1024:
1002:
998:
996:
993:
992:
973:
970:
969:
952:
930:
926:
924:
921:
920:
911:
887:
881:
877:
875:
872:
871:
854:
850:
848:
845:
844:
828:
825:
824:
807:
803:
801:
798:
797:
781:
778:
777:
758:
755:
754:
734:
731:
730:
712:
709:
708:
681:
661:
659:
656:
655:
639:
636:
635:
629:
614:time complexity
582:
579:
578:
562:
559:
558:
524:
521:
520:
504:
501:
500:
478:
475:
474:
458:
455:
454:
438:
435:
434:
418:
415:
414:
399:
341:open addressing
333:Hans Peter Luhn
329:
266:key–value pairs
258:Hash collisions
88:Time complexity
50:
39:
28:
23:
22:
15:
12:
11:
5:
6845:
6835:
6834:
6829:
6812:
6811:
6809:
6808:
6802:
6799:
6798:
6796:
6795:
6790:
6785:
6779:
6777:
6771:
6770:
6768:
6767:
6766:
6765:
6755:
6754:
6753:
6751:Hilbert R-tree
6748:
6743:
6733:
6732:
6731:
6729:Fibonacci heap
6726:
6721:
6711:
6710:
6709:
6704:
6699:
6697:Red–black tree
6694:
6689:
6679:
6673:
6671:
6665:
6664:
6662:
6661:
6656:
6651:
6646:
6641:
6635:
6633:
6627:
6626:
6624:
6623:
6618:
6613:
6608:
6603:
6598:
6592:
6590:
6584:
6583:
6581:
6580:
6579:
6578:
6573:
6563:
6562:
6561:
6554:Priority queue
6551:
6550:
6549:
6539:
6534:
6529:
6528:
6527:
6522:
6511:
6509:
6503:
6502:
6500:
6499:
6494:
6488:
6486:
6482:
6481:
6474:
6473:
6466:
6459:
6451:
6445:
6444:
6438:
6432:
6423:
6412:
6411:External links
6409:
6408:
6407:
6379:(2): 209–224.
6368:
6362:
6339:
6336:
6333:
6332:
6314:
6288:
6263:
6237:
6206:
6155:
6125:
6100:
6064:
6038:
6013:
5983:
5939:
5908:
5889:(2): 232–238.
5873:
5842:
5798:
5757:
5701:
5694:
5676:
5635:
5605:
5566:
5529:
5498:
5479:(4): 600–617.
5463:
5433:
5403:
5396:
5359:
5352:
5335:10.1.1.25.4189
5313:
5302:
5271:
5264:
5216:
5209:
5192:10.1.1.25.4189
5167:
5160:
5142:
5120:
5095:
5088:
5062:
5051:(5): 633–660.
5035:
4994:
4987:
4956:
4919:
4912:
4884:
4871:(3): 265–279.
4851:
4821:
4783:
4749:
4742:
4700:
4678:10.1.1.568.130
4648:
4633:
4604:
4593:(2): 109–112.
4574:
4539:
4523:
4479:
4472:
4421:
4414:
4383:
4350:
4343:
4304:
4297:
4267:
4241:
4234:
4207:Sanders, Peter
4203:Mehlhorn, Kurt
4194:
4187:
4148:
4147:
4145:
4142:
4140:
4139:
4134:
4132:Stable hashing
4129:
4124:
4119:
4114:
4109:
4104:
4099:
4094:
4089:
4084:
4078:
4076:
4073:
3933:
3930:
3918:Main article:
3915:
3912:
3900:Main article:
3897:
3894:
3882:Main article:
3879:
3876:
3855:
3852:
3840:Main article:
3837:
3834:
3832:
3829:
3797:
3794:
3791:
3788:
3764:
3759:
3755:
3751:
3748:
3742:
3736:
3731:
3727:
3723:
3720:
3714:
3709:
3705:
3701:
3696:
3692:
3671:
3651:
3645:
3639:
3636:
3633:
3630:
3624:
3618:
3598:
3595:
3592:
3589:
3569:
3549:
3529:
3513:
3510:
3506:Linear hashing
3501:Linear hashing
3499:Main article:
3496:
3495:Linear hashing
3493:
3492:
3491:
3490:gets executed.
3484:
3472:
3469:
3465:
3462:
3459:
3455:
3446:
3442:
3438:
3435:
3432:
3429:
3426:
3414:
3402:
3399:
3395:
3392:
3389:
3385:
3376:
3372:
3368:
3365:
3362:
3359:
3356:
3328:
3320:
3316:
3313:
3310:
3306:
3302:
3299:
3296:
3293:
3290:
3287:
3266:
3262:
3259:
3256:
3252:
3248:
3245:
3242:
3239:
3236:
3233:
3212:
3208:
3205:
3202:
3198:
3194:
3191:
3188:
3167:
3163:
3160:
3157:
3153:
3149:
3146:
3143:
3108:
3081:
3062:that triggers
3051:
3048:
3038:
3035:
3010:
3007:
3004:
3001:
2989:
2986:
2985:
2984:
2971:
2968:
2947:
2944:
2941:
2920:
2917:
2896:
2893:
2890:
2887:
2867:
2847:
2827:
2807:
2804:
2801:
2798:
2795:
2792:
2789:
2786:
2780:
2774:
2771:
2768:
2765:
2762:
2751:
2739:
2736:
2733:
2730:
2727:
2724:
2721:
2718:
2712:
2706:
2703:
2700:
2697:
2694:
2670:
2650:
2630:
2610:
2607:
2604:
2601:
2598:
2578:
2546:
2543:
2531:neighbourhood,
2514:
2511:
2490:
2487:
2467:
2424:linear probing
2420:cuckoo hashing
2409:Main article:
2406:
2403:
2385:
2382:
2379:
2376:
2365:Cuckoo hashing
2360:Cuckoo hashing
2358:Main article:
2355:
2354:Cuckoo hashing
2352:
2337:Main article:
2334:
2331:
2329:
2326:
2322:memory latency
2309:
2306:
2273:
2262:
2261:
2258:Double hashing
2255:
2249:
2246:Linear probing
2236:probe sequence
2199:Main article:
2196:
2193:
2177:cache-friendly
2145:
2142:
2119:
2115:
2090:
2070:
2067:
2064:
2061:
2034:
2030:
2026:
2023:
2020:
2017:
1989:
1986:
1944:in linked list
1906:
1893:
1873:
1861:key–value pair
1836:
1833:
1814:
1811:
1766:
1763:
1742:
1722:
1702:
1678:
1658:
1653:
1646:
1642:
1638:
1635:
1632:
1629:
1624:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1589:
1586:
1573:
1553:
1550:
1547:
1527:
1507:
1500:
1495:
1489:
1483:
1480:
1477:
1474:
1462:
1459:
1438:
1435:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1376:
1373:
1370:
1350:
1326:
1313:is said to be
1302:
1271:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1187:
1184:
1181:
1160:
1157:
1154:
1151:
1148:
1145:
1142:
1139:
1136:
1132:
1129:
1126:
1123:
1120:
1100:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1023:
1020:
1005:
1001:
988:approaches 1.
977:
964:be resized or
951:
948:
933:
929:
910:
907:
894:
890:
884:
880:
857:
853:
832:
810:
806:
785:
762:
751:
750:
738:
728:
716:
693:
688:
685:
680:
677:
674:
671:
643:
628:
625:
601:
598:
595:
592:
589:
586:
566:
546:
543:
540:
537:
534:
531:
528:
508:
488:
485:
482:
462:
442:
422:
398:
395:
328:
325:
229:to compute an
207:data structure
185:
184:
181:
180:
173:
166:
162:
161:
155:
154:
147:
144:
140:
139:
132:
129:
125:
124:
117:
114:
110:
109:
104:
99:
95:
94:
92:big O notation
80:
79:
76:
72:
71:
65:
59:
58:
26:
9:
6:
4:
3:
2:
6844:
6833:
6830:
6828:
6825:
6824:
6822:
6807:
6804:
6803:
6800:
6794:
6791:
6789:
6786:
6784:
6781:
6780:
6778:
6776:
6772:
6764:
6761:
6760:
6759:
6756:
6752:
6749:
6747:
6744:
6742:
6739:
6738:
6737:
6734:
6730:
6727:
6725:
6724:Binomial heap
6722:
6720:
6717:
6716:
6715:
6712:
6708:
6705:
6703:
6700:
6698:
6695:
6693:
6690:
6688:
6685:
6684:
6683:
6680:
6678:
6675:
6674:
6672:
6670:
6666:
6660:
6657:
6655:
6652:
6650:
6647:
6645:
6642:
6640:
6637:
6636:
6634:
6632:
6628:
6622:
6621:Sparse matrix
6619:
6617:
6614:
6612:
6609:
6607:
6606:Dynamic array
6604:
6602:
6599:
6597:
6594:
6593:
6591:
6589:
6585:
6577:
6574:
6572:
6569:
6568:
6567:
6564:
6560:
6557:
6556:
6555:
6552:
6548:
6545:
6544:
6543:
6540:
6538:
6535:
6533:
6530:
6526:
6523:
6521:
6518:
6517:
6516:
6513:
6512:
6510:
6508:
6504:
6498:
6495:
6493:
6490:
6489:
6487:
6483:
6479:
6472:
6467:
6465:
6460:
6458:
6453:
6452:
6449:
6442:
6439:
6436:
6433:
6431:
6427:
6424:
6422:
6418:
6415:
6414:
6404:
6400:
6395:
6390:
6386:
6382:
6378:
6374:
6369:
6365:
6359:
6355:
6350:
6349:
6342:
6341:
6328:
6327:Dot Net Perls
6324:
6318:
6303:
6299:
6292:
6277:
6273:
6267:
6251:
6247:
6241:
6225:
6221:
6217:
6210:
6202:
6198:
6193:
6188:
6184:
6180:
6176:
6172:
6171:
6166:
6159:
6143:
6139:
6135:
6129:
6114:
6110:
6104:
6085:
6081:
6074:
6068:
6052:
6048:
6042:
6027:
6023:
6017:
6001:
5997:
5993:
5987:
5979:
5973:
5957:
5950:
5943:
5927:
5923:
5922:Linux Journal
5919:
5912:
5904:
5900:
5896:
5892:
5888:
5884:
5877:
5861:
5857:
5853:
5846:
5827:
5823:
5819:
5812:
5805:
5803:
5783:
5779:
5775:
5768:
5761:
5753:
5738:
5734:
5730:
5726:
5722:
5715:
5708:
5706:
5697:
5691:
5687:
5680:
5672:
5657:
5653:
5646:
5639:
5623:
5616:
5609:
5590:
5586:
5579:
5578:
5570:
5551:
5547:
5540:
5533:
5517:
5513:
5509:
5502:
5494:
5490:
5486:
5482:
5478:
5474:
5467:
5448:
5444:
5440:
5436:
5430:
5426:
5419:
5418:
5410:
5408:
5399:
5393:
5389:
5385:
5381:
5374:
5372:
5370:
5368:
5366:
5364:
5355:
5349:
5345:
5341:
5336:
5331:
5327:
5323:
5317:
5309:
5305:
5299:
5295:
5290:
5289:
5280:
5278:
5276:
5267:
5265:0-262-03293-7
5261:
5257:
5253:
5249:
5248:
5243:
5239:
5235:
5231:
5225:
5223:
5221:
5212:
5206:
5202:
5198:
5193:
5188:
5184:
5180:
5174:
5172:
5163:
5157:
5153:
5146:
5127:
5123:
5117:
5113:
5106:
5099:
5091:
5085:
5081:
5077:
5073:
5066:
5058:
5054:
5050:
5046:
5039:
5030:
5026:
5022:
5018:
5014:
5010:
5009:
5004:
4998:
4990:
4984:
4980:
4976:
4972:
4965:
4963:
4961:
4941:
4937:
4930:
4923:
4915:
4909:
4905:
4904:
4899:
4893:
4891:
4889:
4879:
4874:
4870:
4866:
4862:
4855:
4839:
4835:
4828:
4826:
4817:
4813:
4809:
4805:
4801:
4797:
4793:
4787:
4779:
4775:
4771:
4767:
4763:
4759:
4758:Pearson, Karl
4753:
4745:
4739:
4735:
4731:
4730:
4725:
4721:
4717:
4713:
4707:
4705:
4696:
4692:
4688:
4684:
4679:
4674:
4670:
4666:
4659:
4652:
4644:
4640:
4636:
4634:1-4244-0505-X
4630:
4626:
4622:
4618:
4611:
4609:
4600:
4596:
4592:
4588:
4581:
4579:
4570:
4566:
4562:
4558:
4554:
4550:
4543:
4536:
4530:
4528:
4511:
4507:
4503:
4496:
4494:
4492:
4490:
4488:
4486:
4484:
4475:
4469:
4465:
4461:
4457:
4450:
4448:
4446:
4444:
4442:
4440:
4438:
4436:
4434:
4432:
4430:
4428:
4426:
4417:
4411:
4407:
4403:
4399:
4392:
4390:
4388:
4379:
4375:
4374:
4369:
4363:
4361:
4359:
4357:
4355:
4346:
4340:
4336:
4332:
4331:
4326:
4322:
4318:
4314:
4308:
4300:
4294:
4290:
4286:
4282:
4281:Knuth, Donald
4276:
4274:
4272:
4263:
4259:
4255:
4252:(Fall 2005).
4251:
4245:
4237:
4231:
4227:
4223:
4219:
4212:
4208:
4204:
4198:
4190:
4184:
4180:
4179:
4174:
4170:
4166:
4162:
4156:
4154:
4149:
4138:
4135:
4133:
4130:
4128:
4125:
4123:
4120:
4118:
4115:
4113:
4110:
4108:
4107:Lazy deletion
4105:
4103:
4100:
4098:
4095:
4093:
4090:
4088:
4085:
4083:
4080:
4079:
4072:
4070:
4066:
4054:
4049:
4039:
4035:
4029:
4025:
4023:
4015:
4011:
4010:collections.
4009:
4005:LinkedHashMap
4001:LinkedHashSet
3990:
3986:
3984:
3976:
3972:
3970:
3965:
3964:unordered_map
3960:
3956:
3950:
3946:
3941:
3939:
3929:
3927:
3921:
3911:
3909:
3903:
3893:
3891:
3885:
3875:
3873:
3869:
3865:
3861:
3851:
3849:
3843:
3828:
3826:
3823:
3822:case-specific
3819:
3815:
3811:
3792:
3786:
3778:
3757:
3753:
3746:
3740:
3729:
3725:
3718:
3712:
3707:
3703:
3699:
3694:
3690:
3669:
3649:
3634:
3628:
3622:
3616:
3593:
3587:
3567:
3547:
3527:
3519:
3509:
3507:
3502:
3489:
3485:
3444:
3415:
3374:
3345:
3344:
3343:
3341:
3318:
3132:
3128:
3106:
3079:
3069:
3068:memory blocks
3065:
3061:
3057:
3047:
3044:
3034:
3032:
3028:
3024:
3005:
2999:
2969:
2966:
2945:
2942:
2939:
2918:
2915:
2891:
2885:
2865:
2845:
2825:
2805:
2802:
2799:
2796:
2790:
2784:
2778:
2772:
2769:
2766:
2763:
2760:
2752:
2737:
2734:
2731:
2728:
2722:
2716:
2710:
2704:
2701:
2698:
2695:
2692:
2684:
2683:
2682:
2668:
2648:
2628:
2608:
2605:
2602:
2599:
2596:
2576:
2568:
2564:
2560:
2556:
2552:
2542:
2540:
2536:
2532:
2528:
2512:
2509:
2488:
2485:
2465:
2457:
2453:
2449:
2445:
2440:
2438:
2434:
2429:
2428:neighbourhood
2425:
2421:
2417:
2412:
2402:
2400:
2399:infinite loop
2380:
2374:
2366:
2361:
2351:
2349:
2345:
2340:
2325:
2323:
2319:
2315:
2305:
2303:
2299:
2296:the elements
2295:
2291:
2287:
2286:infinite loop
2271:
2259:
2256:
2253:
2250:
2247:
2244:
2243:
2242:
2239:
2237:
2233:
2229:
2222:
2216:
2207:
2202:
2192:
2190:
2186:
2182:
2178:
2174:
2173:dynamic array
2170:
2165:
2163:
2159:
2155:
2151:
2141:
2139:
2134:
2117:
2113:
2104:
2088:
2065:
2059:
2051:
2046:
2028:
2024:
2021:
2015:
2007:
2003:
1999:
1995:
1985:
1983:
1979:
1975:
1969:
1966:
1963:
1960:
1956:
1952:
1948:
1945:
1942:
1939:
1935:
1931:
1927:
1924:
1921:
1918:
1914:
1910:
1905:
1891:
1871:
1862:
1858:
1849:
1841:
1832:
1830:
1826:
1825:hash function
1820:
1810:
1807:
1803:
1801:
1800:
1795:
1790:
1788:
1784:
1778:
1776:
1771:
1762:
1760:
1756:
1740:
1720:
1700:
1692:
1676:
1644:
1633:
1630:
1617:
1611:
1605:
1599:
1585:
1571:
1551:
1548:
1545:
1525:
1505:
1493:
1487:
1478:
1472:
1458:
1456:
1452:
1448:
1444:
1434:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1374:
1371:
1368:
1348:
1340:
1324:
1316:
1300:
1291:
1289:
1285:
1269:
1261:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1212:
1209:
1201:
1185:
1182:
1179:
1158:
1155:
1152:
1149:
1146:
1143:
1140:
1137:
1134:
1130:
1124:
1118:
1098:
1075:
1072:
1069:
1066:
1063:
1060:
1057:
1054:
1051:
1042:
1039:
1036:
1029:
1028:hash function
1022:Hash function
1019:
999:
989:
975:
967:
963:
958:
955:
947:
927:
917:
914:
906:
892:
888:
878:
851:
830:
804:
783:
774:
760:
736:
729:
714:
707:
706:
705:
691:
686:
683:
678:
672:
641:
634:
624:
621:
619:
615:
599:
596:
590:
584:
564:
538:
532:
526:
506:
486:
483:
480:
460:
440:
420:
412:
408:
404:
394:
392:
388:
384:
379:
377:
373:
372:Andrey Ershov
369:
366:
362:
358:
357:Arthur Samuel
354:
350:
346:
342:
338:
334:
324:
322:
318:
314:
310:
306:
302:
299:or any other
298:
293:
291:
290:linear search
287:
286:binary search
282:
278:
273:
271:
267:
261:
259:
255:
250:
248:
244:
240:
236:
232:
228:
227:hash function
224:
220:
216:
212:
208:
204:
200:
191:
178:
174:
171:
167:
163:
160:
156:
152:
148:
145:
141:
137:
133:
130:
126:
122:
118:
115:
111:
108:
105:
103:
100:
96:
93:
89:
85:
81:
77:
73:
70:
66:
64:
60:
55:
52:
48:
45:episode, see
44:
37:
33:
19:
6610:
6576:Disjoint-set
6376:
6372:
6347:
6326:
6317:
6305:. Retrieved
6301:
6296:dotnet-bot.
6291:
6279:. Retrieved
6275:
6266:
6256:December 14,
6254:. Retrieved
6240:
6228:. Retrieved
6219:
6209:
6174:
6168:
6158:
6146:. Retrieved
6137:
6128:
6116:. Retrieved
6112:
6103:
6091:. Retrieved
6084:the original
6067:
6055:. Retrieved
6050:
6041:
6029:. Retrieved
6025:
6016:
6004:. Retrieved
5995:
5986:
5960:. Retrieved
5942:
5930:. Retrieved
5911:
5886:
5882:
5876:
5864:. Retrieved
5860:the original
5845:
5835:December 31,
5833:. Retrieved
5791:November 10,
5789:. Retrieved
5773:
5760:
5750:– via
5744:. Retrieved
5720:
5685:
5679:
5669:– via
5663:. Retrieved
5638:
5626:. Retrieved
5608:
5596:. Retrieved
5576:
5569:
5557:. Retrieved
5532:
5520:. Retrieved
5501:
5476:
5472:
5466:
5454:. Retrieved
5416:
5379:
5325:
5322:Pagh, Rasmus
5316:
5306:– via
5287:
5245:
5182:
5179:Pagh, Rasmus
5151:
5145:
5133:. Retrieved
5126:the original
5111:
5098:
5071:
5065:
5048:
5044:
5038:
5012:
5006:
4997:
4970:
4947:. Retrieved
4935:
4922:
4902:
4868:
4864:
4854:
4842:. Retrieved
4838:the original
4802:(1): 59–72.
4799:
4795:
4786:
4769:
4768:. Series 5.
4765:
4752:
4728:
4664:
4651:
4616:
4590:
4586:
4552:
4548:
4542:
4514:. Retrieved
4455:
4397:
4372:
4329:
4307:
4288:
4284:
4257:
4244:
4217:
4197:
4177:
4082:Bloom filter
4050:
4036:
4030:'s built-in
4026:
4016:'s built-in
4012:
3987:
3977:'s built-in
3973:
3957:
3942:
3935:
3923:
3905:
3887:
3866:(such as in
3857:
3845:
3831:Applications
3776:
3515:
3504:
3487:
3126:
3053:
3040:
3031:memory usage
3022:
2991:
2563:distribution
2550:
2548:
2534:
2530:
2455:
2443:
2441:
2427:
2414:
2363:
2342:
2311:
2290:average cost
2263:
2240:
2235:
2231:
2226:
2166:
2147:
2135:
2047:
1991:
1971:
1967:
1964:
1961:
1958:
1954:
1950:
1946:
1943:
1940:
1937:
1933:
1929:
1925:
1922:
1919:
1916:
1912:
1908:
1854:
1822:
1804:
1797:
1791:
1787:prime number
1783:power of two
1779:
1768:
1759:golden ratio
1755:Donald Knuth
1591:
1464:
1442:
1440:
1292:
1258:, where the
1199:
1025:
990:
965:
961:
959:
956:
953:
918:
915:
912:
775:
752:
632:
630:
622:
400:
387:Arnold Dumey
380:
361:IBM Research
330:
297:search trees
294:
274:
262:
251:
246:
242:
238:
234:
230:
202:
196:
176:
169:
150:
135:
120:
106:
101:
51:
42:
6719:Binary heap
6644:Linked list
6421:hash tables
6307:January 16,
6093:February 8,
5818:Netherlands
5746:November 9,
5665:November 9,
5628:December 4,
5598:November 2,
5559:November 2,
5522:November 1,
5456:November 2,
5308:Archive.org
5256:McGraw-Hill
4929:"Lecture 2"
4555:(1): 5–19.
4516:October 26,
3870:) although
3512:Performance
2907:—let it be
2138:fusion tree
1982:total order
1974:numerically
1857:linked list
1829:array index
663:load factor
633:load factor
627:Load factor
411:unique keys
345:Gene Amdahl
6821:Categories
6707:Splay tree
6611:Hash table
6492:Collection
6394:10092/9691
6220:heroku.com
6118:January 1,
4373:Algorithms
4144:References
4061:Dictionary
3945:JavaScript
3277:through a
2302:clustering
2294:distribute
1817:See also:
1799:clustering
1260:bit length
499:. A value
433:of length
381:The first
217:that maps
203:hash table
107:Worst case
67:Unordered
57:Hash table
43:South Park
6763:Hash tree
6649:Skip list
6596:Bit array
6497:Container
6430:Pat Morin
6419:entry on
6201:215943738
6148:April 27,
5962:March 26,
5932:April 16,
5903:212649328
5866:March 26,
5493:125374363
5330:CiteSeerX
5252:MIT Press
5187:CiteSeerX
4673:CiteSeerX
3961:includes
3940:modules.
3777:collision
3700:≠
3670:σ
3644:%
3617:σ
3528:σ
3043:allocated
2711:≤
2448:bit array
2314:CPU cache
2298:uniformly
2272:α
2187:—such as
2162:CPU cache
2025:
1978:lexically
1657:⌋
1615:⌊
1549:∈
1417:−
1372:∈
1339:injective
1337:if it is
1284:word size
1240:−
1183:∈
1156:−
1131:∈
1073:−
1046:→
1000:α
976:α
928:α
879:α
852:α
831:α
805:α
784:α
761:α
673:α
642:α
484:≥
405:stores a
383:published
368:assembler
270:amortized
235:hash code
199:computing
98:Operation
36:Hash tree
32:Hash list
6692:AVL tree
6571:Multiset
6520:Multimap
6507:Abstract
6403:12854386
6250:Archived
6224:Archived
6177:(1): 3.
6142:Archived
6057:July 15,
6031:July 24,
6000:Archived
5972:cite web
5926:Archived
5826:Archived
5782:Archived
5737:Archived
5656:Archived
5589:Archived
5550:Archived
5516:Archived
5447:Archived
5443:14083698
5135:June 13,
4949:June 30,
4940:Archived
4760:(1900).
4569:17874775
4510:Archived
4283:(1998).
4262:Archived
4209:(2008).
4175:(2009).
4117:PhotoDNA
4075:See also
3814:disperse
3127:cleaning
3023:rehashed
2970:′
2919:′
2559:variance
966:rehashed
843:reaches
557:, where
397:Overview
305:software
247:hash map
75:Invented
6746:R+ tree
6741:R* tree
6687:AA tree
6281:July 1,
6230:July 3,
6179:Bibcode
5029:1740562
4844:May 10,
4816:1402731
4695:2557794
4643:1494710
4057:HashSet
4046:HashSet
4042:HashMap
4008:generic
3997:HashMap
3993:HashSet
3949:coerced
3872:B-trees
3488:command
3483:bucket.
3413:bucket.
3340:wrapper
3323:command
2858:; swap
2567:cluster
2561:of the
2316:due to
2232:probing
2210:Smith".
2152:due to
1994:ordered
1315:perfect
365:IBM 701
327:History
239:buckets
102:Average
6775:Graphs
6736:R-tree
6677:B-tree
6631:Linked
6588:Arrays
6401:
6360:
6356:–418.
6199:
6113:go.dev
6006:May 1,
5901:
5692:
5491:
5441:
5431:
5394:
5350:
5332:
5300:
5262:
5207:
5189:
5158:
5118:
5086:
5027:
4985:
4910:
4814:
4740:
4693:
4675:
4641:
4631:
4567:
4470:
4412:
4341:
4337:–252.
4295:
4232:
4185:
4069:VB.NET
4014:Python
4003:, and
3890:caches
3878:Caches
3744:
3738:
3716:
3647:
3641:
3626:
3620:
3416:Clean
3346:Clean
2782:
2776:
2714:
2708:
1959:delete
1917:insert
1669:Where
1518:Where
1491:
1485:
1453:, and
704:where
667:
355:, and
319:, and
317:caches
281:memory
223:values
143:Delete
128:Insert
113:Search
6669:Trees
6542:Queue
6537:Stack
6485:Types
6399:S2CID
6197:S2CID
6087:(PDF)
6076:(PDF)
5952:(PDF)
5899:S2CID
5829:(PDF)
5814:(PDF)
5785:(PDF)
5770:(PDF)
5740:(PDF)
5717:(PDF)
5659:(PDF)
5648:(PDF)
5618:(PDF)
5592:(PDF)
5581:(PDF)
5553:(PDF)
5542:(PDF)
5489:S2CID
5450:(PDF)
5421:(PDF)
5129:(PDF)
5108:(PDF)
4943:(PDF)
4932:(PDF)
4812:JSTOR
4661:(PDF)
4639:S2CID
4565:S2CID
4214:(PDF)
3959:C++11
2878:with
2533:i.e.
2446:-bit
2105:with
1859:with
1689:is a
1286:of a
301:table
279:. If
268:, at
243:slots
231:index
205:is a
165:Space
6758:Trie
6714:Heap
6532:List
6417:NIST
6358:ISBN
6309:2024
6283:2023
6258:2022
6232:2019
6175:1453
6150:2018
6120:2023
6095:2022
6059:2023
6033:2022
6008:2020
5978:link
5964:2022
5934:2022
5868:2022
5837:2021
5793:2021
5748:2021
5690:ISBN
5667:2021
5630:2023
5600:2021
5561:2021
5524:2021
5458:2021
5439:OCLC
5429:ISBN
5392:ISBN
5348:ISBN
5298:ISBN
5260:ISBN
5254:and
5205:ISBN
5156:ISBN
5137:2010
5116:ISBN
5084:ISBN
4983:ISBN
4951:2008
4908:ISBN
4846:2015
4738:ISBN
4629:ISBN
4518:2021
4468:ISBN
4410:ISBN
4339:ISBN
4293:ISBN
4230:ISBN
4183:ISBN
4067:and
4059:and
4053:.NET
4051:The
4038:Rust
4032:Hash
4028:Ruby
4022:type
4018:dict
3989:Java
3983:type
3896:Sets
3860:disk
3580:and
3486:The
3223:and
3098:and
2779:>
2478:and
1957:)
1936:)
1915:)
1884:and
1792:For
1693:and
1564:and
1172:for
962:must
597:<
321:sets
219:keys
201:, a
146:Θ(1)
131:Θ(1)
116:Θ(1)
78:1953
63:Type
6566:Set
6389:hdl
6381:doi
6354:369
6187:doi
5891:doi
5729:doi
5481:doi
5384:doi
5340:doi
5197:doi
5076:doi
5053:doi
5017:doi
4975:doi
4873:doi
4804:doi
4774:doi
4683:doi
4621:doi
4595:doi
4557:doi
4460:doi
4402:doi
4335:221
4222:doi
3979:map
3953:Map
3943:In
3868:dbm
3449:new
3379:old
3111:new
3084:old
2753:If
2685:If
2527:set
2167:In
2048:In
2022:log
1976:or
1641:mod
1499:mod
1341:on
1262:of
1004:max
932:max
883:max
856:max
809:max
407:set
401:An
359:of
337:IBM
288:or
241:or
221:to
197:In
90:in
34:or
6823::
6428:,
6397:.
6387:.
6377:20
6375:.
6325:.
6300:.
6274:.
6248:.
6222:.
6218:.
6195:.
6185:.
6173:.
6167:.
6140:.
6136:.
6111:.
6078:.
6049:.
6024:.
5998:.
5994:.
5974:}}
5970:{{
5954:.
5924:.
5920:.
5897:.
5887:17
5885:.
5854:.
5824:.
5820::
5816:.
5801:^
5776:.
5772:.
5735:.
5727:.
5723:.
5719:.
5704:^
5650:.
5620:.
5544:.
5510:.
5487:.
5477:28
5475:.
5445:.
5437:.
5406:^
5390:.
5362:^
5346:.
5338:.
5296:.
5274:^
5240:;
5236:;
5232:;
5219:^
5203:.
5195:.
5170:^
5110:.
5082:.
5049:19
5047:.
5025:MR
5023:.
5013:29
5011:.
4981:.
4959:^
4938:.
4934:.
4887:^
4869:22
4867:.
4863:.
4824:^
4810:.
4800:51
4798:.
4770:50
4764:.
4736:.
4722:;
4718:;
4714:;
4703:^
4691:MR
4689:.
4681:.
4667:.
4663:.
4637:.
4627:.
4607:^
4591:45
4589:.
4577:^
4563:.
4551:.
4526:^
4504:.
4482:^
4466:.
4458:.
4424:^
4408:.
4400:.
4386:^
4353:^
4323:;
4319:;
4315:;
4270:^
4260:.
4256:.
4228:.
4216:.
4205:;
4171:;
4167:;
4163:;
4152:^
4071:.
4065:C#
4044:,
4024:.
3999:,
3995:,
3985:.
3975:Go
3971:.
3924:A
3850:.
3560:,
3178:,
3033:.
2641:,
2541:.
2422:,
2324:.
1953:,
1932:,
1911:,
1789:.
1761:.
1449:,
1290:.
1026:A
905:.
773:.
631:A
620:.
351:,
347:,
323:.
315:,
311:,
256:.
249:.
175:O(
168:Θ(
149:O(
134:O(
119:O(
6470:e
6463:t
6456:v
6405:.
6391::
6383::
6366:.
6329:.
6311:.
6285:.
6260:.
6234:.
6203:.
6189::
6181::
6152:.
6122:.
6097:.
6061:.
6035:.
6010:.
5980:)
5966:.
5936:.
5905:.
5893::
5870:.
5839:.
5731::
5698:.
5673:.
5632:.
5602:.
5495:.
5483::
5460:.
5400:.
5386::
5356:.
5342::
5310:.
5269:.
5213:.
5199::
5164:.
5139:.
5092:.
5078::
5059:.
5055::
5033:.
5031:.
5019::
4991:.
4977::
4953:.
4916:.
4881:.
4875::
4848:.
4818:.
4806::
4780:.
4776::
4746:.
4697:.
4685::
4645:.
4623::
4601:.
4597::
4571:.
4559::
4553:7
4537:.
4476:.
4462::
4418:.
4404::
4347:.
4301:.
4238:.
4224::
4191:.
3796:)
3793:1
3790:(
3787:O
3763:)
3758:2
3754:K
3750:(
3747:h
3741:=
3735:)
3730:1
3726:K
3722:(
3719:h
3713:,
3708:2
3704:K
3695:1
3691:K
3650:n
3638:)
3635:K
3632:(
3629:h
3623:=
3597:)
3594:x
3591:(
3588:h
3568:n
3548:K
3520:(
3471:]
3468:)
3464:y
3461:e
3458:k
3454:(
3445:h
3441:[
3437:e
3434:l
3431:b
3428:a
3425:T
3401:]
3398:)
3394:y
3391:e
3388:k
3384:(
3375:h
3371:[
3367:e
3364:l
3361:b
3358:a
3355:T
3327:)
3319:,
3315:y
3312:e
3309:k
3305:(
3301:p
3298:u
3295:k
3292:o
3289:o
3286:L
3265:)
3261:y
3258:e
3255:k
3251:(
3247:e
3244:t
3241:e
3238:l
3235:e
3232:D
3211:)
3207:y
3204:e
3201:k
3197:(
3193:t
3190:e
3187:G
3166:)
3162:y
3159:e
3156:k
3152:(
3148:d
3145:d
3142:A
3107:h
3080:h
3009:)
3006:1
3003:(
3000:O
2967:x
2946:1
2943:+
2940:j
2916:x
2895:]
2892:j
2889:[
2886:T
2866:x
2846:j
2826:x
2806:l
2803:s
2800:p
2797:.
2794:]
2791:j
2788:[
2785:T
2773:l
2770:s
2767:p
2764:.
2761:x
2738:l
2735:s
2732:p
2729:.
2726:]
2723:j
2720:[
2717:T
2705:l
2702:s
2699:p
2696:.
2693:x
2669:j
2649:T
2629:x
2609:l
2606:s
2603:p
2600:.
2597:x
2577:x
2535:H
2513:k
2510:B
2489:k
2486:B
2466:k
2456:H
2444:H
2384:)
2381:1
2378:(
2375:O
2156:—
2118:2
2114:k
2089:k
2069:)
2066:1
2063:(
2060:O
2033:)
2029:n
2019:(
2016:O
1968:T
1962:x
1955:k
1951:T
1947:T
1941:k
1934:k
1930:T
1926:T
1920:x
1913:k
1909:T
1892:x
1872:T
1741:A
1721:m
1701:m
1677:A
1652:)
1645:1
1637:)
1634:A
1631:M
1628:(
1623:(
1618:m
1612:=
1609:)
1606:x
1603:(
1600:h
1572:m
1552:S
1546:x
1526:M
1506:m
1494:x
1488:=
1482:)
1479:x
1476:(
1473:h
1420:1
1414:m
1411:,
1408:.
1405:.
1402:.
1399:,
1396:0
1375:S
1369:x
1349:S
1325:S
1301:h
1270:u
1246:}
1243:1
1237:u
1234:,
1231:.
1228:.
1225:.
1222:,
1219:0
1216:{
1213:=
1210:U
1186:U
1180:x
1159:1
1153:m
1150:,
1147:.
1144:.
1141:.
1138:,
1135:0
1128:)
1125:x
1122:(
1119:h
1099:U
1079:}
1076:1
1070:m
1067:,
1064:.
1061:.
1058:.
1055:,
1052:0
1049:{
1043:U
1040::
1037:h
893:4
889:/
737:m
715:n
692:,
687:m
684:n
679:=
676:)
670:(
600:m
594:)
591:x
588:(
585:h
565:h
545:]
542:)
539:x
536:(
533:h
530:[
527:A
507:x
487:n
481:m
461:n
441:m
421:A
179:)
177:n
172:)
170:n
153:)
151:n
138:)
136:n
123:)
121:n
49:.
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
