Shashi, a simple module to generate, usingpseudo-randomness, auniversal family/set of hash functions, which produceinteger valueswithin the selected range (aprimenumber).

###A random bit of theory

A family

Hof hash functions isuniversalif, for any two items in the universe, theprobability of collisionis as small as possible.

Briefly, assumed that for every input key k ∈ K and for every hash function h ∈ H:

- h(k) map to { 0, 1, .., m−1 }

then,

H is universalwhen, for any two items x != y:

- Prob( h(x) == h(y) ) =
1/m

In other words, chosen

huniformly at random, from auniversal set Hof hash functions, if h is used to hashnarbitrary keys intomslots, then, for a given keyk, we expect that the total number ofcollisionswith k is <n/m.

Universal hash functions could also be used to compute

perfect hashing, for a determined set of keys.

Choosing properly a prime p and a constant c:

- p > c*|set of keys| (c >= ~2.09)

We expect to find a perfect hash mapping for values, in a

finite time(withhigh probability), interpreting lists of resulting hashed values as edges to insert in abipartiteortripartite(hyper)graph G= {V,E}:

- |E| = n (keys)
- |V| = p

we set:

- |V| = c * |E|

then we choose a prime >= 2*n:

- |V| = p = c
|E| = cn > n * 2

Algo example; we choose |H| = 2, then H = { h0, h1 }:

while ( true ) :

pick-up at random 2 hash functions from H

for every key k ∈ K, add resulting edge and vertices to the 2-graph:

- edge = (v0, v1), with v0 = h0(k), v1 = h1(k)
now testing the 2-graph acyclicity (it could be performed in linear time).

if 2-graph is acyclic:

- break the loop, well done!

- from now on, you can build a perfect hashing function for your set of keys, in a deterministic way.
- otherwise let's gamble!!

- continue loop, picking-up 2 others random hash functions

See also:

###Install

```
$ npm install shashi [-g]
```

require:

```
var Shashi = require( 'shashi' );
```

###Run Tests

to run all test files, install devDependecies:

```
$ cd shashi/
# install or update devDependecies
$ npm install
# run tests
$ npm test
```

to execute a single test file simply do:

```
$ node test/file-name.js
```

###Run Benchmarks

run miscellaneous benchmarks for Shashi:

```
$ cd shashi/
$ npm run bench
# or to run a single file
$ node bench/file-name-bench.js
```

###Method

Arguments within [ ] are optional.

#####Generate seed sequence using Math.random.

get a method to use a family of hash functions.

```
/*
* A trivial example, Shashi( 2, 16, 257 ) generates:
* - 2 hash functions, h0 and h1 (indexes 0, 1)
* - every hash fn, expects/accepts at most 16 items to encode
* - the range of items should be: [0,255], then using 1 byte
* per item in the seed sequence.
*
* NOTE:
* - if the p number is not a prime, the next greater prime number will be calculated.
* - if the p number is out of range (> 2^53), you'll get an Error.
*/
Shashi( Number hash_fn, Number items_to_hash, Number prime_for_seed_range ) : Array
```

It returns an Array composed by:

- a method used to retrieve and execute a particular hash function, using an index (0-k).
- the underlying seed
Sequence, used for generating the hashed value (an integer).

```
/*
* When you only need to regenerate random data for seeding your hash functions,
* you can simply refresh the seed sequence using Sequence#fill or Sequence#parse.
*
* See also https://github.com/rootslab/brando.
*/
Array : [ Function uhash, Sequence seed ]
// universal set of hash functions
uhash : function ( Number fn_index, Buffer input_data [, Number bytes_per_item ] )
```

#####Generate seed sequence using a random sample.

When a data Buffer is used to fill the seed sequence, the method automatically switches to the callback mode.

```
Shashi( Number h, Number i, Number p [, Buffer src [, Function cback ] ] ) : undefined
```

the callback gets 3 arguments:

```
/*
* NOTE: an error was returned when:
* - the number supplied for the seed sequence range is not a prime.
* - the sample data are not enough to fill the random seed Sequence.
*/
cback : function ( Error e, Function uhash, Sequence seed ) { .. }
```

See also

examples.

Copyright (c) 2015 < Guglielmo Ferri : 44gatti@gmail.com >

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the 'Software'), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Great Documentation0

Easy to Use0

Performant0

Highly Customizable0

Bleeding Edge0

Responsive Maintainers0

Poor Documentation0

Hard to Use0

Slow0

Buggy0

Abandoned0

Unwelcoming Community0