[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: RE: stringtable and Table Hashing
- From: Yann Com-Nougue <ycomnougue@...>
- Date: Tue, 1 Jun 2004 17:28:47 -0400
@Win Couwenberg said
> About the special string hash table: Lua uses a string
> object (TString) to represent strings and maps equal C
> strings to the *same* TString. To do this it uses the
> special string hash table with ordinary C strings
> (i.e. const char* + length) as keys and TString* as
> values. The "usual" hash table can not be used
> because a C string is not a Lua type that can occur as
> a key (or value) in such a table.
> Testing two TStrings for equality now takes just a
> simple pointer comparison and not a full memcmp call.
> This is a huge gain because strings are very common as
> table keys (almost all identifiers in a Lua program
> end up as keys in a table.)
I agree that hashing strings is a very good thing :). After
learning new vocabulary today I can restate my original thoughts...
The stringtable uses chaining to resolve hash collisions which seems
to me to be a good solution to collisions. Whereas the hashing of tables
(in ltable.c) uses probing to resolve collisions. Intuitivelly I would
think that chaining is a generally better solution but I`m new at this so I
might be wrong.
Anywho, my app inserts data in the hash mostly at init so what I
need is lookup speed. I will be profiling the number of collisions and
nodes traversed when probing to have a better idea of how my data set reacts
to the probe collision handling. If time permits, I might change it to
chaining and run my profiling again to see what's best for me :)