NAME

Algorithm::Toy::HashSC - toy separate chain hash implementation for Perl

SYNOPSIS

  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);

DESCRIPTION

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.

CONSTRUCTOR

The new method accepts any of the "ATTRIBUTES".

ATTRIBUTES

_chain

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).)

METHODS

clear_hash

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 eq operator ("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.

keys

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

Reporting Bugs

Bugs, patches, and whatnot might best be applied towards:

http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Toy-HashSC

https://github.com/thrig/Algorithm-Toy-HashSC

Known Issues

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.

SEE ALSO

"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.

AUTHOR

thrig - Jeremy Mates (cpan:JMATES) <jmates at cpan.org>

COPYRIGHT AND LICENSE

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).