Network Performance Monitor

# npm

## shashi

0.2.4 • Public • Published

### Shashi

Shashi, a simple module to generate, using pseudo-randomness, a universal family/set of hash functions, which produce integer values within the selected range (a prime number).

### A random bit of theory

A family H of hash functions is universal if, for any two items in the universe, the probability of collision is 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 universal when, for any two items x != y:

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

In other words, chosen h uniformly at random, from a universal set H of hash functions, if h is used to hash n arbitrary keys into m slots, then, for a given key k, we expect that the total number of collisions with 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 (with high probability), interpreting lists of resulting hashed values as edges to insert in a bipartite or tripartite (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| = c * n > 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

require:

### Run Tests

to run all test files, install devDependecies:

to execute a single test file simply do:

### Run Benchmarks

run miscellaneous benchmarks for Shashi:

### Method

Arguments within [ ] are optional.

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

get a method to use a family of hash functions.

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

the callback gets 3 arguments:

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.

### Install

`npm i shashi`

28

0.2.4

MIT

### Homepage

github.com/rootslab/shashi

### Repository

github.com/rootslab/shashi