[pro] "fhash"

[Pascal J. Bourguignon]

Daniel Weinreb <dlw at google.com> writes:

> Friends,
>
> I wrote a little package for "fash hash tables", which provide an
> abstraction that is analogous to that of Common Lisp hash tables, but
> is faster for tables with few elements, and only slightly inferior for
> tables with many elements.
>
> I did this because performance analysis showed that our system was
> spending too much time in hash table operations, and using the new
> package helped.
>
> I have recently been cleaning this up, one reason being that I'd like
> to open source it.  The function names used to be things like getfhash
> and mapfhash.  Now they are like fhash:get and fhash:map-elements and
> so on.
>
> However, before I open-source it, I was to make sure it's "right".  It
> recently occurred to me that the package name "fhash" has problems.
>
> Here are pros and cons of changing it that I can see.
>
> Pro: I's not a hash table in the small-cardinality case; it's a linear
> lookup.  So the name is not actually accurate.
>
> Pro: Calling such a data structure a "hash table", even as Common Lisp
> does, is an abstraction violation.  Whether it works by hashing is an
> implementation detail.  The Java collection library calls this a Map.
> Python calls it a dictionary.  Clojure calls it a map.  Those are both
> better names.
>
> Con: Common Lisp already uses the name "hash table", so it would be
> easier for existing Common Lisp programmers to see the analogy.
>
> Advice?  Thanks!

Cesarum has an ADAPTATIVE-DICTIONARY abstraction that does that:

https://gitorious.org/com-informatimago/com-informatimago/blobs/master/common-lisp/cesarum/dictionary.lisp

It uses hash-tables when it's fast, and faster data structure when
hash-tables are slow (ie. when they don't have enough elements).


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.