Есть ли какая-либо функция хэш-кода в JavaScript?
По сути, я пытаюсь создать объект из уникальных объектов, набор. У меня была блестящая идея просто использовать объект JavaScript с объектами для имен свойств. Такие как,
set[obj] = true;
Это работает, до определенного момента. Он отлично работает со строками и числами, но с другими объектами все они, похоже, "хэшируют" одно и то же значение и имеют доступ к одному и тому же свойству. Есть ли какой-то способ, которым я могу сгенерировать уникальное хеш-значение для объекта? Как строки и числа делают это, я могу переопределить то же самое поведение?
21 ответ
Объекты JavaScript могут использовать только строки в качестве ключей (все остальное преобразуется в строку).
В качестве альтернативы вы можете поддерживать массив, который индексирует рассматриваемые объекты, и использовать его индексную строку в качестве ссылки на объект. Что-то вроде этого:
var ObjectReference = [];
ObjectReference.push(obj);
set['ObjectReference.' + ObjectReference.indexOf(obj)] = true;
Очевидно, что это немного многословно, но вы могли бы написать пару методов, которые справятся с этим и получат и установят все, что угодно.
Редактировать:
Ваше предположение является фактом - это определенное поведение в JavaScript - в частности, происходит преобразование toString, означающее, что вы можете определить свою собственную функцию toString для объекта, который будет использоваться в качестве имени свойства. - оллидж
Это поднимает еще один интересный момент; Вы можете определить метод toString для объектов, которые вы хотите хэшировать, и это может сформировать их хеш-идентификатор.
Если вам нужна функция hashCode(), такая как Java в JavaScript, она ваша:
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 (побитовый оператор).
Самый простой способ сделать это - дать каждому из ваших объектов свой уникальный 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> в ваш хеш, иначе это сотрет запись для вашего выходящего объекта с этим идентификатором.
Теперь все мои хэши совершенно холодные. Я также только что опубликовал запись в блоге несколько дней назад на эту тему.
То, что вы описали, покрыто 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
Слабые карты доступны в текущих Firefox, Chrome и Edge. Они также поддерживаются в Node v7 и v6 с --harmony-weak-maps флаг.
Решение, которое я выбрал, похоже на решение Дэниела, но вместо того, чтобы использовать фабрику объектов и переопределить 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("stackru")
// -2559914341
Hashcode.value({ 'site' : "stackru" })
// -3579752159
В ECMAScript 6 теперь есть Set это работает так, как вы хотите: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
Он уже доступен в последних версиях Chrome, FF и IE11.
Спецификация JavaScript определяет доступ к индексированным свойствам как выполнение преобразования toString для имени индекса. Например,
myObject[myProperty] = ...;
такой же как
myObject[myProperty.toString()] = ...;
Это необходимо как в JavaScript
myObject["someProperty"]
такой же как
myObject.someProperty
И да, это меня тоже огорчает:-(
Основываясь на заголовке, мы можем генерировать сильные хэши с помощью js, его можно использовать для генерации уникального хэша из объекта, массива параметров, строки или чего-то еще.
Позже для индексации это позволяет избежать любых возможных ошибок сопоставления, позволяя при этом извлекать индекс из параметров (избегайте поиска / зацикливания объекта и т. Д.):
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
https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/digest
Ссылка: 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';
Вот мое простое решение, которое возвращает уникальное целое число.
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;
}
Я объединил ответы от век и КимХа.
Ниже приведен сервис 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"}'});
Это вернется
[]
Я постараюсь пойти немного глубже, чем другие ответы.
Даже если бы у JS была лучшая поддержка хеширования, он не мог бы магически все хешировать, во многих случаях вам придется определять свою собственную хеш-функцию. Например, Java имеет хорошую поддержку хеширования, но вам все еще нужно подумать и поработать.
Одна проблема связана с термином хэш / хэш-код... существует криптографическое хеширование и некриптографическое хеширование. Другая проблема заключается в том, что вы должны понимать, почему хеширование полезно и как оно работает.
Когда мы говорим о хешировании в JavaScript или Java, большую часть времени мы говорим о некриптографическом хешировании, обычно о хешировании для hashmap / hashtable (если мы не работаем над аутентификацией или паролями, которые вы могли бы выполнять на стороне сервера, используя NodeJS ...).
Это зависит от того, какие данные у вас есть и чего вы хотите достичь.
Ваши данные имеют некоторую естественную "простую" уникальность:
- Хеш целого числа... целое число, как оно уникально, удачи вам!
- Хеш строки... это зависит от строки, если строка представляет уникальный идентификатор, вы можете рассматривать его как хеш (поэтому хеширование не требуется).
- Все, что косвенно в значительной степени является уникальным целым числом, является простейшим случаем
- Это будет уважать: хэш-код равен, если объекты равны
Ваши данные имеют некоторую естественную "составную" уникальность:
- Например, для объекта person вы можете вычислить хеш, используя имя, фамилию, дату рождения,... посмотреть, как это делает Java: хорошая функция хеширования для строк, или использовать другую информацию идентификатора, которая является дешевой и достаточно уникальной для вашего сценария использования.
Вы не представляете, какими будут ваши данные:
- Удачи... вы можете сериализовать строку и хэшировать ее в стиле Java, но это может быть дорого, если строка большая, и это не позволит избежать коллизий, а также произнесет хэш целого числа (self).
Не существует магически эффективного метода хеширования неизвестных данных, в некоторых случаях это довольно просто, в других случаях вам, возможно, придется подумать дважды. Поэтому, даже если JavaScript/ECMAScript добавляет больше поддержки, для этой проблемы не существует волшебного решения.
На практике вам нужны две вещи: достаточно уникальности, достаточно скорости
В дополнение к этому здорово иметь: "хэш-код равен, если объекты равны"
Просто используйте свойство hidden secret с defineProperty enumerable: false
Работает очень быстро:
- Первое чтение uniqueId: 1,257,500 ops / s
- Все остальные: 309226485 операций в секунду
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
}
Мое решение вводит статическую функцию для глобального Object объект.
(function() {
var lastStorageId = 0;
this.Object.hash = function(object) {
var hash = object.__id;
if (!hash)
hash = object.__id = lastStorageId++;
return '#' + hash;
};
}());
Я думаю, что это более удобно с другими функциями управления объектами в JavaScript.
Если вы действительно хотите установить поведение (я знаю Java), то вам будет сложно найти решение в JavaScript. Большинство разработчиков рекомендуют уникальный ключ для представления каждого объекта, но это не так, как установлено, так как вы можете получить два одинаковых объекта каждый с уникальным ключом. Java API выполняет проверку на наличие дублирующихся значений путем сравнения значений хеш-кода, а не ключей, и, поскольку в JavaScript отсутствует представление значений хэш-кода для объектов, становится практически невозможно сделать то же самое. Даже библиотека Prototype JS допускает этот недостаток, когда говорит:
"Хеш можно рассматривать как ассоциативный массив, связывающий уникальные ключи со значениями (которые не обязательно уникальны)..."
Если вы хотите иметь уникальные значения в объекте поиска, вы можете сделать что-то вроде этого:
Создание объекта поиска
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('Stackru');
// key = 'Stackru'
lookup[key] = true;
Конечный результат
{ 1337: true, 01132337: true, Stackru: true }
Обратите внимание, что getHashCode не возвращает никакого значения, когда объект или массив пуст
getHashCode([{},{},{}]);
// '012'
getHashCode([[],[],[]]);
// '012'
Это похоже только на решение @ijmacd getHashCode не имеет JSON зависимость.
В дополнение к ответу без век вот функция, которая возвращает воспроизводимый, уникальный идентификатор для любого объекта:
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);
}
Как вы можете видеть, он использует список для поиска, который очень неэффективен, однако это лучшее, что я смог найти на данный момент.
Сегодня столкнулся с похожей проблемой, потратил 2 часа на это
Решение заключается в использовании
Map(), см. пример ниже:
let someThing = new TreeNode(); // any class/object type
let map = new Map();
map.set(someThing, 1);
let val = map.get(someThing); // <- hashing/ always works..
let obj = {};
obj[someThing] = 1;
let val = obj[someThing]; // <----- does not always work
// So "Map()" takes care of hashing of objects internally
// The object "{}" won't work, converts keys to strings,etc
Если вы хотите использовать объекты в качестве ключей, вам нужно перезаписать их метод toString, как некоторые уже упоминали здесь. Все используемые хэш-функции хороши, но они работают только для одних и тех же объектов, а не для одинаковых объектов.
Я написал небольшую библиотеку, которая создает хэши из объектов, которые вы можете легко использовать для этой цели. Объекты могут даже иметь другой порядок, хэши будут одинаковыми. Внутренне вы можете использовать различные типы для вашего хэша (djb2, md5, sha1, sha256, sha512, palemd160).
Вот небольшой пример из документации:
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