Re: hash metamethod?

[Jerome Vuarand <jerome.vuarand@...>]

2009/2/2 Joshua Haberman <joshua@reverberate.org>:
> Jerome Vuarand <jerome.vuarand <at> gmail.com> writes:
>> 2009/2/1 Joshua Haberman <joshua <at> reverberate.org>:
>>> Languages like Ruby, Python, etc. allow you to define hash functions that
>>> apply to your objects.  You define a hash function and a comparison
>>> function, and this lets user-defined types be keys in hash tables based on
>>> their values.
>>>
>>> [...]
>>>
>>> In any case, like I said I'm mainly wondering if anyone has a PowerPatch,
>>> I'm not going to argue that it should go into the main Lua (though I
>>> wouldn't mind that either :)
>>
>> You don't need a power-patch, with the help of existing metamethods,
>> you can implement your own hashing algorithm. Here is an example:
>>
>> http://lua-users.org/wiki/ComparisonByValue
>
> This scheme requires that two objects that are not equivalent do *not* have the
> same "hash" value.

The 'hashed' function of the article is just a simple example of a way
to use the __hash metamethod. If you want to allow non-equivalent
objects to have the same hash, you have to deal with collisions
yourself, but you can still implement it without patching Lua. And
this doesn't impact the interface of the proposed __hash metamethod
(which was the point of my link).

> At this point it's not really a hash anymore, it's a
> fingerprint:
>
> http://en.wikipedia.org/wiki/Fingerprint_(computing)
>
> [...]

Since you quote Wikipedia let me do the same. From
http://en.wikipedia.org/wiki/Hash_function, I read (words in bracket
are the application to the wiki article) :

"A hash function is any well-defined procedure or mathematical
function [the __hash metamethod] which converts a large, possibly
variable-sized amount of data [the object whose __hash metamethod is
called] into a small datum [the value returned by the __hash
metamethod], usually a single integer [or any other non-nil Lua value]
that may serve as an index [key] into an array [Lua table]."

> All of these things can be worked around in various ways.  But it's awkward and
> the performance will probably not be as good as having the real hash table
> implementation call your hash function and equality comparisons.

In Java (I don't know Ruby or Python) the hashCode and equals methods
of objects are methods of the base Object class. Since Lua has no
class it feels natural to use metamethods instead.

The wiki article proposes an interface (the __hash metamethod), and a
sample implementation that requires no patch to lua source code but
requires instrumenting all Lua tables that would have to use this new
metamethod. It's only using __hash, but it's 10 lines long and it
could be modified to handle __equal too and deal with collisions.

And if that's too slow or if you want that behaviour to be applied to
all tables you can patch Lua to call the metamethod at a lower level.
If you only want speed though and don't mind having to create this
alternate type of table with a function call, you can implement
pseudo-tables with userdata, and have them appear just like tables to
Lua code (afaik with proper metamethods and overriding of type, next,
pairs, ipairs and table.* you can make userdata indistinguishable from
real tables).