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

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

133 голосов
/ 12 октября 2008

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

set[obj] = true;

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

Ответы [ 18 ]

2 голосов
/ 06 апреля 2017

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

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;
}
1 голос
/ 19 февраля 2013

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

(function() {
    var lastStorageId = 0;

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

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

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

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

0 голосов
/ 23 декабря 2018

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

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

Это вернет 

[]
0 голосов
/ 23 ноября 2018

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0 голосов
/ 12 июля 2012

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

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

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

0 голосов
/ 23 января 2013

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

Репозиторий: https://bitbucket.org/tehrengruber/es-js-hash

0 голосов
/ 22 октября 2016

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

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

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

1010 * Объект *

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.

0 голосов
/ 12 октября 2008

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

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

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

Страница:
...