javascript - JavaScript中是否有任何类型的哈希码函数？

Question

基本上，我正在尝试创建一个独特对象的对象，一个集合。我有一个绝妙的想法，就是使用带有对象作为属性名称的 JavaScript 对象。如，

set[obj] = true;

这在一定程度上有效。它适用于字符串和数字，但对于其他对象，它们似乎都“散列”到相同的值并访问相同的属性。有什么方法可以为对象生成唯一的哈希值吗？字符串和数字是如何做到的，我可以覆盖相同的行为吗？

score 69 · Accepted Answer

如果你想要一个 hashCode() 函数，比如 JavaScript 中的 Java，那就是你的：

String.prototype.hashCode = function(){
    var hash = 0;
    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;
}

这就是Java（按位运算符）中的实现方式。

请注意，hashCode 可以是正数和负数，这很正常，请参阅HashCode 给出负值。因此，您可以考虑Math.abs()与此功能一起使用。

score 36 · Accepted Answer

JavaScript 对象只能使用字符串作为键（其他任何东西都被转换为字符串）。

或者，您可以维护一个对相关对象进行索引的数组，并将其索引字符串用作对该对象的引用。像这样的东西：

var ObjectReference = [];
ObjectReference.push(obj);

set['ObjectReference.' + ObjectReference.indexOf(obj)] = true;

显然它有点冗长，但您可以编写几个方法来处理它并随意获取和设置所有内容。

编辑：

您的猜测是事实——这是 JavaScript 中定义的行为——特别是发生了 toString 转换，这意味着您可以在将用作属性名称的对象上定义自己的 toString 函数。- 奥利耶

这带来了另一个有趣的观点；您可以在要散列的对象上定义一个 toString 方法，这可以形成它们的散列标识符。

score 30 · Accepted Answer

最简单的方法是为每个对象赋予其独特的toString方法：

(function() {
    var id = 0;

    /*global MyObject */
    MyObject = function() {
        this.objectId = '<#MyObject:' + (id++) + '>';
        this.toString= function() {
            return this.objectId;
        };
    };
})();

我遇到了同样的问题，这对我来说完美地解决了它，而且几乎没有大惊小怪，并且比重新实现一些肥胖的 Java 风格Hashtable并添加equals()和添加hashCode()到您的对象类要容易得多。只需确保您没有将字符串 '<#MyObject:12> 粘贴到您的哈希中，否则它将清除具有该 ID 的现有对象的条目。

现在我所有的哈希都完全变冷了。几天前我也刚刚发布了一篇关于这个确切主题的博客文章。

score 23 · Accepted Answer

Harmony WeakMaps涵盖了您所描述的内容，它是ECMAScript 6规范（JavaScript 的下一个版本）的一部分。那就是：一个集合，其中的键可以是任何东西（包括未定义的）并且是不可枚举的。

这意味着除非您直接引用链接到它的键（任何对象！），否则不可能获得对值的引用。这对于与效率和垃圾收集相关的一系列引擎实现原因很重要，但它也非常酷，因为它允许新的语义，如可撤销的访问权限和传递数据而不暴露数据发送者。

来自MDN：

var wm1 = new WeakMap(),
    wm2 = new WeakMap();
var o1 = {},
    o2 = function(){},
    o3 = window;

wm1.set(o1, 37);
wm1.set(o2, "azerty");
wm2.set(o1, o2); // A value can be anything, including an object or a function.
wm2.set(o3, undefined);
wm2.set(wm1, wm2); // Keys and values can be any objects. Even WeakMaps!

wm1.get(o2); // "azerty"
wm2.get(o2); // Undefined, because there is no value for o2 on wm2.
wm2.get(o3); // Undefined, because that is the set value.

wm1.has(o2); // True
wm2.has(o2); // False
wm2.has(o3); // True (even if the value itself is 'undefined').

wm1.has(o1);   // True
wm1.delete(o1);
wm1.has(o1);   // False

WeakMaps 在当前的 Firefox、Chrome 和 Edge 中可用。--harmony-weak-mapsNode v7 和带有标志的 v6 也支持它们。

score 18 · Accepted Answer

我选择的解决方案类似于 Daniel 的解决方案，但我没有使用对象工厂并覆盖 toString，而是在第一次通过 getHashCode 函数请求对象时显式地将哈希添加到对象中。有点乱，但更适合我的需要:)

Function.prototype.getHashCode = (function(id) {
    return function() {
        if (!this.hashCode) {
            this.hashCode = '<hash|#' + (id++) + '>';
        }
        return this.hashCode;
    }
}(0));

