JavaScript中是否有某种哈希码函数?

2020/11/11 00:23 · javascript ·  · 0评论

基本上,我试图创建一个具有唯一对象的对象,即一个集合。我有一个绝妙的主意,就是仅将JavaScript对象与属性名称的对象一起使用。如,

set[obj] = true;

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

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

或者,您可以维护一个数组,该数组为有问题的对象建立索引,并将其索引字符串用作对该对象的引用。像这样:

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

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

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

编辑:

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

这带来了另一个有趣的观点。您可以在要哈希的对象上定义toString方法,该方法可以构成其哈希标识符。

如果您想要像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()与此功能一起使用。

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

现在我所有的哈希值都变得很冷。几天前,我也刚刚发布了一篇有关该确切主题的博客文章

您描述的内容已包含ECMAScript 6规范(JavaScript的下一个版本)的一部分Harmony WeakMaps中也就是说:一组键,键可以是任何值(包括未定义),并且是不可枚举的。

这意味着除非您直接引用链接到该键的键(任何对象!),否则无法获得对值的引用。对于许多与效率和垃圾收集有关的引擎实现原因而言,这一点很重要,但是它也非常酷,因为它允许新的语义(例如可撤销的访问权限和传递数据)而不暴露数据发送者。

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标志的它们。

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

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

对于我的特定情况,我只关心键和基元值的对象相等性。对我有用的解决方案是将对象转换为其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
// }

不久前,我组合了一个小的JavaScript模块,以生成字符串,对象,数组等的哈希码。(我刚刚将其提交给GitHub :))

用法:

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

在ECMAScript 6中,现在有一个可以满足Set您的需求的工具:https : //developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Set

最新的Chrome,FF和IE11中已经提供了该功能。

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

myObject[myProperty] = ...;

是相同的

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

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

myObject["someProperty"]

是相同的

myObject.someProperty

是的,这也让我难过:-(

参考:https : //developer.mozilla.org/zh-CN/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';

基于标题,我们可以在浏览器上下文中生成强大的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/zh-CN/docs/Web/API/SubtleCrypto/digest#Converting_a_digest_to_a_hex_string

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

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;
}

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

(function() {
    var lastStorageId = 0;

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

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

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

我认为这与JavaScript中的其他对象操纵函数比较方便。

我将尝试比其他答案更深入。

即使JS拥有更好的哈希支持,它也无法完美地对所有内容进行神奇的哈希处理,在许多情况下,您将必须定义自己的哈希函数。例如,Java具有良好的哈希支持,但是您仍然必须考虑并做一些工作。

一个问题是术语“哈希/哈希码”……存在加密哈希和非加密哈希。另一个问题是,您必须了解哈希为何有用以及它如何工作。

大多数时候,当我们谈论JavaScript或Java中的哈希时,我们谈论的是非加密哈希,通常是关于hashmap / hashtable的哈希(除非我们正在处理身份验证或密码,您可以使用NodeJS在服务器端进行此操作)。 ..)。

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

您的数据具有一些自然的“简单”唯一性:

  • 整数的哈希值是……整数,因为它是唯一的,所以很幸运!
  • 字符串的哈希值...取决于字符串,如果字符串表示唯一标识符,则可以将其视为哈希值(因此不需要哈希值)。
  • 间接地是唯一整数的任何事物都是最简单的情况
  • 这将遵守:如果对象相等,则哈希码相等

您的数据具有一些自然的“复合”唯一性:

  • 例如,对于一个人员对象,您可以使用名字,姓氏,生日等来计算哈希值……参见Java的工作原理:String的良好哈希函数,或使用其他一些ID信息,这些信息对于您的用例而言足够便宜且独特

您不知道您的数据是什么:

  • 祝您好运...您可以序列化为字符串并以Java样式对其进行哈希处理,但是如果字符串很大并且无法避免冲突(比如说整数(自身)的哈希),则可能会很昂贵。

对于未知数据,没有魔术般有效的哈希技术,在某些情况下,这很容易,在其他情况下,您可能需要三思而后行。因此,即使JavaScript / ECMAScript添加了更多支持,也没有针对该问题的魔术语言解决方案。

实际上,您需要两件事:足够的独特性,足够的速度

除此之外,它还很棒:“如果对象相等,则哈希码相等”

如果您确实想要设置行为(我掌握Java知识),那么将很难在JavaScript中找到解决方案。大多数开发人员会建议一个唯一的键来表示每个对象,但这与set不同,因为您可以获得两个相同的对象,每个对象都有一个唯一的键。Java API通过比较哈希码值而不是键来完成检查重复值的工作,并且由于JavaScript中没有对象的哈希码值表示,因此几乎不可能做到这一点。即使是Prototype JS库,它也指出了这一缺点:

“哈希可以看作是一个关联数组,将唯一键绑定到值(不一定是唯一的)……”

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

除了可以解决失明问题之外,以下函数还可以为任何对象返回可重现的唯一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);
}

如您所见,它使用查找列表非常低效,但是这是我目前能找到的最好的列表。

如果要将对象用作键,则需要覆盖其toString方法,如此处已提到的那样。使用的哈希函数都很好,但是它们仅适用于相同的对象,而不适用于相等的对象。

我编写了一个小型库,该库从对象创建哈希,您可以轻松地将其用于此目的。对象甚至可以具有不同的顺序,散列将相同。在内部,您可以对哈希使用不同的类型(djb2,md5,sha1,sha256,sha512,tripmd160)。

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

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-J中使用。

仓库:https : //bitbucket.org/tehrengruber/es-js-hash

如果要在查找对象中具有唯一值,可以执行以下操作:

创建一个查找对象

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依赖性。

我结合了双眼失明和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创建的哈希函数。我在字符串中添加了类型,以便对象的构造也将影响最终的哈希值。对键进行哈希处理以防止数组冲突。

眼睑失明的对象比较用于通过自引用对象来防止无限递归。

用法

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

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"}'});

这将返回

[]

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

它工作非常快

  • 首次读取的uniqueId1,257,500 ops / s
  • 所有其他:309,226,485 ops / s
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
}
本文地址:http://javascript.askforanswer.com/javascriptzhongshifouyoumouzhonghaximahanshu.html
文章标签: ,   ,   ,  
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!