JavaScript 中是否有任何类型的哈希码函数?

IT技术 javascript hash set hashcode
2021-03-14 13:49:05

基本上,我试图创建一个由独特对象组成的对象,一个集合。我有一个绝妙的主意,就是将 JavaScript 对象与属性名称的对象一起使用。如,

set[obj] = true;

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

6个回答

如果你想要一个像 JavaScript 中的 Java 那样的 hashCode() 函数,那就是你的:

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()与此功能一起使用。

@qodeninja 和 @szeryf:你只需要小心使用它。例如,我试图pickOne["helloo".hashCode() % 20]为一个pickOne有 20 个元素的数组我得到undefined是因为哈希码是负数,所以这是一个例子,其中有人(我)隐含地假设了正哈希码。
2021-04-30 13:49:05
@KimKhachar是 JS 中的保留字,可能会导致一些问题。其他的名字会更好。
2021-05-02 13:49:05
这会创建 -hash,并不完美
2021-05-03 13:49:05
@qdeninja 说谁?这是我第一次听到这样的说法。你能链接到一些来源吗?散列通常使用固定大小的整数算术和位运算来计算,因此得到正或负结果是可以预料的。
2021-05-07 13:49:05
挑剔,但是……“如果(this.length == 0)返回哈希值;” 是多余的 :) 并且会亲自将“字符”更改为“代码”。
2021-05-19 13:49:05

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

或者,您可以维护一个数组来索引相关对象,并使用其索引字符串作为对对象的引用。像这样的东西:

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

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

显然它有点冗长,但是您可以编写一些方法来处理它,并且可以随意获取和设置所有内容。

编辑:

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

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

“如果你将同一个对象添加两次,这将失败。它会认为它是不同的。” 好点子。一个解决方案可能是为 ObjectReference 将 Array 子类化,将重复检查挂钩到 push() 中。我现在没有时间编辑这个解决方案,但我希望我以后会记得。
2021-04-23 13:49:05
我喜欢这个解决方案,因为它不需要对象中的任何附加属性。但是,如果您尝试使用干净的垃圾收集器,就会出现问题。在您的方法中,它会保存该对象,尽管它的其他引用已被删除。这可能会导致更大的应用程序出现问题。
2021-04-28 13:49:05
如果每次引用对象时都需要对数组进行线性扫描,那么对对象进行散列有什么意义呢?
2021-04-28 13:49:05
另一种选择是给每个对象一个随机值,因为它是散列 - 可能是一个随机数 + 总滴答声 - 然后有一组函数来从数组中添加/删除对象。
2021-05-10 13:49:05
如果您两次添加相同的对象,这将失败。它会认为它是不同的。
2021-05-15 13:49:05

最简单的方法是为每个对象赋予自己独特的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 的退出对象的条目。

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

@Metalstorm 问题不是询问“真实”哈希码,而是如何在 JavaScript 中成功使用对象作为集合。
2021-04-27 13:49:05
但这没有抓住重点。Java 具有equals()并且,hashCode()因此两个等效对象具有相同的散列值。使用上述方法意味着 的每个实例都MyObject将有一个唯一的字符串,这意味着您必须保留对该对象的引用才能从映射中检索正确的值。拥有键是没有意义的,因为它与对象的唯一性无关。toString()需要为您用作键的特定类型的对象实现一个有用的功能。
2021-04-28 13:49:05
投了赞成票。这不是哈希码,请参阅我对以下问题的回答:stackoverflow.com/a/14953738/524126以及哈希码的真实实现:stackoverflow.com/a/15868654/524126
2021-05-01 13:49:05
@sethro 您可以toString为对象实现,使其直接映射到等价关系,以便两个对象创建相同的字符串,如果它们被视为“相等”。
2021-05-06 13:49:05
没错,那就是只有用正确的方法toString(),让你使用一个Object作为Set我想我误解了你的答案,因为我试图提供一个通用的解决方案,以避免编写toString()等效的equals()hashCode()逐案的。
2021-05-19 13:49:05

您描述的内容包含在 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 中可用。它们在 Node v7 和带有--harmony-weak-maps标志的v6 中也受支持

这并不能完全正确地工作......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
2021-05-02 13:49:05
这些和 有Map什么区别
2021-05-06 13:49:05
@Sancarn它不必是同一个变量,但它们必须指向同一个对象。在您的第一个示例中,您有两个不同的对象,它们看起来相同,但它们的地址不同。
2021-05-18 13:49:05
@smac89 WeakMap 有局限性:1) 仅将对象作为键 2) 没有大小属性​​ 3) 没有迭代器或 forEach 方法 4) 没有明确的方法。键是对象 - 因此当对象将从内存中删除时 - 来自与该对象连接的 WeakMap 的数据也将被删除。当我们想要保留信息时它非常有用,这些信息应该只在对象存在时才存在。所以 WeakMap 只有方法:set, delete for write 和 get, has for read
2021-05-21 13:49:05

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

Function.prototype.getHashCode = (function(id) {
    return function() {
        if (!this.hashCode) {
            this.hashCode = '<hash|#' + (id++) + '>';
        }
        return this.hashCode;
    }
}(0));
如果你想要走这条路,这是更好的通过设置的hashCodeObject.definePropertyenumerable设置为false,这样你就不会崩溃任何for .. in循环。
2021-05-13 13:49:05