lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Wed, Oct 7, 2020 at 8:39 PM Roberto Ierusalimschy wrote:
> Amortized cost of table insertion is O(n)
> It looks like a bug.
> Although the manual promises nothing about Lua interpreter speed,
> something like O(logn) is usually required for table operations.

I don't think it is wise to expect O(log n) as the worst case for table
operations. Most hash tables have a worst case O(n) for insertion and
retrieval, due to collisions.

It is true that it is always possible to create a sequence of
table operations to exploit collisions in a hash table.

But the bug discussed here is not about collisions.
The keys in my example are the natural sequence of numbers 1,-1,2,-2,....
It is obviously NOT a maliciously crafted sequence to exploit hash table

The bug is due to table rehashing might happen VERY often,
and each rehash costs O(n), hence the quadratic time complexity.
In a correct implementation it is wise to expect O(n) table operations done
before the next rehash happens.