Crystal: Drop SimpleHash (Was: SimpleHash and other hashes)

Created on 20 Mar 2016 · 4Comments · Source: crystal-lang/crystal

In the compiler we used to use SimpleHash (a hash built on top of an array of pairs) for some paths where the hash would end up with a few elements. However, we don't use that anymore because the performance difference was negligible.

The problem is, it's kind of public API now, and others want to use it, like here, but I'm not sure I want to stick with that type in the standard library. Or, if we stick with it, it's better if we change its name and clearly state its use case.

The questions are:

Should we keep it in the std? If so, what name do we use? Since it's a Hash backed by an array, maybe ArrayHash would be an appropriate name, although it sounds confusing.
Should we also add a class similar to Hash but without maintaining order? Right now Hash has a doubly linked list that allows maintaining insertion sorter, but this needs more allocated memory to work, so not having this functionality will speed up things in some cases. If so, what name should we use? Or maybe we can swap things, and maybe Hash dumber and add a LinkedHash.

draft stdlib

Source

asterite

Most helpful comment

At first we should drop SimpleHash, especially if it's inefficient and we don't want to maintain it.

I'm all in favor for a fast Hash table by default (there are a bunch of papers on the subject), and maybe an OrderedHash that could be slower/use more memory but come handy at times.

ysbaddaden on 20 Mar 2016

👍6

All 4 comments

Sorry, hit close button on smartphone...

ysbaddaden on 20 Mar 2016

At first we should drop SimpleHash, especially if it's inefficient and we don't want to maintain it.

I'm all in favor for a fast Hash table by default (there are a bunch of papers on the subject), and maybe an OrderedHash that could be slower/use more memory but come handy at times.

ysbaddaden on 20 Mar 2016

👍6

BTW on the topic of hashes: http://preshing.com/20160314/leapfrog-probing/

ysbaddaden on 22 Mar 2016

Wouldn't it be best to have Map and OrderedMap as recommended types? Specific implementations could be chosen amongst via an optional size-ballpark-figure passed to new, or it defaults to a generically fast one. Ofcourse the implementations could be used directly if wanted: HashMap, LeapFrogMap, whatever...

Of course this would cause every call to methods on an instance created via Map.new to be branched I guess (HashMap|LinearMap|LeapFrogMap|MagicMushroomMap|Whatever)