Cuckoo hashing: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 21:44, 20 July 2024 edit Raphaaal (talk \| contribs) 3 edits Correct the cycle example. Insert key 45 instead. That also leads to a shorter cycle to describe. Tag: Visual edit: Switched ← Previous edit		Latest revision as of 04:38, 13 August 2025 edit undo Bender the Bot (talk \| contribs) Bots 1,064,377 edits m →External links: HTTP to HTTPS for Blogspot Tag: AWB
(8 intermediate revisions by 6 users not shown)
Line 12: ===Lookup=== Cuckoo hashing uses two hash tables, <math>T_1</math> and <math>T_2</math>. Assuming <math>r</math> is the length of each table, the hash functions for the two tables is defined as, <math>h_1,\ h_2\ :\ ~~\cup~~S \rightarrow \{0, ..., r-1\}</math> and <math>\forall x \in S</math> where <math>x</math> is the key and <math>S</math> is the set whose keys are stored in <math>h_1(x)</math> of <math>T_1</math> or <math>h_2(x)</math> of <math>T_2</math>. The lookup operation is as follows:{{r\|Cuckoo\|p=124}} {\| \|- style="vertical-align:top" Line 272: ==Known users== Cuckoo hashing is used in [[TikTok]]'s recommendation system to solve the problem of "embedding table collisions", which can result in reduced model quality. The TikTok recommendation system "Monolith" takes advantage cuckoo hashing's collision resolution to prevent different concepts from being mapped to the same vectors.<ref>{{~~Cite~~cite ~~web~~arXiv \|vauthors=Liu Z, Zou L, Zou X, Wang C, Zhang B, Tang D, Zhu B, Zhu Y, Wu P, Wang K, Cheng Y\|date=27 Sep 2022\|title=Monolith: ~~The~~Real Time Recommendation System ~~Behind~~With ~~TikTok~~Collisionless ~~\|url=https://gantry.io/blog/papers-to-know-20230110/~~Embedding Table\|~~access-date~~arxiv=~~2023-05-30 \|website=gantry~~2209.io 07663\|~~language~~class=encs.IR}}</ref> ==See also== Line 286: * [http://www.ru.is/faculty/ulfar/CuckooHash.pdf A cool and practical alternative to traditional hash tables] {{Webarchive\|url=https://web.archive.org/web/20190407085017/http://www.ru.is/faculty/ulfar/CuckooHash.pdf \|date=2019-04-07 }}, U. Erlingsson, M. Manasse, F. Mcsherry, 2006. * [http://www.itu.dk/people/pagh/papers/cuckoo-undergrad.pdf Cuckoo Hashing for Undergraduates, 2006], R. Pagh, 2006. * [~~http~~https://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part.html Cuckoo Hashing, Theory and Practice] (Part 1, [~~http~~https://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part_15.html Part 2] and [~~http~~https://mybiasedcoin.blogspot.com/2007/06/cuckoo-hashing-theory-and-practice-part_19.html Part 3]), Michael Mitzenmacher, 2007. * {{cite conference \|last=Naor \|first=Moni \|author2=Segev, Gil \|author3=Wieder, Udi \|title=History-Independent Cuckoo Hashing \|book-title=International Colloquium on Automata, Languages and Programming (ICALP) \|place=Reykjavik, Iceland \|year=2008 \|url=http://www.wisdom.weizmann.ac.il/~naor/PAPERS/cuckoo_hi_abs.html \|access-date=2008-07-21}} * [http://www.cs.princeton.edu/~mfreed/docs/cuckoo-eurosys14.pdf Algorithmic Improvements for Fast Concurrent Cuckoo Hashing], X. Li, D. Andersen, M. Kaminsky, M. Freedman. EuroSys 2014. Line 292: ===Examples=== [https://github.com/efficient/libcuckoo Concurrent high-performance Cuckoo hashtable written in C++] [~~http~~https://sourceforge.net/projects/cuckoo-cpp/ Cuckoo hash map written in C++] * [http://www.theiling.de/projects/lookuptable.html Static cuckoo hashtable generator for C/C++] * [http://hackage.haskell.org/packages/archive/hashtables/latest/doc/html/Data-HashTable-ST-Cuckoo.html Cuckoo hash table written in Haskell]