This topic is very interesting. There are a few hashmap implementations floating around based on J's object system. I wrote one myself a long time ago.
Having a canonical, or primitive implementation of a hashmap / dictionary is something I am all for. I think necessities are 1. mutability: changing keys or values does not copy the whole datastructure. 2. Constant time lookup, insert, removal. Constant time may degrade into linear time under certain cases. 3. Arbitrary keys. Numerical, characters, boxes. Objects would be tricky. 4. If hashing is used on keys, which I presume will be, use a good, fast, standard non crypto hash. Murmurhash or CityHash for example. 5. Extra idea. Override key hash algorithm, and therefore equality operation, if possible. 6. Another extra idea. As D. And d. are now vacant, why not use these primitives? Thanks, Jon On Apr 14, 2021, 11:56 PM, at 11:56 PM, Henry Rich <[email protected]> wrote: >Let's get a spec for what we need before we implement. > >1. What datatypes are needed? >* Dictionary > >2. What operations are needed? >* Add key/value pairs >* return value for a given key > >3. What are the types of key and value? >* they can have any type >* perhaps the keys have to have all the same type, values likewise > >Please fill this out. This is as far as I got, and for that I think >the >Dictionary type could just be a numbered locale with a few methods. > >Henry Rich > > > >On 4/14/2021 10:47 AM, Raul Miller wrote: >> Conceptually, here, you're probably thinking about using hashes of >> character strings as array indices. >> >> A character string, in J, is either a boxed rank 1 list of characters >> or a rank 1 member of a higher dimensional character array which has >> been padded on the right hand side with spaces. >> >> Since all of the current array index primitives throw an error when >we >> try to use characters to index them, I think that we would not need >> any new primitives -- we would "only" need to characterize the >> normalization process used to convert arbitrary character arrays or >> boxed character arrays to array indices. >> >> That said, these hashed arrays would also be sparse. And, it would be >> desirable to support boxed items and boxed hashes. And that gets into >> some issues which are ... rather involved, if we think about the >> existing sparse array implementation. >> >> So ... when estimating this task it might be best to think of it as >> "re-implementing sparse arrays from the ground up"? >> >> Thanks, >> > > >-- >This email has been checked for viruses by AVG. >https://www.avg.com > >---------------------------------------------------------------------- >For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
