有没有适用于任何对象类型的哈希码函数？

Question

有没有适用于任何对象类型的哈希码函数？

175

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

set[obj] = true;

这个方法在某种程度上是可行的。对于字符串和数字，它能够很好地工作，但是对于其他对象来说，它们似乎都会“哈希”到相同的值并访问相同的属性。有没有一种方式可以为对象生成唯一的哈希值？字符串和数字是如何实现的，我能否重写相同的行为？

- Boog

34

所有的对象都“哈希”到相同的值的原因是因为你没有重写它们的toString方法。由于键必须是字符串，因此自动调用toString方法以获取有效的键，因此你的所有对象都会转换为相同的默认字符串：“[object Object]”。 - alanning

5

根据问题和目标平台，JSON.stringify(obj)或obj.toSource()可能适合你。 - AnnanFay

6

JSON.stringify(obj)的作用是将整个对象转换为字符串。因此，你实际上只是将对象复制到它自己上面。这是没有意义的，浪费空间且不优化。 - Metalstorm

1

@Metalstorm 确实如此，这就取决于你的问题是什么。当我通过谷歌找到这个问题时，我的最终解决方案是在对象上调用 toSource()。另一种方法只是在源上使用传统哈希。 - AnnanFay

@Annan，顺便说一句，toSource 在 Chrome 上不起作用。 - Pacerier

如果你正在使用node.js，可以访问https://www.npmjs.com/package/object-hash。 - Jason C

20个回答

37

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

或者，您可以维护一个数组来索引所需的对象，并使用其索引字符串作为对该对象的引用。类似于以下示例：

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

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

显然这有点啰嗦，但你可以编写一些方法来处理它，并任意获取和设置。

编辑：

你猜得对 —— 这是 JavaScript 中定义的行为 —— 具体来说，会发生 toString 转换，意味着您可以在对象上定义自己的 toString 函数，该函数将用作属性名称。- olliej

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

- eyelidlessness

另一个选项是为每个对象分配一个随机值作为其哈希 - 可能是随机数+总刻度-然后有一组函数将对象从数组中添加/删除。 - Sugendran

5

如果您添加同一个对象两次，它将会失败。程序会认为这是不同的对象。 - Daniel X Moore

8

我喜欢这个解决方案，因为它不需要在对象中添加任何额外的属性。但是，如果你试图拥有一个干净的垃圾收集器，这就会变得棘手起来。在你的方法中，即使该对象的其他引用已被删除，它仍将被保存。这可能会在更大型的应用程序中导致问题。 - Johnny

44

如果每次引用对象都需要对数组进行线性扫描，那么哈希对象的意义是什么？ - Bordaigorl

这将导致内存泄漏，因为对这些对象的引用将始终保留在该数组中，只要该数组存在，垃圾收集器就不会清理这些对象。 - Dmitry Druganov

显示剩余2条评论

29

最简单的方法是为每个对象提供其自己独特的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的现有对象的条目。

现在我的哈希表非常稳定。我几天前还发布了一篇关于这个确切主题的博客文章。

- Daniel X Moore

30

但这样做忽略了整个重点。Java有 equals() 和 hashCode()，以便于两个相等的对象具有相同的哈希值。使用上述方法意味着每个 MyObject 的实例都将有一个唯一的字符串，这意味着您将不得不保留对该对象的引用才能从映射中检索正确的值。拥有键是无意义的，因为它与对象的唯一性无关。必须为作为键使用的特定类型的对象实现一个有用的 toString() 函数。 - sethro

@sethro，你可以实现对象的 toString 方法，使其直接映射到等价关系，从而当两个对象被视为“相等”时，它们创建相同的字符串。 - Daniel X Moore

3

是的，这是唯一正确的使用 toString() 的方法，以允许将一个 Object 用作 Set。我认为我误解了你的回答，试图提供一种通用的解决方案，避免按情况逐个编写类似于equals()或hashCode()的toString()等效方法。 - sethro

3

下投票了。这不是一个哈希码，详见我对以下问题的回答：https://dev59.com/jXVC5IYBdhLWcg3wvT_g#14953738，以及真正实现哈希码的方法：https://dev59.com/jXVC5IYBdhLWcg3wvT_g#15868654。 - Metalstorm

6

这个问题并不是在询问“真正”的哈希码，而是如何在JavaScript中成功地使用一个对象作为集合。 - Daniel X Moore

显示剩余2条评论

26

你所描述的内容被Harmony WeakMaps所覆盖，这是ECMAScript 6规范（JavaScript的下一版本）的一部分。也就是说，它是一个可以拥有任何键（包括undefined）且不可枚举的集合。

