在Javascript中从字符串生成哈希

Question

我需要将字符串转换为某种形式的哈希.这在JavaScript中可行吗？

我没有使用服务器端语言,所以我不能这样做.

Answer 1

String.prototype.hashCode = function() {
  var hash = 0, i, chr;
  if (this.length === 0) return hash;
  for (i = 0; i < this.length; i++) {
    chr   = this.charCodeAt(i);
    hash  = ((hash << 5) - hash) + chr;
    hash |= 0; // Convert to 32bit integer
  }
  return hash;
};

资料来源:http: //werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method/

Answer 2

编辑

基于我的jsperf测试,接受的答案实际上更快:http://jsperf.com/hashcodelordvlad

原版的

如果有人感兴趣,这里有一个改进的(更快的)版本,在没有reduce数组功能的旧浏览器上会失败.

hashCode = function(s){
  return s.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
}

Answer 3

注意:即使使用最佳的32位散列,您也必须处理迟早会发生冲突的事实.即两个不同的输入字符串将返回相同的散列值,概率至少为1:2 ^ 32.

在回答这个问题时, 哪种哈希算法最适合于唯一性和速度？,Ian Boyd发表了一篇很好的深度分析报告.简而言之(正如我所解释的那样),他得出的结论是Murmur是最好的,其次是FNV-1a.
esmiralha提出的Java的String.hashCode()算法似乎是DJB2的变种.

• FNV-1a的分布比DJB2好,但速度较慢
• DJB2比FNV-1a快,但往往会产生更多的碰撞
• MurmurHash3比DJB2和FNV-1a更好更快(但优化的实现需要比FNV和DJB2更多的代码行)

这里有一些带有大输入字符串的基准测试:http://jsperf.com/32-bit-hash
当短输入字符串被散列时,murmur的性能相对于DJ2B和FNV-1a而言下降:http://jsperf.com/32- 位散列/ 3

所以一般来说我会推荐murmur3.
请参阅此处获取JavaScript实现:https: //github.com/garycourt/murmurhash-js

如果输入字符串很短并且性能比分发质量更重要,请使用DJB2(由esmiralha接受的答案提出).

如果质量和小代码大小比速度更重要,我使用FNV-1a的这种实现(基于此代码).

/**
 * Calculate a 32 bit FNV-1a hash
 * Found here: https://gist.github.com/vaiorabbit/5657561
 * Ref.: http://isthe.com/chongo/tech/comp/fnv/
 *
 * @param {string} str the input value
 * @param {boolean} [asString=false] set to true to return the hash value as 
 *     8-digit hex string instead of an integer
 * @param {integer} [seed] optionally pass the hash of the previous chunk
 * @returns {integer | string}
 */
function hashFnv32a(str, asString, seed) {
    /*jshint bitwise:false */
    var i, l,
        hval = (seed === undefined) ? 0x811c9dc5 : seed;

    for (i = 0, l = str.length; i < l; i++) {
        hval ^= str.charCodeAt(i);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }
    if( asString ){
        // Convert to 8 digit hex string
        return ("0000000" + (hval >>> 0).toString(16)).substr(-8);
    }
    return hval >>> 0;
}

Answer 4

根据ES6中接受的答案.更小,可维护,适用于现代浏览器.

function hashCode(str) {
  return str.split('').reduce((prevHash, currVal) =>
    (((prevHash << 5) - prevHash) + currVal.charCodeAt(0))|0, 0);
}

// Test
console.log("hashCode(\"Hello!\"): ", hashCode('Hello!'));

Answer 5

这是一个简单,分布均匀的53位哈希.与32位散列相比,它速度非常快,并且具有明显更低的冲突率.

var jhashcode=s=>{for(var i=0,h;i<s.length;i++)h=Math.imul(31,h)+s.charCodeAt(i)|0;return h}

它使用类似于xxHash/MurmurHash3的技术,但不是那么彻底.它实现了雪崩(非严格),因此输入中的微小变化会使输出发生很大变化,使其看起来是随机的:

