darkskyapp / string-hash Goto Github PK

Fast string hashing function for Node.JS.

JavaScript 100.00%

string-hash's Introduction

string-hash

A fast string hashing function for Node.JS. The particular algorithm is quite similar to djb2, by Dan Bernstein and available here. Differences include iterating over the string backwards (as that is faster in JavaScript) and using the XOR operator instead of the addition operator (as described at that page and because it obviates the need for modular arithmetic in JavaScript).

The hashing function returns a number between 0 and 4294967295 (inclusive).

Thanks to cscott for reminding us how integers work in JavaScript.

Example

npm install string-hash or yarn add string-hash, then:

const stringHash = require("string-hash");
console.log(stringHash("foo")); // prints "193420387"

Note that the return value is always an unsigned, 32-bit integer.

License

To the extend possible by law, The Dark Sky Company, LLC has waived all copyright and related or neighboring rights to this library.

string-hash's People

Contributors

Stargazers

Watchers

string-hash's Issues

Consider iterating over the string in forward direction

Differences include iterating over the string backwards (as that is faster in JavaScript)

This requires some proof, because for long strings backward iteration may break any data caching/prefetching, therefore access to string characters may be significantly slower.

https://jsperf.com/string-hash-speed forward direction is faster in Chrome

https://gist.github.com/victor-homyakov/bcb7d7911e4a388b1c810f8c3ce17bcf shows me that in Node 8.6.0 forward iteration is twice as fast.

Strange case insensitivity property

I was using this module to get a hash and mod by 16 to get a random-ish but constant index for a given string. I was about to ensure the string was lowercase so that the hash was case insensitive, when I noticed that all my indexes for a string were the same no matter what the case was!

Here's an example on tonic to show this: https://tonicdev.com/rahat/string-hash-case-insensitivity

I noticed that this property holds true if you mod a hash by a power of 2 up to 6432 (though 64 does have a lot of matching indexes, it will rarely have a different index for a different case).

I don't know if this a bug per-se, but it is a very interesting property. Any clue as to why it behaves like this?

bump version number?

so that your changes since 2012 will be available on npm =]

I found a collision with 70k strings T_T

source code:

const glob = require('glob')
const hash = require('string-hash')

const names = glob.sync('**')
console.log('Size: %s', names.length)

const used = {}
for (const item of names) {
  const value = hash(item)
  if (used[value]) {
    console.log('Found collision, hash: %s, a: %s, b: %s', value, used[value], item)
  }
  used[value] = item
}

The output is:

Size: 69791
Found collision, hash: 413020853, a: node_modules/@shimo/ui/icons/symbol/plus_circle.svg, b: node_modules/aliyun-sdk/apis/dm-2015-11-23.json

Converting signed to unsigned integers.

I suspect that (x >>> 0) is a quicker way to convert the hash result to an unsigned integer.

Ie, replace:

hash >= 0 ? hash : (hash & 0x7FFFFFFF) + 0x80000000

with:

hash >>> 0

What's the chance of collision?

Thanks for creating this. I was curious, what is the chance of two hashes colliding within this algorithm. I was thinking of using it to hash emails.

no such file or directory, rename

[user@likely html]$ sudo npm install string-hash -save
npm ERR! path /var/www/html/node_modules/npm/node_modules/dezalgo
npm ERR! code ENOENT
npm ERR! errno -2
npm ERR! syscall rename
npm ERR! enoent ENOENT: no such file or directory, rename '/var/www/html/node_modules/npm/node_modules/dezalgo' -> '/var/www/html/node_modules/npm/node_modules/.dezalgo.DELETE'
npm ERR! enoent This is related to npm not being able to find a file.
npm ERR! enoent

npm ERR! A complete log of this run can be found in:
npm ERR! /root/.npm/_logs/2017-12-10T05_45_35_903Z-debug.log