[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: worst case time using hash-tables in Lua
- From: Andrea <andrea.l.vitali@...>
- Date: Mon, 11 May 2020 15:55:43 -0700
I have seen the recent thread on hash-tables and wanted to ask what is the reason to allow short chains to merge when inserting a key in a slot which was part of another chain?
it seems that this is done to guarantee a constant time to insert, right?
one could achieve constant time without merging the list if there were pointer to previous node, but this would require more memory per node, right?
it seems that this was done in recent versions of Lua - how were collisions managed in previous versions?
I have read many papers on Lua but found little about the design choices adopted in the most recent versions
I hope the Lua team can find the time to write a paper with some historical perspective on how things have evolved, which solutions have been evaluated and discarded and why
lua-l mailing list -- email@example.com
To unsubscribe send an email to firstname.lastname@example.org