O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911300773216256 |
|---|---|
| author | Bell, Tolson Frieze, Alan |
| author_facet | Bell, Tolson Frieze, Alan |
| contents | The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk $d$-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every $d\ge 3$ random hashes, let $c_d^*$ be the sharp threshold for the load factor at which a valid assignment of $cm$ objects to a hash table of size $m$ exists with high probability. We show that for any $d\ge 3$ hashes and load factor $c<c_d^*$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14394 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold Bell, Tolson Frieze, Alan Data Structures and Algorithms Combinatorics 68Q25 F.2.2; E.2 The random walk $d$-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk $d$-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every $d\ge 3$ random hashes, let $c_d^*$ be the sharp threshold for the load factor at which a valid assignment of $cm$ objects to a hash table of size $m$ exists with high probability. We show that for any $d\ge 3$ hashes and load factor $c<c_d^*$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$. |
| title | O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold |
| topic | Data Structures and Algorithms Combinatorics 68Q25 F.2.2; E.2 |
| url | https://arxiv.org/abs/2401.14394 |