On 4/14/26 22:54, Thiago Macieira via Std-Proposals wrote:
> On Tuesday, 14 April 2026 12:55:46 Pacific Daylight Time Bjorn Reese via Std-
> Proposals wrote:

>> You may want to read this:
>>
>>
>> https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-scien
>> ce-conjecture-20250210/
>
> The problem Jens was alluding to isn't on the table itself, but on the hashing
> *function*, such that two or more elements have a hash collision, so they must
> end up in the same bucket in any hashing table implementation. And this affects
> not just insertion, but in particular it affected lookups as well, so the
> standard thinking of "hash table lookups are O(1)" isn't true any more - it's
> O(n), which is worse than a sorted flat map.

This problem is known as linear or uniform probing, and this is exactly
that the abovementioned article addresses.