const cyrb53 = function(str, seed = 0) {
    let h1 = 0xdeadbeef ^ seed, h2 = 0x41c6ce57 ^ seed;
    for (let i = 0, ch; i < str.length; i++) {
        ch = str.charCodeAt(i);
        h1 = Math.imul(h1 ^ ch, 2654435761);
        h2 = Math.imul(h2 ^ ch, 1597334677);
    }
    h1 = Math.imul(h1 ^ h1>>>16, 2246822507) ^ Math.imul(h2 ^ h2>>>13, 3266489909);
    h2 = Math.imul(h2 ^ h2>>>16, 2246822507) ^ Math.imul(h1 ^ h1>>>13, 3266489909);
    return 4294967296 * (2097151 & h2) + (h1>>>0);
};

您还可以为相同输入的备用流提供种子:

0xc2ba782c97901 = cyrb53("a")
0xeda5bc254d2bf = cyrb53("b")
0xe64cc3b748385 = cyrb53("revenge")
0xd85148d13f93a = cyrb53("revenue")

从技术上讲,它是64位散列,但JavaScript仅限于53位整数.通过改变十六进制字符串或数组的返回行,仍然可以使用完整的64位:

0xee5e6598ccd5c = cyrb53("revenue", 1)
0x72e2831253862 = cyrb53("revenue", 2)
0x0de31708e6ab7 = cyrb53("revenue", 3)

问题是,构造十六进制字符串成为性能瓶颈,数组需要两个比较运算符而不是一个,这不方便.因此,在将其用于高性能应用程序时请记住这一点.

而且只是为了好玩,这里有89个字符的最小32位散列,仍然比FNV/DJB2/SMDB好:

return (h2>>>0).toString(16).padStart(8,0)+(h1>>>0).toString(16).padStart(8,0);
// or
return [h2>>>0, h1>>>0];

Answer 6

如果它可以帮助任何人,我将前两个答案组合成一个较旧的浏览器容忍版本,如果reduce可用则使用快速版本,如果不是,则使用esmiralha的解决方案.

/**
 * @see http://stackoverflow.com/q/7616461/940217
 * @return {number}
 */
