Есть ли какая-либо функция хэш-кода в JavaScript?

javascript hash set hashcode

157809 просмотра

19 ответа

1873 Репутация автора

По сути, я пытаюсь создать объект из уникальных объектов, набор. У меня была блестящая идея просто использовать объект JavaScript с объектами для имен свойств. Такие как,

set[obj] = true;

Это работает, до определенного момента. Он отлично работает со строками и числами, но с другими объектами все они, похоже, "хэшируют" одно и то же значение и имеют доступ к одному и тому же свойству. Есть ли какой-то способ, которым я могу сгенерировать уникальное хеш-значение для объекта? Как строки и числа делают это, я могу переопределить то же самое поведение?

Автор: Boog Источник Размещён: 11.10.2008 11:45

Ответы (19)


32 плюса

52314 Репутация автора

Решение

Объекты JavaScript могут использовать только строки в качестве ключей (все остальное преобразуется в строку).

В качестве альтернативы вы можете поддерживать массив, который индексирует рассматриваемые объекты, и использовать его индексную строку в качестве ссылки на объект. Что-то вроде этого:

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

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

Очевидно, что это немного многословно, но вы могли бы написать пару методов, которые справятся с этим и получат и установят все волей и неволей.

Редактировать:

Ваше предположение является фактом - это определенное поведение в JavaScript - в частности, происходит преобразование toString, означающее, что вы можете определить свою собственную функцию toString для объекта, который будет использоваться в качестве имени свойства. - оллидж

Это поднимает еще один интересный момент; Вы можете определить метод toString для объектов, которые хотите хэшировать, и это может сформировать их хеш-идентификатор.

Автор: eyelidlessness Размещён: 12.10.2008 12:42

0 плюса

0 Репутация автора

Если вы действительно хотите установить поведение (я знаю Java), вам будет сложно найти решение в JavaScript. Большинство разработчиков рекомендуют уникальный ключ для представления каждого объекта, но это не так, как установлено, в том смысле, что вы можете получить два идентичных объекта каждый с уникальным ключом. Java API выполняет проверку на наличие дублирующихся значений путем сравнения значений хеш-кода, а не ключей, и, поскольку в JavaScript отсутствует представление значений хеш-кода объектов в JavaScript, практически невозможно сделать то же самое. Даже библиотека Prototype JS допускает этот недостаток, когда говорит:

«Хэш можно рассматривать как ассоциативный массив, связывающий уникальные ключи со значениями (которые не обязательно уникальны) ...»

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

Автор: user4903 Размещён: 12.10.2008 01:49

8 плюса

29386 Репутация автора

Спецификация JavaScript определяет доступ к индексированным свойствам как выполнение преобразования toString для имени индекса. Например,

myObject[myProperty] = ...;

такой же как

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

Это необходимо как в JavaScript

myObject["someProperty"]

такой же как

myObject.someProperty

И да, это меня тоже огорчает :-(

Автор: olliej Размещён: 12.10.2008 08:02

31 плюса

10213 Репутация автора

Самый простой способ сделать это - дать каждому из ваших объектов свой уникальный 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> в ваш хеш, иначе это сотрет запись для вашего выходящего объекта с этим идентификатором.

Теперь все мои хэши совершенно холодные. Я также только что опубликовал запись в блоге несколько дней назад на эту тему .

Автор: Daniel X Moore Размещён: 20.05.2009 02:51

18 плюса

793 Репутация автора

Решение, которое я выбрал, похоже на решение Дэниела, но вместо того, чтобы использовать фабрику объектов и переопределить toString, я явно добавляю хэш к объекту, когда он сначала запрашивается через функцию getHashCode. Немного грязно, но лучше для моих нужд :)

Function.prototype.getHashCode = (function(id) {
    return function() {
        if (!this.hashCode) {
            this.hashCode = '<hash|#' + (id++) + '>';
        }
        return this.hashCode;
    }
}(0));
Автор: theGecko Размещён: 26.04.2011 01:10

52 плюса

3553 Репутация автора

Если вам нужна функция 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 (побитовый оператор).

Автор: KimKha Размещён: 10.11.2011 08:01

18 плюса

0 Репутация автора

То, что вы описали, покрыто 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флагом.

Автор: user748221 Размещён: 10.11.2011 09:31

0 плюса

1668 Репутация автора

В дополнение к ответу без век, вот функция, которая возвращает воспроизводимый уникальный идентификатор для любого объекта:

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

Как вы можете видеть, он использует список для поиска, который очень неэффективен, однако это лучшее, что я смог найти на данный момент.

Автор: cburgmer Размещён: 11.07.2012 08:29

0 плюса

31 Репутация автора

Если вы хотите использовать объекты в качестве ключей, вам нужно перезаписать их метод 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

Автор: darthmatch Размещён: 22.01.2013 10:35

1 плюс

449 Репутация автора

