To do justice to this topic requires an extended essay.
a. It matters a great deal what kind of keys you have.
For some keys I know of no efficient implementation.
(e.g. boxed items containing more than a few floating
point numbers, with non-zero tolerance.)
b. It matters what the pattern of put and get is like.
(Lots of gets with few puts? As many puts as gets?
Individualized gets? Gets with lots of keys en masse?)
c. The special code in J is for K&i. . But K has to
be fixed.
d. One method is to make K more than twice as
big as the number of real keys, and rehash when
the density exceeds 0.5.
e. Probably best to avoid the phrase (V,a:) or
(V,nullvalue) in get. Better to use something like
> V {~ :: (nullvalue"_) K i. boxopen y
(p.s. Ian Clark, this is a good example of using a
constant function.)
----- Original Message -----
From: Andrew Nikitin <[email protected]>
Date: Friday, February 26, 2010 10:26
Subject: [Jprogramming] Dictionary AKA hash
To: J programming <[email protected]>
>
> What is the reference implementation of dictionary AKA hash?
>
> I see 2 alternatives:
>
> One is to use dyadic i.
> Something like
>
> cocurrent 'hash'
> K=:i.0
> V=:i.0
>
> get=:3 : '>(V,a:){~K i. boxopen y'
> put=:4 : 0
> i=.K i. y=.boxopen y
> if. i>:#K do.
> V=:V,<x
> K=:K,y
> else.
> V=:(<x) i} V
> end.
> i. 0 0
> )
> cocurrent 'base'
>
> I mildly recall that i. has some kind of special code that could
> help make the above scheme tolerable for larger sets of keys,
> but I am not sure which form triggers this special code.
>
> Another is to use J's built in ability to search for a name in
> locale. That would require to nameify arbitrary string and save
> the value into this name (in dedicated dictionary locale) using
> some kind of ". or (expr)=:...
>
> This one just does not feel right.
>
> I would appreciate if someone who already implemented hashes
> could share his insights.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