String.prototype.hashCode = function(){
    if (Array.prototype.reduce){
        return this.split("").reduce(function(a,b){a=((a<<5)-a)+b.charCodeAt(0);return a&a},0);              
    } 
    var hash = 0;
    if (this.length === 0) return hash;
    for (var i = 0; i < this.length; i++) {
        var character  = this.charCodeAt(i);
        hash  = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

用法如下:

var hash = new String("some string to be hashed").hashCode();

Answer 7

这是一个精致且性能更好的变体:

String.prototype.hashCode = function() {
    var hash = 0, i = 0, len = this.length;
    while ( i < len ) {
        hash  = ((hash << 5) - hash + this.charCodeAt(i++)) << 0;
    }
    return hash;
};

这与Java的标准实现相匹配 object.hashCode()

这里也只返回正的哈希码:

String.prototype.hashcode = function() {
    return (this.hashCode() + 2147483647) + 1;
};

这是一个匹配的Java,只返回正的哈希码:

public static long hashcode(Object obj) {
    return ((long) obj.hashCode()) + Integer.MAX_VALUE + 1l;
}

请享用!

Answer 8

UUID v3 和 UUID v5 实际上是给定输入字符串的哈希值。

• UUID v3基于MD5，
• UUID v5 基于 SHA-1。

因此，最明显的选择是使用 UUID v5。

幸运的是，有一个流行的 npm 包，其中包含所有 UUID 算法。

npm install uuid

要实际生成 UUID v5，您需要一个唯一的命名空间。这个命名空间就像一个种子，并且应该是一个常量，以确保对于给定的输入，输出始终是相同的。讽刺的是，您应该生成 UUID v4 作为命名空间。最简单的方法是使用一些在线工具。

获得命名空间后，一切就都准备好了。

import { v5 as uuidv5 } from 'uuid';

const MY_NAMESPACE = '1b671a64-40d5-491e-99b0-da01ff1f3341';
const hash = uuidv5('input', MY_NAMESPACE);

例如，如果您的输入字符串始终是 URL，则可以使用一些默认名称空间。

const hashForURL = uuidv5('https://www.w3.org/', uuidv5.URL);

Answer 9

我有点惊讶没有人谈论过新的SubtleCrypto API.

要从字符串中获取哈希值,可以使用以下subtle.digest方法:

function getHash(str, algo = "SHA-256") {
  let strBuf = new TextEncoder('utf-8').encode(str);
  return crypto.subtle.digest(algo, strBuf)
    .then(hash => {
      window.hash = hash;
      // here hash is an arrayBuffer, 
      // so we'll connvert it to its hex version
      let result = '';
      const view = new DataView(hash);
      for (let i = 0; i < hash.byteLength; i += 4) {
        result += ('00000000' + view.getUint32(i).toString(16)).slice(-8);
      }
      return result;
    });
}

getHash('hello world')
  .then(hash => {
    console.log(hash);
  });

Answer 10

这是一个紧凑的 ES6 友好可读片段

const stringHashCode = str => {
  let hash = 0
  for (let i = 0; i < str.length; ++i)
    hash = Math.imul(31, hash) + str.charCodeAt(i)

  return hash | 0
}

Answer 11

多亏了mar10的例子,我找到了一种方法,可以在C#和Javascript中为FNV-1a获得相同的结果.如果存在unicode字符,则为了性能而丢弃上部.不知道为什么在散列时维护它们会有所帮助,因为现在只有散列url路径.

C#版本

private static readonly UInt32 FNV_OFFSET_32 = 0x811c9dc5;   // 2166136261
private static readonly UInt32 FNV_PRIME_32 = 0x1000193;     // 16777619

// Unsigned 32bit integer FNV-1a
public static UInt32 HashFnv32u(this string s)
{
    // byte[] arr = Encoding.UTF8.GetBytes(s);      // 8 bit expanded unicode array
    char[] arr = s.ToCharArray();                   // 16 bit unicode is native .net 

    UInt32 hash = FNV_OFFSET_32;
    for (var i = 0; i < s.Length; i++)
    {
        // Strips unicode bits, only the lower 8 bits of the values are used
        hash = hash ^ unchecked((byte)(arr[i] & 0xFF));
        hash = hash * FNV_PRIME_32;
    }
    return hash;
}

// Signed hash for storing in SQL Server
public static Int32 HashFnv32s(this string s)
{
    return unchecked((int)s.HashFnv32u());
}

JavaScript版本

var utils = utils || {};

utils.FNV_OFFSET_32 = 0x811c9dc5;

utils.hashFnv32a = function (input) {
    var hval = utils.FNV_OFFSET_32;

    // Strips unicode bits, only the lower 8 bits of the values are used
    for (var i = 0; i < input.length; i++) {
        hval = hval ^ (input.charCodeAt(i) & 0xFF);
        hval += (hval << 1) + (hval << 4) + (hval << 7) + (hval << 8) + (hval << 24);
    }

    return hval >>> 0;
}

utils.toHex = function (val) {
    return ("0000000" + (val >>> 0).toString(16)).substr(-8);
}

Answer 12

我参加聚会有点晚了，但你可以使用这个模块：crypto：

const crypto = require('crypto');

const SALT = '$ome$alt';

function generateHash(pass) {
  return crypto.createHmac('sha256', SALT)
    .update(pass)
    .digest('hex');
}

该函数的结果始终是64字符串；像这样："aa54e7563b1964037849528e7ba068eb7767b1fab74a8d80fe300828b996714a"

Answer 13

Jenkins One at a Time Hash非常好：

//Credits (modified code): Bob Jenkins (http://www.burtleburtle.net/bob/hash/doobs.html)
//See also: https://en.wikipedia.org/wiki/Jenkins_hash_function
//Takes a string of any size and returns an avalanching hash string of 8 hex characters.
function jenkinsOneAtATimeHash(keyString)
{
  let hash = 0;
  for (charIndex = 0; charIndex < keyString.length; ++charIndex)
  {
    hash += keyString.charCodeAt(charIndex);
    hash += hash << 10;
    hash ^= hash >> 6;
  }
  hash += hash << 3;
  hash ^= hash >> 11;
  //4,294,967,295 is FFFFFFFF, the maximum 32 bit unsigned integer value, used here as a mask.
  return (((hash + (hash << 15)) & 4294967295) >>> 0).toString(16)
};

例子：

jenkinsOneAtATimeHash('test')
"31c25ec1"
jenkinsOneAtATimeHash('a')
"ca2e9442"
jenkinsOneAtATimeHash('0')
"6e3c5c6b"

您还可以删除.toString(16)末尾的部分来生成数字：

jenkinsOneAtATimeHash2('test')
834821825
jenkinsOneAtATimeHash2('a')
3392050242
jenkinsOneAtATimeHash2('0')
1849449579

请注意，如果您不需要专门对字符串或密钥进行哈希处理，而只需要凭空生成的哈希值，则可以使用：

window.crypto.getRandomValues(new Uint32Array(1))[0].toString(16)

例子：

window.crypto.getRandomValues(new Uint32Array(1))[0].toString(16)
"6ba9ea7"
window.crypto.getRandomValues(new Uint32Array(1))[0].toString(16)
"13fe7edf"
window.crypto.getRandomValues(new Uint32Array(1))[0].toString(16)
"971ffed4"

和上面一样，你可以删除末尾的 `.toString(16) 部分来生成数字：

window.crypto.getRandomValues(new Uint32Array(1))[0]
1154752776
window.crypto.getRandomValues(new Uint32Array(1))[0]
3420298692
window.crypto.getRandomValues(new Uint32Array(1))[0]
1781389127

注意：您还可以使用此方法一次生成多个值，例如：

window.crypto.getRandomValues(new Uint32Array(3))
Uint32Array(3) [ 2050530949, 3280127172, 3001752815 ]

Answer 14

我需要一个类似的函数（但有所不同）来根据用户名和当前时间生成一个唯一的ID。所以：

window.newId = ->
  # create a number based on the username
  unless window.userNumber?
    window.userNumber = 0
  for c,i in window.MyNamespace.userName
    char = window.MyNamespace.userName.charCodeAt(i)
    window.MyNamespace.userNumber+=char
  ((window.MyNamespace.userNumber + Math.floor(Math.random() * 1e15) + new Date().getMilliseconds()).toString(36)).toUpperCase()

产生：

2DVFXJGEKL
6IZPAKFQFL
ORGOENVMG
... etc 

编辑2015年6月：对于新代码，我使用shortid：https：//www.npmjs.com/package/shortid

Answer 15

一种快速简洁的方法，从这里改编而成：

String.prototype.hashCode = function() {
  var hash = 5381, i = this.length
  while(i)
    hash = (hash * 33) ^ this.charCodeAt(--i)
  return hash >>> 0;
}

Answer 16

我基于FNV Multiply+Xor方法的快速（很长）衬垫：

my_string.split('').map(v=>v.charCodeAt(0)).reduce((a,v)=>a+((a<<7)+(a<<3))^v).toString(16);

Answer 17

SubtleCrypto.digest

我没有使用服务器端语言，所以我不能那样做。

你肯定你不能这样做呀？

您是否忘记了您正在使用 Javascript，这是一种不断发展的语言？

试试SubtleCrypto。它支持 SHA-1、SHA-128、SHA-256 和 SHA-512 哈希函数。

async function hash(message/*: string */) {
	const text_encoder = new TextEncoder;
	const data = text_encoder.encode(message);
	const message_digest = await window.crypto.subtle.digest("SHA-512", data);
	return message_digest;
} // -> ArrayBuffer

function in_hex(data/*: ArrayBuffer */) {
	const octets = new Uint8Array(data);
	const hex = [].map.call(octets, octet => octet.toString(16).padStart(2, "0")).join("");
	return hex;
} // -> string

(async function demo() {
	console.log(in_hex(await hash("Thanks for the magic.")));
})();