Мое решение вводит статическую функцию для глобального Objectобъекта.

(function() {
    var lastStorageId = 0;

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

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

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

Я думаю, что это более удобно с другими функциями управления объектами в JavaScript.

Автор: Johnny Размещён: 19.02.2013 09:14

8 плюса

1445 Репутация автора

Некоторое время назад я собрал небольшой модуль JavaScript для создания хеш-кодов для строк, объектов, массивов и т. Д. (Я просто передал его в GitHub :))

Использование:

Hashcode.value("stackoverflow")
// -2559914341
Hashcode.value({ 'site' : "stackoverflow" })
// -3579752159
Автор: Metalstorm Размещён: 07.04.2013 10:33

13 плюса

237 Репутация автора

Для моей конкретной ситуации меня интересует только равенство объекта в том, что касается ключей и примитивных значений. Решением, которое работало для меня, было преобразование объекта в его 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.03.2014 04:30

7 плюса

10213 Репутация автора

В ECMAScript 6 теперь есть функция, Setкоторая работает так, как вам хочется: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

Он уже доступен в последних версиях Chrome, FF и IE11.

Автор: Daniel X Moore Размещён: 13.01.2015 07:48

0 плюса

10461 Репутация автора

Если вы хотите иметь уникальные значения в объекте поиска, вы можете сделать что-то вроде этого:

Создание объекта поиска

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зависимости.

Автор: A1rPun Размещён: 22.10.2016 01:38

4 плюса

1094 Репутация автора

Ссылка: 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';
Автор: Khalid Azam Размещён: 29.01.2017 08:22

2 плюса

16890 Репутация автора

Вот мое простое решение, которое возвращает уникальное целое число.

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;
}
Автор: Timothy Perez Размещён: 06.04.2017 03:41

0 плюса

10413 Репутация автора

Я постараюсь пойти немного глубже, чем другие ответы.

Даже если бы у JS была лучшая поддержка хеширования, он не мог бы магически все хешировать, во многих случаях вам придется определять свою собственную хеш-функцию. Например, Java имеет хорошую поддержку хеширования, но вам все еще нужно подумать и поработать.

Одна проблема связана с термином хэш / хэш-код ... существует криптографическое хеширование и некриптографическое хеширование. Другая проблема заключается в том, что вы должны понимать, почему хеширование полезно и как оно работает.

Когда мы говорим о хешировании в JavaScript или Java, большую часть времени мы говорим о некриптографическом хешировании, обычно о хешировании для hashmap / hashtable (если мы не работаем над аутентификацией или паролями, которые вы могли бы выполнять на стороне сервера с помощью NodeJS. ..).

Это зависит от того, какие данные у вас есть и чего вы хотите достичь.

Ваши данные имеют некоторую естественную «простую» уникальность:

  • Хеш целого числа ... целое число, как оно уникально, удачи вам!
  • Хеш строки ... это зависит от строки, если строка представляет уникальный идентификатор, вы можете рассматривать его как хеш (поэтому хеширование не требуется).
  • Все, что косвенно в значительной степени является уникальным целым числом, является простейшим случаем.
  • Это будет уважать: хэш-код равен, если объекты равны

Ваши данные имеют некоторую естественную «составную» уникальность:

  • Например, для объекта person вы можете вычислить хеш, используя имя, фамилию, дату рождения, ... посмотрите, как это делает Java: хорошая функция для строк , или используйте другую информацию идентификатора, которая является дешевой и достаточно уникальной для вашего сценария использования.

Вы не представляете, какими будут ваши данные:

  • Удачи ... вы можете сериализовать строку и хэшировать ее в стиле Java, но это может быть дорого, если строка большая, и это не позволит избежать коллизий, а также произнесет хэш целого числа (self).

Не существует магически эффективного метода хеширования неизвестных данных, в некоторых случаях это довольно легко, в других случаях вам, возможно, придется подумать дважды. Таким образом, даже если JavaScript / ECMAScript добавляет дополнительную поддержку, для этой проблемы не существует волшебного решения.

На практике вам нужны две вещи: достаточно уникальности, достаточно скорости

В дополнение к этому здорово иметь: «хэш-код равен, если объекты равны»

Автор: Christophe Roussy Размещён: 23.11.2018 04:26

0 плюса

91 Репутация автора

Я объединил ответы от век и КимХа.

Ниже приведен сервис 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"}'});

Это вернется

[]
Автор: jozsef morrissey Размещён: 23.12.2018 04:43

0 плюса

2054 Репутация автора

Основываясь на заголовке, мы можем генерировать сильные хэши с помощью js, это можно использовать так:

async function c(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('')
  return hashHex
}

async function H(it) {
  const d = await c(it)
  console.log(d)
}

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

/ API / SubtleCrypto / дайджест # Converting_a_digest_to_a_hex_string

Автор: NVRM Размещён: 07.08.2019 01:28
Вопросы из категории :
32x32