Javascript алгоритм хэширования

Question

Я пытаюсь узнать, как сделать некоторые основные хэширования в JavaScript, и я сталкивался со следующим алгоритмом:

var hash = 0; 
for (i = 0; i < this.length; i++) { 
    char = str.charCodeAt(i); 
    hash = ((hash<<5)-hash)+char; 
    hash = hash & hash; 
} 

Я не очень понимаю, как это работает, и я надеялся, вы могли бы помочь мне. В частности, я не понимаю (hash<<5)-hash и hash = hash & hash. Спасибо за ваши ответы.

Примечание: Для тех, кто ищет источник, это реализация String.hashCode в Java(): http://werxltd.com/wp/2010/05/13/javascript-implementation-of-javas-string-hashcode-method

Answer 1

Стадию

hash = ((hash << 5) - hash) + char; 

эффективно:

hash = ((hash * 32) - hash) + char; 

Затем

hash = hash & hash; 

изменится только значение, если число Переполнение диапазон целое (32 бита, или возможно 31). (. Я бы не сделать это таким образом, но это вопрос стиля)

В этом коде переменные «я» и «символ» должен быть объявлен:

var hash = 0, i, char; 

Answer 2

< < и & являются битовые операции. Один - это смещение битов, а другое - их обработка.

0010 << 2 становится 1000 потому что все сдвинуто влево.

0101 & 1110 становится 0100, потому что результат равен 1, если оба значения имеют 1 для этого конкретного бита.

@ Ответ Pointy объясняет, что такое hash = hash & hash (), я не был уверен, что он сделал.

См:

https://en.wikipedia.org/wiki/Bitwise_operation https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

Answer 3

hash << 5 является bitshifting значение хэша для "левых" 5 мест. Это эквивалентно hash * 32. Для алгоритма хэш-генерации легче думать об этом с точки зрения перемещения бит.

hash = hash & hash выглядит как ошибка. Это «ands» значение хеша с собой и присваивает его себе. Anding значение с самим результатом приводит к исходному значению, так что это форма nop.

Answer 4

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

В этом случае:

((hash << 5) - hash) 

эффективно "хэш * 31".Примените оператор сдвига влево, <<, 5 раз, как умножение числа на 2, 5 раз. Или, умножая его на 2^5, что равно 32. Затем они вычитают один раз, давая 31.

hash & hash - фактически операция «ничего не делать», выполняющая логическое И (&) на число с собой, возвращает то же самое, он не «ничего делать», но может использоваться для принуждения номера и обеспечения его целостности. Вероятно, некоторые JS-махинации продолжаются с представлением числа, и для этого есть вторая строка.

Если бы это было просто сырье C, это было бы просто hash = hash * 31 + char.

Answer 5

< < представляет собой операцию сдвига влево. Этот оператор перемещает первый операнд на заданное число бит слева, например:

var num = 2; // in binary 10 
var shift = 2 << 2; //shift is 8, in binary 1000 

Оператор & представляет собой и логическую операцию, например:

var num1 = 6; // in binary 110 
var num2 = 7; // in binary 111 
var result = num1 & num2; // result is 6, in binary 110 

для полной ссылки на побитовом операторы смотрят на Mozilla javascript reference.