lua-users home
lua-l archive

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


Miles Bader wrote:
"Ashwin Hirschi"<lua-l@reflexis.com>  writes:
Scripting languages like Python, Ruby, Javascript and Perl are dealing
(or have already dealt) with this hash collision issue by making the
necessary changes to their hash implementations.

Shrug.  They are different languages, with different user communities
and applications.  Obviously languages like Ruby _do_ seem to be
overwhelmingly used in "across the internet" applications, so maybe
such a default makes sense for it.  But Lua is not Ruby.

This problem got a lot of major press attention in Germany [1][2][3]. Lua sometimes got explicitly named as vulnerable [1]. I don't think we can afford to ignore this problem.

I believe Lua needs to do the same. If it does not, it risks being
deemed not suitable for writing software for the web. I don't know
about you, but I for one would not like to see that happen.

An "all characters" hash is not free, especially for _very_ long
strings (I regularly handle 500MB strings), and the benefit of such a
change needs to be weighed against the costs, weighted by the
likelihood of each case.

Yes, Lua can't just copy the solution of other languages because the hash needs to skip characters. However, the solution for Lua was already proposed here. A self-balancing tree in the string table seems to solve the problem.


[1] <http://heise.de/-1401784> or the translation
    <http://h-online.com/-1401863>
[2] <http://www.golem.de/1112/88697.html>.
[3] <http://www.spiegel.de/netzwelt/web/0,1518,806173,00.html>