Создание уникального идентификатора из массива строк в JavaScript?

Question

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

По сути, я хочу что-то вроде SHA1, но для javascript.

Есть идеи, как мне это сделать?

Спасибо.

Answer 1

К сожалению, нет способа получить 100% гарантированную уникальность без использования всего содержимого массива в качестве вашего ключа.Большинство хороших некриптографических хэшей уменьшит коллизии только до величины, приемлемой для хорошей производительности в хэш-таблице, но вам все равно нужно проверить, что все содержимое совпадает.

Даже криптографический хеш, такой как SHA-1или MD5 все еще может иметь коллизии, но в большинстве случаев это крайне маловероятно.Если это достаточно хорошо, я бы, вероятно, пошел с SHA-1.В противном случае я бы преобразовал массив в строку для использования в качестве ключа и позволил бы JavaScript беспокоиться о хешировании и коллизиях.

В любом случае, вы, вероятно, торгуете производительностью (нативное хеширование, которое JavaScript делает, вероятно,быть намного быстрее, чем все, что вы можете написать в JavaScript) и, возможно, абсолютно корректно для пространства.

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

Answer 2

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

1. Если ожидается, что конкатенация строк будет "длинной", вы захотите использовать какой-то "хеш", который возвращает более короткое значение.
2. Вам, вероятно, не нужен хеш криптостойкости, поэтому md5 или sha1, вероятно, излишни
3. Даже высокотехнологичные быстрые хэши, такие как (length of string concat as int) + '/' + (number of strings as int) + '/' + (first char of each string), могут подойти в зависимости от ваших ожидаемых значений

Наконец, вот реализация string.GetHashCode(), портированная из C #. Если это достаточно хорошо для .NET, то, вероятно, достаточно хорошо для вас.

var str = "concatenation of all array values";
var hash1 = (5381<<16) + 5381; 
var hash2 = hash1;
var hashPos = 0;
while(hashPos < str.length) { 
    hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ str.charCodeAt(hashPos);
    if( hashPos == str.length - 1) { 
        break;
    }
    hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ str.charCodeAt(hashPos + 1);
    hashPos += 2; 
} 

return hash1 + (hash2 * 1566083941);

Answer 3

Без использования хэша вы не получите ничего уникального и маленького.

Выполнение myArray.join() может гарантировать уникальность, но может занять большой объем памяти и привести к крайним случаям, когда она не будет уникальной.

Лучше всего использовать реализацию алгоритма хеширования в JavaScript.

Answer 4

Вы хотите sha1 в JavaScript? Здесь -> http://pajhome.org.uk/crypt/md5/sha1.html

Answer 5

Может быть, это:

var newDate = new Date;
var uid = newDate.getTime();

или это:

var uid = Math.random() * Math.pow(10, 17) + Math.random() * Math.pow(10, 17) + Math.random() * Math.pow(10, 17) + Math.random() * Math.pow(10, 17));

Есть много способов получить что-то столь же близкое, как уникальный идентификатор, и так как вы работаете с JavaScript длякеширование становится прощеЭто вопрос выбора того, что подходит вам лучше всего.