Wow, I appreciate your thorough examination.
Nearly all of the shortcomings came from me following the simple interface
and behavior laid out in chapter 5 of Mark Weiss' "Data Structures and
Algorithm Analysis in C++" (I wanted to ensure that I had something working
as intended), such as using horners to begin with and reducing mod 2^32
(the book uses unsigned ints, though you are right about moving the mod
inside the reduction) and reversing the input string to mimic a for each
loop.
I guess the only reason for tacking on the zero is to handle zero-length
strings?
Frankly, I hadn't even considered empty strings, but rather, I was using 0
as a logical start value.
One alternative is to use the recently-added fold family of the
conjunctions
I have actually never used these before, but it appears that the equivalent
of the C++ code, found in Figure 5.4 of the aforementioned book and below,
would be (0 [F..((2 ^ 32x)|[+37x*]) 3 u: ]), which is much less
intimidating than I had originally thought and handles empty strings as you
mentioned.
unsigned int horners(const std::string& key, int tableSize) {
unsigned int hashValue = 0;
for (char c : key) hashValue = 37 * hashValue + c;
return hashValue % s;
}
clear =: {{ 1 [ table =: a: #~ ts }
I should definitely set occupancy to 0 here regardless, but I am not sure
about setting the table size to 0 (reusing the initial table size to
possibly free up memory seems better). The goal of this method is to
simply empty all of the items inserted into the table, and my current,
naive understanding is that you would change how many buckets you have
when it's time to rehash, which is the situation Matt is describing in his
talk with the set max load factor method. Could you elaborate on this?
Best Regards,
Luke De La Cruz
On Tue, Jul 18, 2023 at 5:13 AM Elijah Stone <elro...@elronnd.net> wrote:
Cool.
> if. contains y do. 0 return. end.
I think the more usual hash table interface, when asked to insert a key
that
matches an existing one, replaces the existing value with the new one.
> horners =. (2 ^ 32x) | [: (+37x&*)/ 0 |.@, 3 u: ]
- Reducing this mod 2^32 at end seems a bit pointless, as you are about to
reduce it mod the table size anyway. Evaluating the intermediate
operations
mod 2^32, to avoid blowup in the intermediate terms, seems more useful.
The
way to do this now is to use the recently-added conjunction m.
(https://code.jsoftware.com/wiki/Vocabulary/mdot); + m. (2x^32) does an
addition mod 2^32, and ditto * .
- Adding a zero at the beginning and then reversing seems a bit odd--why
not
just add the zero to the end and not reverse? The result will be
different,
but if the hash is good, it should not change the quality. (I guess the
only
reason for tacking on the zero is to handle zero-length strings? It's
annoying that this needs extra effort, and I've specced, but not
implemented,
a solution. One alternative is to use the recently-added fold family of
the
conjunctions--https://code.jsoftware.com/wiki/Vocabulary/fcap)
Following notes are for recreational purposes only:
- I think a more usual approach nowadays to hashing large strings is to
apply
a mac to some fixed-size blocks (a straightforward--though probably
suboptimal--implementation is (-blocksize) mac\ string) and then a more
expensive/expressive polynomial or similar for combining the blocks--this
should be faster and better quality than djb, though probably more effort.
- You can use _3&ic--after padding to a multiple of 8 bytes--to get the
characters packed more densely--eight per element, rather than one. If
using
a better hash (i.e., something other than the likes of djb or fna-1a),
that
will let you get through it quicker.
> NB. maybe there's a better int hash?
Perhaps an appelby-style mixer--e.g.
http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
It's a good idea to apply such a mixer to the result of the string hash,
too.
> ts&|`horners@.('literal' -: datatype) y
> index =: {{ ts | hash y }}
When y is an integer, you reduce it mod x in hash, and then immediately
again
in index.
> clear =: {{ 1 [ table =: a: #~ ts }}
I think this is prone to space leaks. Shouldn't it reset the table size
to
zero? You won't be able to reuse the storage from the table anyway.
(Well,
you could, but you don't.) Alternately, you could save the size passed in
when the table was created and use that instead. But empirically, it
seems
like a bad idea to let users control such aspects of the hash table--as
the
designer of google's hash table says: https://youtu.be/ncHmEUmJZf4?t=3075.
> cs =: 0 NB. current size
I think this is usually referred to as 'occupancy' (as in 'how many
occupants
does the table have?').
> 1 [ insert every items
It's common to return EMPTY (which is the same as i.0 0) from a verb which
is
called only for effect (rather than for its result). As a matrix with
zero
rows, it takes up zero lines of precious screenspace at the repl--a pun,
but a
cute one.
On Tue, 18 Jul 2023, Luke D wrote:
> I have written an implementation for a separate chaining hash table that
> handles integer and string keys, which I have posted as a gist
> https://gist.github.com/4hg/f412476edba86599f1b0e6dd2ea8b12d, and I am
> moderately pleased with the outcome. It was my first exploration with the
> topics found in chapter 25 of Learning J.
>
> If anyone cares to comment, I am eager to hear any feedback regarding
> convention or design. Feel free to tear it up, if necessary, however, I
> still have some testing to do, so apologies if I am showcasing a limp
horse.
>
> Best Regards,
> Luke De La Cruz
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
