Re: [PATCH] make light userdata a little bit heavier

[Ross Bencina <rossb-lists@...>]

On 22/04/2014 6:39 PM, Coroutines wrote:
> Anyway, I don't see how a hash table of the pointer addresses would be
> better.  Because they're just numbers a binary search to do an
> existence check would seem appropriate, but I'd love to know how a
> hash table would be better suited :>  I'm still trying to get a
> mastery on data structures so...

A hash table has amortized O(1) insert/lookup.

A binary search has worst-case O(logN) lookup time.

If you care about amortized-time then a hash table might be faster. If 
you care about worst-case time then your sorted list solution may be faster.

Either way you need to purge old elements. Although leaving them in the 
table and marking them "dead" when the associated object is deallocated 
kind-of gets around the problem of accessing deallocated data.

Ross.