On Tuesday, 14 April 2026 12:55:46 Pacific Daylight Time Bjorn Reese via Std-
Proposals wrote:
> > Not really. If you have a fixed non-cryptographic hash function,
> > I think it's practical to construct a set of keys that will cause
> > so many collisions that nobody would call that O(1). A decade ago
>
> 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.

The solution for this was to introduce non-linear hashing functions and a
private salt.

-- 
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
  Principal Engineer - Intel Data Center - Platform & Sys. Eng.