<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/129384>129384</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] adapt "elastic hashing" in `std::__hash_table`
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++,
            performance
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          firewave
      </td>
    </tr>
</table>

<pre>
    Recently I came across this article: [Undergrad and colleagues accidentally shred 40-year hash table gospel](https://www.theregister.com/2025/02/13/hash_table_breakthrough/).

It refers to another article ([Undergraduate Upends a 40-Year-Old Data Science Conjecture](https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/)) which is about the paper [Optimal Bounds for Open Addressing Without Reordering](https://arxiv.org/abs/2501.02305).

The paper is about assumptions in the implementation of hash tables and includes an insertion strategy referred to as "elastic hashing".

I do not know if this could actually be applied to the implementation of `std::__hash_table` but I thought it might be worth pointing out.

CC @ldionne as this concerns libc++ performance.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJx8VE1v4zYQ_TXUZSCDpizHPujgJDCQU4BtF0VPwYgcSexSpEoO46a_vqDiTVwg7UkSIb2PeU-DKdnRE3WivRftY4WZpxC7wUa64CtVfTBv3TfS5Nm9wRNonAlQx5AS8GQTYGSrHYnmBKK9_-4NxTGiAfQGdHCOcMyUALW2hjyjc2-QpkgGdrJ-I4wwYZqAsXcEY0gLOdE-CnWYmJckmpNQZ6HOl8tlwxNFGm1iihsdZqHOSqpWqLNUQp23jVDngvWyYr30kfAHTzHkcVoxjhshT0KenhgiDRQTcAD0ocD-tAFCHW5tZGSC7wt5kwCL4t8JY_3sDDwiI_yiLXlN8BD8H6Q5R_ov7X9m9Iwzjvi39bQJcRTqnG9p6rzS1FhfB1MHZ2qDjHV6p6n1B01dnEu1le_OhDrCZbJ6gpJIHzIDTwQLLhRLLM8L2xkd3IdcnAwhwvNCHk7GRErJ-hF-szyV775RiIai9eNXVjD-ZV-v6rFPJYJWbjdSNbL9nPCvH9wfcjClPC9sg09g_arOzoujuXSiHEMYbpqQ1v5Yr1026wNYnyiuLyaOyDS-vadYmlRyTCCUIoeJrV6BigOlfmYOJoAPDD98uIAd3rurQ3YGUHNea9kT4LI4-474tUSxl4lNmUdzenn5rJvYS-gzwxOUMY4Tg2WYbbnpCS4h8gRLsJ7LrEPmq66HBxA76YwN3lMxcdXlNUWfwNleC3Uv1D0sFIcQZ_SaNpXpGnNsjlhRt73byUOz37fbaupMc5CyQdzhXqrm2BM2x6MZGhr6_bHfU2W7tTiN3G6b3U4eNmRwuzN3Bxr2_Z2Ug9hJmtG6jXOvcwm6sill6rbq2Bx2lcOeXFqXhVKf6oRSQj0IpW5UlrP2sYpdQar7PKbi1CZOn9hs2a2r5waqfQQ0uPDXeZby_E8GVY6u-3dlR8tT7q8LozBfL_USQ_mbhDqvFkuZry5fO_VPAAAA__8fGrB5">