- SEE ALSO
- COPYRIGHT AND LICENSE
Algorithm::Toy::HashSC - toy separate chain hash implementation for Perl
use Algorithm::Toy::HashSC; my $h = Algorithm::Toy::HashSC->new; $h->put("key", "value"); $h->get("key"); # "value" $h->put("blah", 42); $h->keys; # "key","blah" $h->take("blah"); # 42 $h->keys; # "key" # perhaps more interesting once more key/value pairs are added $h->keys_with("key") # "key" # keys in a particular chain (from 0 to the modulus-1) $h->keys_in(0); # reset things $h->clear_hash; # change the number of chains (or buckets). this will destory # any prior contents of the hash $h->modulus(2); # or the modulus can be set via the constructor $h = Algorithm::Toy::HashSC->new( modulus => 2 ); # Danger zone! $h->unsafe(1);
A toy separate chain hash implementation; productive uses are left as an exercise to the reader. (Hint: music or artwork where the particulars of the hash code and modulus groups the data in a deterministic manner; this ordering or grouping can help determine e.g. pitch sets, rhythmic material, etc. Hence, the keys_in and keys_with methods to obtain the keys in a chain, or with a particular key. Variety could be added by varying the modulus, or changing the hash or hashcode methods.)
This module is not for use where performance is a concern, or where untrusted user input may be supplied for the key material. "Algorithmic Complexity Attacks" in perlsec discusses why Perl's hash are no longer deterministic.
The new method accepts any of the "ATTRIBUTES".
Where the keys and values are stored. Internal value. No peeking!
- modulus an-integer-greater-than-one
Gets or sets the modulus attribute. This determines the number of chains available. It probably should be a prime number (and must be greater than one) to better help evenly distribute the keys. A smaller modulus will cause longer chains, that is, more keys and values lumped together.
Setting this value will clear the contents of the hash (by default).
- unsafe boolean
If set to a true value, will allow unsafe operations. Possible side- effects include old keys and values lingering in the hash (use clear_hash if this is a problem) or keys and values not being available, or to allow duplicate keys to be stored (depending on the particulars of modulus and the result of the hash calculation).
(A caller could pass keys with a hashcode method that violates the unsafe setting, but that's their problem (or feature).)
Clears the contents of the hash and returns the object.
The hash may also be cleared by default when various attributes are altered.
- get key
Obtains the value for the given key. The key may be a scalar value, or a coderef that provides a hashcode method. Equality is tested for via the
eqoperator ("Equality Operators" in perlop).
Like take but not destructive.
- hash key
Used internally to calculate the index of the chain (or bucket) where a given key resides, within the limits of the modulus attribute. This calculation can be adjusted by supplying keys with a hashcode method.
Returns the keys present in the hash, if any. Keys are ordered based on the structure of the hash chains, and this ordering will not change unless the modulus attribute or hash or hashcode methods are altered.
- keys_in chain-number
Returns the keys in the given chain-number where chain-number is less than modulus, if any.
- keys_with key
Returns the keys in the same chain as the given key, if any. As with keys, this grouping will not change unless various attributes or methods are altered. A smaller modulus will cause more keys to group together.
- put key value
Adds the given key and value to the hash. The key may be an object with a hashcode method; this method should return a number that for the expected set of key values results in evenly distributed numbers across the given modulus. If the key already exists in the hash, the value will be updated.
- take key
Deletes the given key/value pair from the hash, and returns the value. A destructive version of get.
Bugs, patches, and whatnot might best be applied towards:
The default hash code calculation has not been tested to determine how evenly it spreads keys out across the modulus space. As a workaround, the hash key can be an object that provides a hashcode method, in which case this issue falls out of scope of this module.
"Algorithmic Complexity Attacks" in perlsec - details on why Perl's hash do not behave so simply as that of this module do.
"Algorithms" (4th Edition) by Robert Sedgewick and Kevin Wayne.
Hash::Util - insight into Perl's hashes.
The "smhasher" project may help verify whether hashcode functions are as perfect as possible.
thrig - Jeremy Mates (cpan:JMATES)
<jmates at cpan.org>
Copyright (C) 2015 by Jeremy Mates
This module is free software; you can redistribute it and/or modify it under the Artistic License (2.0).