这意味着，除非您拥有直接链接到它的关键字（任何对象！）的引用，否则无法获得对值的引用。这对于许多与引擎实现相关的效率和垃圾收集问题非常重要，但它也非常酷，因为它允许新的语义，例如可撤销的访问权限和在不暴露数据发送方情况下传递数据。

来自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中可用。它们也支持Node v7，在v6中需要使用--harmony-weak-maps标志。

- user748221

1

这些和 Map 有什么区别？ - smac89

@smac89 WeakMap 有其限制： 1）只能使用对象作为键 2）没有 size 属性 3）没有迭代器或 forEach 方法 4）没有 clear 方法。键是对象 - 因此当该对象从内存中删除时，与该对象相关联的 WeakMap 数据也将被删除。当我们想要保留仅在对象存在时才存在的信息时，这非常有用。因此，WeakMap 只有 set、delete 写入方法和 get、has 读取方法。 - Ekaterina Tokareva

这并不完全正确... var m = new Map();m.set({},"abc"); console.log(m.get({}) //=>undefined 只有在您在set命令中最初引用的变量相同时才有效。例如 var m = new Map();a={};m.set(a,"abc"); console.log(m.get(a) //=>undefined - Sancarn

1

@Sancarn 不一定要是同一个变量，但它们必须指向同一个对象。在你的第一个例子中，你有两个不同的对象，它们看起来相同，但它们有不同的地址。 - Svish

18

我选择的解决方案与Daniel的类似，但是不使用对象工厂和重写toString，而是在首次通过getHashCode函数请求对象时显式地将哈希添加到对象中。有点混乱，但更适合我的需求 :)

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

- theGecko

9

如果你想这样做，最好使用Object.defineProperty来设置hashCode，并将enumerable设置为false，这样可以避免在for .. in循环中出现崩溃。 - Sebastian Nowak

16

对于我的具体情况，我只关心对象的键和基本值的相等性。对我有效的解决方案是将对象转换为其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
// }

- ijmacd

11

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

用法:

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

- Metalstorm

JavaScript的GC也会在循环引用时出现问题吗？ - Clayton Rabenda

@Ryan Long，我可能会说，如果你有循环引用，那么你需要重构你的代码 ;) - Metalstorm

13

“那么你需要重构你的代码。” 你在开玩笑吧？每个DOM元素的父子对都构成了一个循环引用。 - Chris Middleton

9

它在对具有数字属性的对象进行哈希处理时表现不佳，在许多情况下返回相同的值，例如 var hash1 = Hashcode.value({ a: 1, b: 2 }); var hash2 = Hashcode.value({ a: 2, b: 1 }); console.log(hash1, hash2); 将记录 2867874173 2867874173。 - Julien Bérubé

9

在ECMAScript 6中，现在有一个Set，它可以按照您的期望工作：https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set。它已经在最新版本的Chrome、FF和IE11中可用。

- Daniel X Moore

1

这应该是2016年的最佳答案。如果您使用Babel，可以按照ES6规范使用Set，并且它将自动在ES5输出中进行填充。https://babeljs.io/docs/learn-es2015/#map-set-weak-map-weak-set - atroberts20

1

我不认为这是一个有效的答案或解决了OP的问题，因为JS集合不允许对象实现哈希码函数。请考虑以下代码：const set = new Set();set.add({a:1});set.add({a:1});set.size // <--- 这个结果是2，而不是1。 - lance.dolan

8

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

myObject[myProperty] = ...;

是同义词

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

这是必要的，因为在JavaScript中

myObject["someProperty"]

是相同的意思

myObject.someProperty

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

- olliej

7

根据标题，我们可以在浏览器上下文中生成强大的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

转换摘要为十六进制字符串

然而，对于一个仅用于避免碰撞的简单快速校验和哈希函数，请参考CRC32（内容冗余检查）

JavaScript CRC32

您可能还会对这种类似于通过 Web Crypto API 生成 HMAC 码的方法感兴趣。

- NVRM

1

请注意，这仅适用于HTTPS。WebCrypto规范明确指出，在不安全的上下文（即http）中，webcrypto为“未定义”。 - Gautham C.

这真的很酷，但是在旧版浏览器中不支持它。 - dovidweisz

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- KimKha · Accepted Answer

如果你想在JavaScript中拥有类似Java的hashCode()函数，那么这就是你需要的：

function hashCode(string){
    var hash = 0;
    for (var i = 0; i < string.length; i++) {
        var code = string.charCodeAt(i);
        hash = ((hash<<5)-hash)+code;
        hash = hash & hash; // Convert to 32bit integer
    }
    return hash;
}

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

请注意，hashCode可能为正数也可能为负数，这是正常的，参见HashCode giving negative values。因此，您可以考虑在此函数中使用Math.abs()。