score 16 · Accepted Answer

对于我的具体情况，我只关心键和原始值的对象是否相等。对我有用的解决方案是将对象转换为其 JSON 表示并将其用作哈希。存在键定义顺序可能不一致等限制；但就像我说的那样，它对我有用，因为这些对象都是在一个地方生成的。

var hashtable = {};

var myObject = {a:0,b:1,c:2};

var hash = JSON.stringify(myObject);
// '{"a":0,"b":1,"c":2}'

hashtable[hash] = myObject;
// {
//   '{"a":0,"b":1,"c":2}': myObject
// }

score 10 · Accepted Answer

不久前我组装了一个小的 JavaScript 模块来为字符串、对象、数组等生成哈希码（我刚刚将它提交到GitHub :)）

用法：

Hashcode.value("stackoverflow")
// -2559914341
Hashcode.value({ 'site' : "stackoverflow" })
// -3579752159

score 9 · Accepted Answer

在 ECMAScript 6 中，现在有一个Set可以按照您的方式工作：https ://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

它已经在最新的 Chrome、FF 和 IE11 中可用。

score 8 · Accepted Answer

JavaScript 规范将索引属性访问定义为对索引名称执行 toString 转换。例如，

myObject[myProperty] = ...;

是相同的

myObject[myProperty.toString()] = ...;

这是必需的，就像在 JavaScript 中一样

myObject["someProperty"]

是相同的

myObject.someProperty

