Skip to content

Instantly share code, notes, and snippets.

@hyamamoto
Created September 30, 2016 07:19
  • Star 72 You must be signed in to star a gist
  • Fork 6 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save hyamamoto/fd435505d29ebfa3d9716fd2be8d42f0 to your computer and use it in GitHub Desktop.
JavaScript Implementation of String.hashCode() .
/**
* Returns a hash code for a string.
* (Compatible to Java's String.hashCode())
*
* The hash code for a string object is computed as
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
* using number arithmetic, where s[i] is the i th character
* of the given string, n is the length of the string,
* and ^ indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @param {string} s a string
* @return {number} a hash code value for the given string.
*/
hashCode = function(s) {
var h = 0, l = s.length, i = 0;
if ( l > 0 )
while (i < l)
h = (h << 5) - h + s.charCodeAt(i++) | 0;
return h;
};
> hashCode('')
0
> hashCode('Hello')
69609650
@Super-Chama
Copy link

Super-Chama commented May 4, 2023

Here's even faster implementation of the original using ES6 reduce.
This code is similar to what @jschirrmacher have suggested hence not a new implementation.
But from my small limited testing it seems to be faster than original while loop and for loop.

function hashCode(s) {
  return [...s].reduce(
    (hash, c) => (Math.imul(31, hash) + c.charCodeAt(0)) | 0,
    0
  );
}

Tested in Chrome (112.0 v)

  • Original (while loop): 2.40087890625 ms
  • Modified (for loop): 3.412109375 ms
  • New (reduce): 1.150146484375 ms

@martin-juul
Copy link

@Super-Chama you copied the answer from @4nte ...

@Super-Chama
Copy link

@martin-juul no, look again.

@ngp33
Copy link

ngp33 commented Jun 28, 2023

So no one else wastes time looking for the difference (there is none):

const hashCode = (str) => [...str].reduce((s, c) => Math.imul(31, s) + c.charCodeAt(0) | 0, 0)
function hashCode(s) {
  return [...s].reduce(
    (hash, c) => (Math.imul(31, hash) + c.charCodeAt(0)) | 0, // extraneous ( )
    0
  );
}

@Super-Chama
Copy link

@ngp33 there's at least 5 differences. my point is, i didn't copy anyone's code. I would happily give credit if i did. I saw the original implementation and thought reduce will be nicer than loop and faster. so i wrote my own, tested with console.time and posted for anyone coming into this thread. but i'll update my comment as precaution

@bryc
Copy link

bryc commented Jul 3, 2023

@martin-juul What's your point? this whole thread is entirely derivative, and there's only so many ways to continually add a sequence of numbers and multiply by 31 in a loop. We're talking about one line of code basically. People modified my code and I did not care, because it's far too basic.

@Super-Chama Hmm, that version appears to in fact be noticeably slower (than my for loop version at least). It could be that either the spread operator or reduce is slowing things down in batch operations, not sure which. See benchmark: https://jsbench.me/vcljn1em32

@ngp33
Copy link

ngp33 commented Jul 4, 2023

I tried to use this method in my project but it didn't seem to spread out adjacent inputs very well:

for (let i = 0; i < 1000; i++) {
  console.log(hashCode("" + i));
}
48 49 50 51 52 53 54 55 56 57 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700

I found this awesome single file module that works great though:
https://github.com/garycourt/murmurhash-js

@bryc
Copy link

bryc commented Jul 4, 2023

@ngp33 Indeed, it's not a good hash function, but some people need compatibility with Java.
I posted this answer in direct response to this algorithm constantly being shared around, for those needing a rock-solid general function.

@jlevy
Copy link

jlevy commented Feb 15, 2024

Just FYI, another take on the same problem here, with both an old Java-style hash and with a version of @bryc's excellent, more modern cyrb53 hash:
https://gist.github.com/jlevy/c246006675becc446360a798e2b2d781

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment