{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T06:40:11Z","timestamp":1778740811501,"version":"3.51.4"},"reference-count":109,"publisher":"Emerald","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,7,11]]},"abstract":"<jats:p>Many tasks in computer systems could be abstracted as distributing items into buckets, so that the allocation of items across buckets is as balanced as possible, and furthermore, given an item\u2019s identifier it is possible to determine quickly to which bucket it was assigned. A canonical example is a dictionary data structure, where \u2018items\u2019 stands for key-value pairs and \u2018buckets\u2019 for memory locations. Another example is a distributed key-value store, where the buckets represent locations in disk or even whole servers. A third example may be a distributed execution engine where items represent processes and buckets compute devices, and so on. A common technique in this domain is the use of a hash-function that maps an item into a relatively short fixed length string. The hash function is then used in some way to associate the item to its bucket. The use of a hash function is typically the first step in the solution and additional algorithmic ideas are required to deal with collisions and the imbalance of hash values. In this monograph we survey some of these techniques. We focus on multiple choice schemes where items are placed into buckets via the use of several independent hash functions, and typically an item is placed at the least loaded bucket at the time of placement. We analyze the distributions obtained in detail, and show how these ideas could be used to design basic data structures. With respect to data structures we focus on dictionaries, presenting linear probing, cuckoo hashing and many of their variants.<\/jats:p>","DOI":"10.1561\/0400000070","type":"journal-article","created":{"date-parts":[[2017,7,11]],"date-time":"2017-07-11T08:39:21Z","timestamp":1499762361000},"page":"275-379","source":"Crossref","is-referenced-by-count":22,"title":["Hashing, Load Balancing and Multiple Choice"],"prefix":"10.1108","volume":"12","author":[{"given":"Udi","family":"Wieder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2017,7,11]]},"reference":[{"issue":"4","key":"2026040314124240700_ref001","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","article-title":"A fast and simple\n      randomized parallel algorithm for the maximal independent set problem","volume":"7","author":"Alon","year":"1986","journal-title":"J. Algorithms"},{"issue":"5","key":"2026040314124240700_ref002","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1145\/324133.324179","article-title":"Linear hash\n      functions","volume":"46","author":"Alon","year":"1999","journal-title":"J. ACM"},{"issue":"3","key":"2026040314124240700_ref003","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","article-title":"Simple construction\n      of almost k-wise independent random variables","volume":"3","author":"Alon","year":"1992","journal-title":"Random Struct.\n      Algorithms"},{"issue":"1","key":"2026040314124240700_ref004","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/rsa.3240040109","article-title":"Addendum to\n      \u201csimple construction of almost k-wise independent random\n      variables\u201d","volume":"4","author":"Alon","year":"1993","journal-title":"Random Struct. Algorithms"},{"key":"2026040314124240700_ref005","author":"Alon","year":"1992","journal-title":"The Probabilistic\n      Method"},{"key":"2026040314124240700_ref006","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/978-3-642-02927-1_11","volume-title":"Automata, Languages and Programming, 36th International Colloquium","author":"Arbitman","year":"2009"},{"key":"2026040314124240700_ref007","first-page":"787","article-title":"Backyard cuckoo\n      hashing: Constant worst-case operations with a succinct representation","author":"Arbitman","year":"2010"},{"issue":"3","key":"2026040314124240700_ref008","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/s00453-013-9840-x","article-title":"Explicit and\n      efficient hash families suffice for cuckoo hashing with a stash","volume":"70","author":"Aum\u00fcller","year":"2014","journal-title":"Algorithmica"},{"issue":"1","key":"2026040314124240700_ref009","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/S0097539795288490","article-title":"Balanced\n      allocations","volume":"29","author":"Azar","year":"1999","journal-title":"SIAM J. Comput"},{"key":"2026040314124240700_ref010","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.jda.2011.12.006","article-title":"Chains-into-bins\n      processes","volume":"14","author":"Batu","year":"2012","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"2026040314124240700_ref011","doi-asserted-by":"crossref","first-page":"2065","DOI":"10.1016\/j.jpdc.2013.10.008","article-title":"Balls into non-uniform\n      bins","volume":"74","author":"Berenbrink","year":"2014","journal-title":"J. Parallel Distrib. Comput"},{"issue":"6","key":"2026040314124240700_ref012","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1137\/S009753970444435X","article-title":"Balanced\n      allocations: The heavily loaded case","volume":"35","author":"Berenbrink","year":"2006","journal-title":"SIAM J. Comput."},{"issue":"3","key":"2026040314124240700_ref013","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.tcs.2008.09.023","article-title":"On weighted\n      balls-into-bins games","volume":"409","author":"Berenbrink","year":"2008","journal-title":"Theoretical Computer Science"},{"key":"2026040314124240700_ref014","article-title":"Self-stabilizing\n      balls & bins in batches: The power of leaky bins","author":"Berenbrink","year":"2016"},{"key":"2026040314124240700_ref015","first-page":"83","article-title":"bins in batches: The power of leaky bins","volume-title":"In","author":"Berenbrink","year":"2016"},{"key":"2026040314124240700_ref016","first-page":"326","article-title":"Balls-into-bins with\n      nearly optimal load distribution","volume-title":"In","author":"Berenbrink","year":"2013"},{"key":"2026040314124240700_ref017","first-page":"16","article-title":"Balls into bins via local\n      search","volume-title":"In","author":"Bogdan","year":"2013"},{"issue":"5","key":"2026040314124240700_ref018","first-page":"28:1","article-title":"Polylogarithmic\n      independence fools ac0 circuits","volume":"57","author":"Braverman","year":"2008","journal-title":"J. ACM"},{"key":"2026040314124240700_ref019","first-page":"187","volume-title":"31st International\n      Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of Leibniz\n      International Proceedings in Informatics (LIPIcs)","author":"Bringmann","year":"2014"},{"key":"2026040314124240700_ref020","first-page":"43","article-title":"Multilevel adaptive\n      hashing","author":"Broder","year":"1990"},{"key":"2026040314124240700_ref021","first-page":"1454","article-title":"Using multiple\n      hash functions to improve IP lookups","author":"Broder","year":"2001"},{"key":"2026040314124240700_ref022","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/978-3-540-45172-3_7","article-title":"Simple load\n      balancing for distributed hash tables","author":"Byers","year":"2003","journal-title":"Peer-to-Peer Systems II:\n      Second International Workshop"},{"key":"2026040314124240700_ref023","first-page":"469","article-title":"The random graph\n      threshold for -orientiability and a fast algorithm for optimal multiple-choice\n      allocation","author":"Cain","year":"2007"},{"issue":"2","key":"2026040314124240700_ref024","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal classes of\n      hash functions","volume":"18","author":"Lawrence Carter","year":"1979","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314124240700_ref025","unstructured":"Cassandra\n          . Apache. http:\/\/cassandra.apache.org\/."},{"issue":"3","key":"2026040314124240700_ref026","doi-asserted-by":"crossref","first-page":"1030","DOI":"10.1137\/120871626","article-title":"Balls and bins:\n      Smaller hash families and faster evaluation","volume":"42","author":"Elisa Celis","year":"2013","journal-title":"SIAM J. Comput."},{"key":"2026040314124240700_ref027","doi-asserted-by":"crossref","article-title":"Derandomized Balanced\n      Allocation","author":"Chen","DOI":"10.1137\/1.9781611975482.154"},{"key":"2026040314124240700_ref028","first-page":"813","article-title":"From independence to\n      expansion and back again","volume-title":"In","author":"Christiani","year":"2015"},{"key":"2026040314124240700_ref029","first-page":"194","article-title":"Randomized allocation\n      processes","author":"Czumaj","year":"1997"},{"key":"2026040314124240700_ref030","article-title":"Eva Rotenberg, and\n      Mikkel Thorup. Hashing for statistics over k-partitions","author":"Dahlgaard","year":"2015"},{"key":"2026040314124240700_ref031","doi-asserted-by":"crossref","article-title":"The power of two\n      choices with simple tabulation","author":"Dahlgaard","DOI":"10.1137\/1.9781611974331.ch111"},{"issue":"6","key":"2026040314124240700_ref032","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1145\/1323293.1294281","article-title":"Dynamo:\n      Amazon\u2019s highly available key-value store","volume":"41","author":"DeCandia","year":"2007","journal-title":"SIGOPS Oper. Syst.\n      Rev."},{"key":"2026040314124240700_ref033","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0020-0190(02)00500-8","article-title":"Cuckoo hashing: Further\n      analysis","volume":"86","author":"Devroye","year":"2003","journal-title":"Information Processing Letters"},{"key":"2026040314124240700_ref034","doi-asserted-by":"crossref","article-title":"Universal\n      hashing and k-wise independent random variables via integer arithmetic without\n      primes","author":"Dietzfelbinger","DOI":"10.1007\/3-540-60922-9_46"},{"key":"2026040314124240700_ref035","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/3-540-55719-9_77","article-title":"Polynomial hash\n      functions are reliable","volume-title":"Proceedings of the 19th International\n      Colloquium on Automata, Languages and Programming","author":"Dietzfelbinger","year":"1992"},{"key":"2026040314124240700_ref036","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14165-2_19","article-title":"Tight thresholds for\n      cuckoo hashing via XORSAT","author":"Dietzfelbinger","year":"2010"},{"key":"2026040314124240700_ref037","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0032018","article-title":"A new universal class\n      of hash functions and dynamic hashing in real time","author":"Dietzfelbinger","year":"1990"},{"issue":"4","key":"2026040314124240700_ref038","first-page":"738","article-title":"Friedheim Meyer auf\n      der Heide, Hans Rohnr, and Robert Endre Tarjan","volume":"23","author":"Dietzfelbinger","year":"1994","journal-title":"Dynamic perfect\n      hashing: Upper and lower bounds. SIAM J. Comput."},{"key":"2026040314124240700_ref039","first-page":"354","volume-title":"Applications of a splitting\n      trick","author":"Dietzfelbinger","year":"2009"},{"key":"2026040314124240700_ref040","first-page":"795","article-title":"On risks of using\n      cuckoo hashing with simple universal hash classes","volume-title":"Proceedings of\n      the 20th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Dietzfelbinger","year":"2009"},{"issue":"1-2","key":"2026040314124240700_ref041","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","article-title":"Balanced allocation\n      and dictionaries with tightly packed constant size bins","volume":"380","author":"Dietzfelbinger","year":"2007","journal-title":"Theoretical\n      Computer Science"},{"key":"2026040314124240700_ref042","first-page":"629","article-title":"Almost random graphs\n      with simple hash functions","volume-title":"Proceedings of the 35th Annual ACM\n      Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA","author":"Dietzfelbinger","year":"2003"},{"key":"2026040314124240700_ref043","article-title":"A simplified binet\n      formula for k-generalized bonacci numbers","volume":"17","author":"Dresden","year":"2014","journal-title":"Journal of Integer\n      Sequences"},{"issue":"2","key":"2026040314124240700_ref044","first-page":"2012","article-title":"A precise analysis\n      of cuckoo hashing. ACM Trans","volume":"8","author":"Drmota","journal-title":"Algorithms"},{"key":"2026040314124240700_ref045","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure\n      for the Analysis of Randomized Algorithms","author":"Dubhashi","year":"2009","edition":"1st"},{"issue":"5","key":"2026040314124240700_ref046","first-page":"6","article-title":"Indexing for rapid\n      random access memory systems","volume":"12","author":"Dumey","year":"1956","journal-title":"Computers and Automation"},{"key":"2026040314124240700_ref047","first-page":"459","article-title":"The\n      -orientability thresholds for","author":"Fernholz","year":"2007"},{"issue":"2","key":"2026040314124240700_ref048","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","article-title":".\n      &lt;article&gt;Space efficient hash tables with worst case constant access\n      time","volume":"38","author":"Motakis","year":"2005","journal-title":"Theory Comput. Syst"},{"key":"2026040314124240700_ref049","first-page":"23","article-title":"The\n      multiple-orientability thresholds for random hypergraphs","author":"Fountoulakis","year":"2011","journal-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011,\n      San Francisco"},{"issue":"3","key":"2026040314124240700_ref050","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1002\/rsa.20426","article-title":"Sharp load\n      thresholds for cuckoo hashing","volume":"41","author":"Fountoulakis","year":"2012","journal-title":"Random Struct. Algorithms"},{"issue":"6","key":"2026040314124240700_ref051","doi-asserted-by":"crossref","first-page":"2156","DOI":"10.1137\/100797503","article-title":"On the insertion time\n      of cuckoo hashing","volume":"42","author":"Fountoulakis","year":"2013","journal-title":"SIAM J. Comput"},{"issue":"3","key":"2026040314124240700_ref052","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a\n      sparse table with 0(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. ACM"},{"issue":"2","key":"2026040314124240700_ref053","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1137\/090770928","article-title":"An analysis of\n      random-walk cuckoo hashing","volume":"40","author":"Frieze","year":"2011","journal-title":"SIAM J. Comput"},{"key":"2026040314124240700_ref054","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611974782.97","article-title":"On the insertion\n      time of random walk cuckoo hashing","volume-title":"CoRR","author":"Frieze"},{"issue":"3","key":"2026040314124240700_ref055","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1002\/rsa.20427","article-title":"Maximum matchings in\n      random bipartite graphs and the space utilization of cuckoo hash tables","volume":"41","author":"Frieze","year":"2012","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"2026040314124240700_ref056","doi-asserted-by":"crossref","first-page":"774","DOI":"10.1017\/S096354831400073X","article-title":"Orientability\n      thresholds for random hypergraphs","volume":"24","author":"Gao","year":"2015","journal-title":"Combinatorics, Probability &\n      Computing"},{"key":"2026040314124240700_ref057","article-title":"Balls and\n      bins with structure: Balanced allocations on hypergraphs","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Brighten Godfrey"},{"key":"2026040314124240700_ref058","article-title":"More practical and\n      secure history-independent hash tables","author":"Goodrich","year":"2016","journal-title":"European symposium on\n      Research in Computer Security"},{"key":"2026040314124240700_ref059","first-page":"654","article-title":"Consistent hashing and\n      random trees: Distributed caching protocols for relieving hot spots on the world wide\n      web","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of\n      Computing","author":"Karger"},{"key":"2026040314124240700_ref060","volume-title":"Proceedings of the 24th\n      Annual ACM Symposium on Theory of Computing","author":"Karp","year":"1992"},{"key":"2026040314124240700_ref061","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1145\/1109557.1109606","article-title":"Balanced allocation\n      on graphs","author":"Kenthapadi","year":"2006","journal-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium\n      on Discrete Algorithms"},{"key":"2026040314124240700_ref062","first-page":"601","article-title":"Balls into bins made\n      faster","author":"Khosla","year":"2013","journal-title":"Algorithms - ESA"},{"key":"2026040314124240700_ref063","article-title":"Using a queue to\n      deformized cuckoo hashing in hardware","author":"Kirsch","year":"2007"},{"issue":"4","key":"2026040314124240700_ref064","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1137\/080728743","article-title":"More robust hashing:\n      Cuckoo hashing with a stash","volume":"39","author":"Kirsch","year":"2009","journal-title":"SIAM J. Comput."},{"key":"2026040314124240700_ref065","article-title":"Independence of\n      tabulation-based hash classes","author":"Klassen","year":"2012","journal-title":"LATIN 2012: Theoretical Informatics\n      - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings, pages\n      506-517"},{"key":"2026040314124240700_ref066","article-title":"Notes on open\n      addressing","author":"Knuth","year":"1963"},{"issue":"3","key":"2026040314124240700_ref067","first-page":"81","article-title":"A further analysis\n      of cuckoo hashing with a stash and random graphs of excess r","volume":"12","author":"Kutzelnigg","year":"2010","journal-title":"Discrete\n      Mathematics & Theoretical Computer Science"},{"key":"2026040314124240700_ref068","first-page":"671","author":"Lehman","year":"2009"},{"key":"2026040314124240700_ref069","first-page":"251","article-title":"A new approach to the\n      orientation of random hypergraphs","author":"Lelarge","year":"2012","journal-title":"In Proceedings of the 23rd Annual\n      ACM-SIAM Symposium on Discrete Algorithms, SODA 2012"},{"issue":"4-5","key":"2026040314124240700_ref070","doi-asserted-by":"crossref","first-page":"604","DOI":"10.1016\/j.dam.2011.11.009","article-title":"The universality of\n      iterated hashing over variable-length strings","volume":"160","author":"Lemire","year":"2012","journal-title":"Discrete Applied\n      Mathematics"},{"key":"2026040314124240700_ref071","first-page":"11","article-title":"Tight bounds for\n      parallel randomized load balancing: Extended abstract","author":"Lenzen","year":"2011"},{"issue":"3","key":"2026040314124240700_ref072","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s004930200021","article-title":"Improved pseudorandom\n      generators for combinatorial rectangles","volume":"22","author":"Lu","year":"2002","journal-title":"Combinatorica"},{"key":"2026040314124240700_ref073","first-page":"859","article-title":"Fast\n      pseudorandomness for independence and load balancing - (extended abstract)","author":"Meka","year":"2014"},{"key":"2026040314124240700_ref074","first-page":"456","article-title":"Oblivious data\n      structures: Applications to cryptography","author":"Micciancio","year":"1997"},{"key":"2026040314124240700_ref075","unstructured":"Michael\n              Mitzenmacher\n            \n          . The Power of Two\n      Choices in Randomized Load Balancing. PhD thesis, University of California at\n     Berkeley, 1996."},{"key":"2026040314124240700_ref076","first-page":"331","article-title":"Balanced\n      allocations and double hashing","author":"Mitzenmacher","year":"2014"},{"key":"2026040314124240700_ref077","first-page":"255","article-title":"The power of two\n      random choices: A survey of techniques and results","author":"Mitzenmacher","journal-title":"In in\n       Handbook of Randomized Computing, pages"},{"key":"2026040314124240700_ref078","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing:\n      Randomized Algorithms and Probabilistic Analysis. Cambridge University Press","author":"Mitzenmacher","year":"2005"},{"key":"2026040314124240700_ref079","first-page":"746","article-title":"Why simple hash\n      functions work: Exploiting the entropy in a data stream","author":"Mitzenmacher"},{"key":"2026040314124240700_ref080","first-page":"326","article-title":"The\n      asymptotics of selecting the shortest of two, improved","author":"Mitzenmacher","year":"1999","journal-title":"In Proceedings\n      of the 37th Annual Allerton Conference on Communication, Control, and Computing"},{"key":"2026040314124240700_ref081","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized\n      Algorithms","author":"Motwani","year":"1995"},{"issue":"4","key":"2026040314124240700_ref082","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","article-title":"Small-bias probability\n      spaces: Efficient constructions and applications","volume":"22","author":"Naor","year":"1993","journal-title":"SIAM J.\n      Comput"},{"key":"2026040314124240700_ref083","first-page":"631","volume-title":"Automata, Languages and Programming, 35th\n      International Colloquium, ICAIP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part\n      II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and\n      Cryptography Foundations","author":"Naor","year":"2008"},{"key":"2026040314124240700_ref084","first-page":"492","article-title":"Anti-persistence:\n      History independent data structures","author":"Naor","year":"2001"},{"key":"2026040314124240700_ref085","first-page":"50","article-title":"Novel architectures\n      for p2p applications: The continuous-discrete approach","author":"Naor"},{"issue":"1","key":"2026040314124240700_ref086","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","article-title":"Randomness is\n      linear in space","volume":"52","author":"Nisan","year":"1996","journal-title":"J. Comput. Syst. Sci"},{"issue":"1","key":"2026040314124240700_ref087","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1137\/060658400","article-title":"Uniform hashing in\n      constant time and optimal space","volume":"38","author":"Pagh","year":"2008","journal-title":"SIAM J. Comput"},{"issue":"3","key":"2026040314124240700_ref088","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/110827831","article-title":"Linear probing with\n      5-wise independence","volume":"53","author":"Pagh","year":"2011","journal-title":"SIAM Review"},{"issue":"2","key":"2026040314124240700_ref089","first-page":"122","article-title":"Cuckoo\n      hashing","volume":"51","author":"Pagh","year":"2004"},{"key":"2026040314124240700_ref090","first-page":"830","article-title":"Efficient hashing\n      with lookups in two memory accesses","author":"Panigrahy","year":"2005"},{"key":"2026040314124240700_ref091","article-title":"Graphical balanced\n      allocations and the (1 + beta)-choice process","author":"Peres","year":"2014","journal-title":"Random\n      Structures and Algorithms"},{"issue":"2","key":"2026040314124240700_ref092","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for\n      random-access storage","volume":"1","author":"Peterson","year":"1957","journal-title":"IBM J. Res. Dev"},{"issue":"3","key":"2026040314124240700_ref093","first-page":"2012","article-title":"The power of simple\n      tabulation hashing","volume":"59","author":"P\u0103tra\u015fcu","journal-title":"J. ACM"},{"key":"2026040314124240700_ref094","first-page":"209","article-title":"Twisted\n      tabulation hashing","author":"Mihai\n       P\u0103tra\u015fcu and Mikkel Thorup","year":"2013"},{"issue":"1","key":"2026040314124240700_ref095","first-page":"27","article-title":"On the k-independence\n      required by linear probing and minwise independence. ACM\n      Trans","volume":"12","author":"P\u0103tra\u015fcu","year":"2015","journal-title":"Algorithms"},{"key":"2026040314124240700_ref096","first-page":"159","volume-title":"Lecture Notes in Computer Science","author":"Raab","year":"1998"},{"key":"2026040314124240700_ref097","first-page":"943","volume-title":"Automata, Languages, and Programming - 41st\n      International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014,\n      Proceedings","author":"Reingold","year":"2014"},{"key":"2026040314124240700_ref098","author":"Wayne Roberts","year":"1973","edition":"1st"},{"key":"2026040314124240700_ref099","first-page":"849","article-title":"Fast concurrent access\n      to parallel disks","author":"Sanders","year":"2000"},{"issue":"3","key":"2026040314124240700_ref100","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/S0097539701386216","article-title":"On universal classes\n      of extremely random constant-time hash functions","volume":"33","author":"Siegel","year":"2004","journal-title":"SIAM J.\n      Comput"},{"issue":"4","key":"2026040314124240700_ref101","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1145\/964723.383071","article-title":"Chord: A\n      scalable peer-to-peer lookup service for internet applications","volume":"31","author":"Stoica","year":"2001","journal-title":"SIGCOMM Comput. Commun. Rev"},{"key":"2026040314124240700_ref102","first-page":"256","article-title":"Balanced allocations:\n      the weighted case","author":"Talwar","year":"2007","journal-title":"Proceedings of the 39th Annual ACM Symposium on\n      Theory of Computing, San Diego, California"},{"key":"2026040314124240700_ref103","first-page":"979","volume-title":"Automata,\n      Languages, and Programming, volume 8572 of Lecture Notes in Computer Science","author":"Talwar","year":"2014"},{"key":"2026040314124240700_ref104","first-page":"655","article-title":"String hashing for\n      linear probing","author":"Thorup","year":"2009"},{"issue":"2","key":"2026040314124240700_ref105","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/100800774","article-title":"Tabulation-based\n      5-independent hashing with applications to linear probing and second moment\n      estimation","volume":"41","author":"Thorup","year":"2012","journal-title":"SIAM J. Comput"},{"issue":"4","key":"2026040314124240700_ref106","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1145\/792538.792546","article-title":"How asymmetry\n      helps load balancing","volume":"50","author":"V\u00f6cking","year":"2003","journal-title":"J. ACM"},{"issue":"3","key":"2026040314124240700_ref107","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","article-title":"New hash functions and\n      their use in authentication and set equality","volume":"22","author":"Wegman","year":"1981","journal-title":"J. Comput. Syst.\n      Sci"},{"key":"2026040314124240700_ref108","first-page":"188","author":"Wieder","year":"2007"},{"key":"2026040314124240700_ref109","first-page":"424","article-title":"Asymmetric balanced\n      allocation with simple hash functions","author":"Woelfel","year":"2006"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/12\/3-4\/275\/11159624\/0400000070en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/12\/3-4\/275\/11159624\/0400000070en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:17Z","timestamp":1777489277000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/12\/3-4\/275\/1332724\/Hashing-Load-Balancing-and-Multiple-Choice"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,11]]},"references-count":109,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2017,7,11]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000070","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,11]]}}}