是的，这也让我很难过:-(

score 6 · Accepted Answer

根据标题，我们可以生成强SHA哈希，在浏览器上下文中，它可以用于从对象、参数数组、字符串或其他任何内容生成唯一哈希。

async function H(m) {
  const msgUint8 = new TextEncoder().encode(m)                       
  const hashBuffer = await crypto.subtle.digest('SHA-256', msgUint8)          
  const hashArray = Array.from(new Uint8Array(hashBuffer))                    
  const hashHex = hashArray.map(b => b.toString(16).padStart(2, '0')).join('')
  console.log(hashHex)
}

/* Examples ----------------------- */
H("An obscure ....")
H(JSON.stringify( {"hello" : "world"} ))
H(JSON.stringify( [54,51,54,47] ))

我的浏览器中的上述输出，对你来说也应该是相等的：

bf1cf3fe6975fe382ab392ec1dd42009380614be03d489f23601c11413cfca2b
93a23971a914e5eacbf0a8d25154cda309c3c1c72fbb9914d47c60f3cb681588
d2f209e194045604a3b15bdfd7502898a0e848e4603c5a818bd01da69c00ad19

支持的算法：

SHA-1 (but don't use this in cryptographic applications)
SHA-256
SHA-384
SHA-512

https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/digest#Converting_a_digest_to_a_hex_string

但是，对于一个简单的 FAST 校验和哈希函数，仅用于避免冲突，请参阅CRC32（内容冗余检查）

JavaScript CRC32

您可能也对这种通过 web crypto api生成 HMAC 代码的类似方法感兴趣。

score 4 · Accepted Answer

参考：https ://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Symbol

您可以使用 Es6 符号创建唯一键和访问对象。从 Symbol() 返回的每个符号值都是唯一的。符号值可以用作对象属性的标识符；这是数据类型的唯一用途。

var obj = {};

obj[Symbol('a')] = 'a';
obj[Symbol.for('b')] = 'b';
obj['c'] = 'c';
obj.d = 'd';

score 2 · Accepted Answer

这是我返回唯一整数的简单解决方案。

function hashcode(obj) {
    var hc = 0;
    var chars = JSON.stringify(obj).replace(/\{|\"|\}|\:|,/g, '');
    var len = chars.length;
    for (var i = 0; i < len; i++) {
        // Bump 7 to larger prime number to increase uniqueness
        hc += (chars.charCodeAt(i) * 7);
    }
    return hc;
}

score 1 · Accepted Answer

Object我的解决方案为全局对象引入了一个静态函数。

(function() {
    var lastStorageId = 0;

    this.Object.hash = function(object) {
        var hash = object.__id;

        if (!hash)
             hash = object.__id = lastStorageId++;

        return '#' + hash;
    };
}());

我认为这与 JavaScript 中的其他对象操作函数更方便。

score 1 · Accepted Answer

我会尝试比其他答案更深入一点。

即使 JS 有更好的散列支持，它也不会神奇地完美地散列所有内容，在许多情况下，您必须定义自己的散列函数。例如 Java 有很好的散列支持，但你仍然需要思考和做一些工作。

一个问题是散列/散列码这个术语……有加密散列和非加密散列。另一个问题是您必须了解散列为什么有用以及它是如何工作的。

当我们谈论 JavaScript 或 Java 中的散列时，大部分时间我们都在谈论非加密散列，通常是关于 hashmap/hashtable 的散列（除非我们正在处理身份验证或密码，您可以使用 NodeJS 在服务器端进行。 ..)。

这取决于您拥有什么数据以及您想要实现什么。

您的数据具有一些自然的“简单”独特性：

整数的散列是......整数，因为它是唯一的，你很幸运！
字符串的散列......它取决于字符串，如果字符串表示唯一标识符，您可以将其视为散列（因此不需要散列）。
任何间接几乎是唯一整数的东西都是最简单的情况
这将尊重：如果对象相等，则哈希码相等

您的数据具有一些自然的“复合”独特性：

例如，对于 person 对象，您可以使用 firstname、lastname、birthdate 来计算散列……看看 Java 是如何做到的：Good Hash Function for Strings，或者使用其他一些对您的用例来说足够便宜且足够独特的 ID 信息

您不知道您的数据将是什么：

祝你好运……您可以序列化为字符串并对其进行 Java 风格的哈希处理，但如果字符串很大并且它不会避免冲突以及说整数（自身）的哈希值，这可能会很昂贵。

对于未知数据没有神奇的高效散列技术，在某些情况下很容易，在其他情况下你可能需要三思而后行。所以即使 JavaScript/ECMAScript 增加了更多的支持，也没有什么神奇的语言可以解决这个问题。

在实践中你需要两件事：足够的独特性，足够的速度

除此之外，它很棒：“如果对象相等，哈希码相等”

score 1 · Accepted Answer

只需将隐藏的秘密属性与defineProperty enumerable: false

它工作得非常快：

首次读取uniqueId：1,257,500 ops/s
所有其他：309,226,485 次操作/秒

var nextObjectId = 1
function getNextObjectId() {
    return nextObjectId++
}

var UNIQUE_ID_PROPERTY_NAME = '458d576952bc489ab45e98ac7f296fd9'
function getObjectUniqueId(object) {
    if (object == null) {
        return null
    }

    var id = object[UNIQUE_ID_PROPERTY_NAME]

    if (id != null) {
        return id
    }

    if (Object.isFrozen(object)) {
        return null
    }

    var uniqueId = getNextObjectId()
    Object.defineProperty(object, UNIQUE_ID_PROPERTY_NAME, {
        enumerable: false,
        configurable: false,
        writable: false,
        value: uniqueId,
    })

    return uniqueId
}

score 0 · Accepted Answer

如果您真的想要设置行为（我将根据 Java 知识进行说明），那么您将很难在 JavaScript 中找到解决方案。大多数开发人员会推荐一个唯一的键来表示每个对象，但这与 set 不同，因为您可以获得两个相同的对象，每个对象都有一个唯一的键。Java API 通过比较哈希码值而不是键来检查重复值，并且由于 JavaScript 中没有对象的哈希码值表示，因此几乎不可能做同样的事情。甚至 Prototype JS 库也承认了这个缺点，当它说：

“哈希可以被认为是一个关联数组，将唯一键绑定到值（不一定是唯一的）......”

http://www.prototypejs.org/api/hash

score 0 · Accepted Answer

除了 eyelidlessness 的答案之外，这里还有一个函数，它为任何对象返回一个可重现的、唯一的 ID：

var uniqueIdList = [];
function getConstantUniqueIdFor(element) {
    // HACK, using a list results in O(n), but how do we hash e.g. a DOM node?
    if (uniqueIdList.indexOf(element) < 0) {
        uniqueIdList.push(element);
    }
    return uniqueIdList.indexOf(element);
}

正如您所看到的，它使用一个非常低效的查找列表，但这是我现在能找到的最好的。

score 0 · Accepted Answer

如果你想使用对象作为键，你需要覆盖它们的 toString 方法，正如这里已经提到的一些。使用的散列函数都很好，但它们只适用于相同的对象，而不适用于相等的对象。

我编写了一个从对象创建散列的小型库，您可以轻松地将其用于此目的。对象甚至可以有不同的顺序，哈希值是相同的。在内部，您可以为哈希使用不同的类型（djb2、md5、sha1、sha256、sha512、ripemd160）。

这是文档中的一个小示例：

var hash = require('es-hash');

// Save data in an object with an object as a key
Object.prototype.toString = function () {
    return '[object Object #'+hash(this)+']';
}

var foo = {};

foo[{bar: 'foo'}] = 'foo';

/*
 * Output:
 *  foo
 *  undefined
 */
console.log(foo[{bar: 'foo'}]);
console.log(foo[{}]);

该包可以在浏览器和 Node-Js 中使用。

存储库：https ://bitbucket.org/tehrengruber/es-js-hash

score 0 · Accepted Answer

如果您想在查找对象中具有唯一值，您可以执行以下操作：

创建查找对象

var lookup = {};

设置哈希码函数

function getHashCode(obj) {
    var hashCode = '';
    if (typeof obj !== 'object')
        return hashCode + obj;
    for (var prop in obj) // No hasOwnProperty needed
        hashCode += prop + getHashCode(obj[prop]); // Add key + value to the result string
    return hashCode;
}

目的

var key = getHashCode({ 1: 3, 3: 7 });
// key = '1337'
lookup[key] = true;

大批

var key = getHashCode([1, 3, 3, 7]);
// key = '01132337'
lookup[key] = true;

其他类型

var key = getHashCode('StackOverflow');
// key = 'StackOverflow'
lookup[key] = true;

最后结果

{ 1337: true, 01132337: true, StackOverflow: true }

请注意，getHashCode当对象或数组为空时不返回任何值

getHashCode([{},{},{}]);
// '012'
getHashCode([[],[],[]]);
// '012'

这类似于@ijmacd 解决方案，只是getHashCode没有JSON依赖关系。

score 0 · Accepted Answer

我结合了眼睑和 KimKha 的答案。

下面是一个 angularjs 服务，它支持数字、字符串和对象。

exports.Hash = () => {
  let hashFunc;
  function stringHash(string, noType) {
    let hashString = string;
    if (!noType) {
      hashString = `string${string}`;
    }
    var hash = 0;
    for (var i = 0; i < hashString.length; i++) {
        var character = hashString.charCodeAt(i);
        hash = ((hash<<5)-hash)+character;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
  }

  function objectHash(obj, exclude) {
    if (exclude.indexOf(obj) > -1) {
      return undefined;
    }
    let hash = '';
    const keys = Object.keys(obj).sort();
    for (let index = 0; index < keys.length; index += 1) {
      const key = keys[index];
      const keyHash = hashFunc(key);
      const attrHash = hashFunc(obj[key], exclude);
      exclude.push(obj[key]);
      hash += stringHash(`object${keyHash}${attrHash}`, true);
    }
    return stringHash(hash, true);
  }

  function Hash(unkType, exclude) {
    let ex = exclude;
    if (ex === undefined) {
      ex = [];
    }
    if (!isNaN(unkType) && typeof unkType !== 'string') {
      return unkType;
    }
    switch (typeof unkType) {
      case 'object':
        return objectHash(unkType, ex);
      default:
        return stringHash(String(unkType));
    }
  }

  hashFunc = Hash;

  return Hash;
};

示例用法：

Hash('hello world'), Hash('hello world') == Hash('hello world')
Hash({hello: 'hello world'}), Hash({hello: 'hello world'}) == Hash({hello: 'hello world'})
Hash({hello: 'hello world', goodbye: 'adios amigos'}), Hash({hello: 'hello world', goodbye: 'adios amigos'}) == Hash({goodbye: 'adios amigos', hello: 'hello world'})
Hash(['hello world']), Hash(['hello world']) == Hash(['hello world'])
Hash(1), Hash(1) == Hash(1)
Hash('1'), Hash('1') == Hash('1')

输出

432700947 true
-411117486 true
1725787021 true
-1585332251 true
1 true
-1881759168 true

解释

如您所见，该服务的核心是由 KimKha 创建的哈希函数。我已将类型添加到字符串中，以便对象的结构也会影响最终的哈希值。对键进行哈希处理以防止数组|对象冲突。

eyelidlessness 对象比较用于防止自引用对象的无限递归。

用法

我创建了这个服务，以便我可以使用对象访问错误服务。这样一个服务可以注册一个给定对象的错误，另一个可以确定是否发现了任何错误。

IE

JsonValidation.js

ErrorSvc({id: 1, json: '{attr: "not-valid"}'}, 'Invalid Json Syntax - key not double quoted');

UserOfData.js

ErrorSvc({id: 1, json: '{attr: "not-valid"}'});

这将返回：

['Invalid Json Syntax - key not double quoted']

尽管

ErrorSvc({id: 1, json: '{"attr": "not-valid"}'});

这将返回

[]

javascript - JavaScript中是否有任何类型的哈希码函数？

20 回答 20

Related

Reference