JavaScript calculate hashcode from real number and integer number

Question

Hi there I need function to calculate unique integer number from number (real number double precision) and integer.

Try explain I am developing GIS application in javascript and I am working with complex vector object like polygon (array of points object with two coordinate in ring) and lines array of points. I need fast algorithm to recognize that element has been changed it must be really fast because my vector object is collection of thousand points . In C# I am calculating hash code from coordinate using bitwise operation XOR.

But javascript convert all operands in bitwise operation to integer but i need convert double precision to integer before apply bitwise in c# way (binnary). In reflector i see this that c# calculate hash code fro double like this and I need this function in javascript as fast as can be.

public override unsafe int GetHashCode() //from System.Double
{
    double num = this;
    if (num == 0.0)
    {
        return 0;
    }
    long num2 = *((long*) &num);
    return (((int) num2) ^ ((int) (num2 >> 32)));
}

Example:

var rotation = function (n) {
    n = (n >> 1) | ((n & 0x001) << 31);
    return n;
}

var x: number = 1;
var y: number = 5;

var hash = x ^ rotation(y); // result is -2147483645

var x1: number = 1.1;
var y1: number = 5;

var hash1 = x1 ^ rotation(y1); // result is -2147483645

Example result is not correct hash == hash1

Example 2: Using to string there is correct result but calculate Hash from string is to complicate and I thing is not fast enough.

    var rotation = function (n) {
        n = (n >> 1) | ((n & 0x001) << 31);
        return n;
    }

     var GetHashCodeString = function(str: string): number {
        var hash = 0, i, l, ch;
        if (str.length == 0) return hash;
        for (i = 0, l = str.length; i < l; i++) {
            ch = str.charCodeAt(i);
            hash = ((hash << 5) - hash) + ch;
            hash |= 0; // Convert to 32bit integer
        }
        return hash;
     }

    var x: number = 1;
    var y: number = 5;

    var hash = GetHashCodeString(x.toString()) ^ rotation(GetHashCodeString(y.toString()));
    //result is -2147483605
    var x1: number = 1.1;
    var y1: number = 5;

    var hash1 = GetHashCodeString(x1.toString()) ^ rotation(GetHashCodeString(y1.toString()));
   //result is -2147435090

Example2 result is correct hash != hash1

Is there some faster way than converting number to string than calculate hash from each character? Because my object is very large and it will take lot of time and operation in this way ...

I try do it using TypedArrays but yet I am not successful.

Thanks very much for your help

Ivan Mjartan · Answer 1 · 2015-07-08T10:58:10.237

Hi there I tried use TypedArrays to calculate Hash code from number and the result is interesting. In IE the performance 4x better in Chrome 2x in FireFox this approach is equal to string version ...

var GetHashCodeNumber = function (n: number): number {
         //create 8 byte array buffer number in js is 64bit 
         var arr = new ArrayBuffer(8);

         //create view to array buffer
         var dv = new DataView(arr);

         //set number to buffer as 64 bit float  
         dv.setFloat64(0, n);

         //now get first 32 bit from array and convert it to integer
         // from offset 0
         var c = dv.getInt32(0);

         //now get next 32 bit from array and convert it to integer 
         //from offset 4 
         var d = dv.getInt32(4);

         //XOR first end second integer numbers 
         return c ^ d;
     }

I think this can be useful for someone

EDIT: using one buffer and DataView is faster !

score 1 · Answer 2 · edited May 23 '17 at 11:46

1

I looked up some hashing libraries to see how they did it: xxhashjs, jshashes, etc.

Most seem to take a string or an ArrayBuffer, and also depend on UINT32-like functionality. This is equivalent to you needing a binary representation of the double (from your C# example). Notably I did not find any solution that included more-strange types, other than in another (unanswered) question.

His solution uses a method proposed here, which converts it to various typed arrays. This is most likely what you want, and the fastest accurate solution (I think).

I highly recommend that you structure your code to traverse objects/arrays as desired, and also benchmark the solution to see how comparable it is to your existing methods (the non-working one and the string one).

edited May 23 '17 at 11:46

Community

1
1

answered Jul 01 '15 at 12:47

Neofish

118
8

Hi there thanks a lot i solved it myself few minutes before your post ... but thanks a lot ... – Ivan Mjartan Jul 01 '15 at 13:12
I can't comment on your answer, sorry. Your solution uses more calls than the one I linked to, so I expect this one will be faster. Please check and then accept whichever answer is fastest. – Neofish Jul 01 '15 at 13:35
1

I see this they don't use dataview ... I will try it! Thanks – Ivan Mjartan Jul 01 '15 at 13:55
I tested it and using dataview is faster ... thanks a lot – Ivan Mjartan Jul 01 '15 at 14:37
You should change the accepted answer to yours then. Thanks for checking. :) – Neofish Jul 01 '15 at 14:46
:-) Ok as u wish ... but your answer was very useful for me! – Ivan Mjartan Jul 01 '15 at 15:15

glebm · Accepted Answer · 2017-08-30T13:08:31.150

1

Here is a faster way to do this in JavaScript.

const kBuf = new ArrayBuffer(8);
const kBufAsF64 = new Float64Array(kBuf);
const kBufAsI32 = new Int32Array(kBuf);

function hashNumber(n) {
  // Remove this `if` if you want 0 and -0 to hash to different values.
  if (~~n === n) {
    return ~~n;
  }
  kBufAsF64[0] = n;
  return kBufAsI32[0] ^ kBufAsI32[1];
}

It's 250x faster than the DataView approach: see benchmark.

edited Aug 30 '17 at 13:08

answered Aug 30 '17 at 00:11

glebm

20,282
8
51
67

is there a way to understand what this code is doing? why are the arrays kBuf, kBufAsF64, kBufAsI32 declared as constants if they are being updated with n later in the function. Also kBufAsI32 was never assigned any value directly, so is there some kind of pointer play involved here? – Sanket_Diwale Apr 08 '18 at 14:05
Both of these "arrays" are views into the same 8-byte buffer. We first write the number to the buffer as `float64` (native JavaScript `number` type), then XOR the first half of the bytes with the second half by reading the buffer as two 32-bit (4-byte) integers. – glebm Apr 09 '18 at 14:35

JavaScript calculate hashcode from real number and integer number

3 Answers3