Преносима реализация на hashCode за двоични данни

Търся преносим алгоритъм за създаване на хешкод за двоични данни. Нито една от двоичните данни не е много дълга -- аз съм Avro-кодиращи ключове за използване в kafka.KeyedMessages -- вероятно говорим за дължина от 2 до 100 байта, но повечето от ключовете са в диапазона от 4 до 8 байта.

Досега най-доброто ми решение е да конвертирам данните в шестнадесетичен низ и след това да направя hashCode от това. Мога да накарам това да работи както в Scala, така и в JavaScript. Ако приемем, че съм дефинирал b: Array[Byte], Scala изглежда така:

b.map("%02X" format _).mkString.hashCode

В JavaScript е малко по-сложно -- за щастие някой вече е пренесъл основния алгоритъм на hashCode към JavaScript -- но смисълът е да мога да създам низ Hex за представяне на двоичните данни, мога да гарантирам, че алгоритъмът за хеширане работи със същите входове.

От друга страна, трябва да създам обект два пъти по-голям от оригинала, само за да създам hashCode. За щастие повечето ми данни са малки, но все пак -- трябва да има по-добър начин за това.

Вместо да допълвате данните като шестнадесетична стойност, предполагам, че можете просто да принудите двоичните данни в низ, така че низът да има същия брой байтове като двоичните данни. Всичко ще бъде изкривено, повече контролни знаци, отколкото знаци за печат, но въпреки това ще бъде низ. Срещате ли обаче проблеми с преносимостта? Endian-ness, Unicode и др.

Между другото, ако сте прочели толкова далеч и все още не знаете това -- не можете просто да направите:

val b: Array[Byte] = ...
b.hashCode

За щастие вече знаех това, преди да започна, защото се натъкнах на това рано.

Актуализация

Въз основа на първия даден отговор на пръв поглед изглежда, че java.util.Arrays.hashCode(Array[Byte]) ще свърши работа. Въпреки това, ако следвате пътеката на javadoc, ще видите, че това е алгоритъмът зад него, който е базиран на комбинирания алгоритъм за List и алгоритъм за byte.

int hashCode = 1;
for (byte e : list)  hashCode = 31*hashCode + (e==null ? 0 : e.intValue());

Както можете да видите, всичко, което прави, е да създаде Long, представляващо стойността. В определен момент числото става твърде голямо и се увива. Това не е много преносимо. Мога да го накарам да работи за JavaScript, но трябва да импортирате npm модула long. Ако го направите, изглежда така:

function bufferHashCode(buffer) {
  const Long = require('long');
  var hashCode = new Long(1);
  for (var value of buff.values()) { hashCode = hashCode.multiply(31).add(value) }
  return hashCode
}

bufferHashCode(new Buffer([1,2,3]));
// hashCode = Long { low: 30817, high: 0, unsigned: false }

И наистина получавате същите резултати, когато данните се обвият, нещо като, макар че не съм сигурен защо. В Scala:

java.util.Arrays.hashCode(Array[Byte](1,2,3,4,5,6,7,8,9,10))
// res30: Int = -975991962

Имайте предвид, че резултатът е Int. В JavaScript:

bufferHashCode(new Buffer([1,2,3,4,5,6,7,8,9,10]);
// hashCode = Long { low: -975991962, high: 197407, unsigned: false }

Така че трябва да взема low байта и да игнорирам high, но иначе получавам същите резултати.


java javascript scala hashcode
person David Griffin    schedule 03.05.2016    source източник
comment
Ако трябва да бъде преносим, ​​тогава не трябва ли да използвате нещо като md5? Трябва да има API/имплементации на md5 на всички езици, които споменахте, нали?   -  person DavidS    schedule 05.05.2016
comment
Или по-широко някакъв бърз некриптографски хеш.   -  person DavidS    schedule 05.05.2016

Отговори (2)


arrow_upward
1
arrow_downward

Тази функционалност вече е налична в стандартната библиотека на Java, вижте метода Arrays.hashCode().

Тъй като вашите двоични данни са Array[Byte], ето как можете да проверите дали работи:

println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817
println(java.util.Arrays.hashCode(Array[Byte](1,2,3))) // prints 30817
println(java.util.Arrays.hashCode(Array[Byte](2,2,3))) // prints 31778

Актуализация: Не е вярно, че изпълнението на Java поставя байтовете в кутии. Разбира се, има преобразуване в int, но няма начин да се заобиколи това. Това е изпълнението на Java:

public static int hashCode(byte a[]) {
    if (a == null) return 0;
    int result = 1;
    for (byte element : a) result = 31 * result + element;
    return result;
}

Актуализация 2 Ако това, от което се нуждаете, е реализация на JavaScript, която дава същите резултати като реализация на Scala/Java, тогава можете да разширите алгоритъма, като например вземете само най-десните 31 бита:

def hashCode(a: Array[Byte]): Int = {
  if (a == null) {
    0
  } else {
    var hash = 1
    var i: Int = 0
    while (i < a.length) {
      hash = 31 * hash + a(i)
      hash = hash & Int.MaxValue // taking only the rightmost 31 bits
      i += 1
    }
    hash
  }
}

и JavaScript:

var hashCode = function(arr) {
    if (arr == null) return 0; 
    var hash = 1;
    for (var i = 0; i < arr.length; i++) {
        hash = hash * 31 + arr[i]
        hash = hash % 0x80000000 // taking only the rightmost 31 bits in integer representation
    }
    return hash;
}

Защо двете реализации дават еднакви резултати? В Java целочисленото препълване се държи така, сякаш събирането е извършено без загуба на точност и след това битове, по-високи от 32, са изхвърлени и & Int.MaxValue изхвърля 32nd бит. В JavaScript няма загуба на точност за цели числа до 253, което е ограничение, което изразът 31 * hash + a(i) никога не превишава. % 0x80000000 тогава се държи като взема най-десните 31 бита. Случаят без преливания е очевиден.

person Mifeet    schedule 04.05.2016
comment
Някаква идея какъв е алгоритъмът - въпросът е и преносимостта. Как работи, ще мога ли да го пресъздам на език, който не е базиран на Java? - person David Griffin; 04.05.2016
comment
Вижте моята актуализация във въпроса, този алгоритъм не е много преносим. - person David Griffin; 04.05.2016
comment
@DavidGriffin И така, това, което искате, не е алгоритъм за хеширане в Scala/Java и Javascript, а алгоритъм, който дава един и същ резултат и в двете? Ако е така, вижте актуализирания ми отговор. - person Mifeet; 07.05.2016
comment
Предполагам, че не е по-лошо от гледна точка на сблъсъци, тъй като резултатът е Int така или иначе? - person David Griffin; 07.05.2016
comment
Степента на сблъсък зависи от модела на използване. Хеш-таблиците често имат размер, който е степен на 2. Ако използвате прост модулен размер на таблица, точността е същата като версията Arrays. Ако използвате същия алгоритъм като Java HashMap, може да загубите известна точност за таблици, по-големи от 2^17. Като цяло, ако наистина се нуждаете от възможно най-малко сблъсъци, по-добре е да използвате друга хеш функция, напр. Murmur hash или това, което DavidS предложи в коментарите. Иначе горната функция е достатъчно добра. - person Mifeet; 07.05.2016

arrow_upward
1
arrow_downward

Това е същността на алгоритъма, използван в библиотеката на Java:

  int result 1;
  for (byte element : a) result = 31 * result + element;

Вие коментирате:

този алгоритъм не е много преносим

Неправилно. Ако говорим за Java, тогава при условие, че всички сме съгласни с типа на result, тогава алгоритъмът е 100% преносим.

Да, изчислението препълва, но препълва точно по същия начин при всички валидни реализации на езика Java. Java int е определено като 32-битово допълнение със знак две и поведението на операторите при възникване на препълване е добре дефинирано ... и еднакво за всички реализации. (Същото важи и за long ... въпреки че размерът е различен, очевидно.)

Не съм експерт, но моето разбиране е, че числовите типове на Scala имат същите свойства като Java. Javascript е различен, базиран на IEE 754 с плаваща запетая с двойна точност. Въпреки това, с регистър трябва да можете да кодирате Java алгоритъма преносимо в Javascript. (Мисля, че версията на @Mifeet е грешна ...)

person Stephen C    schedule 04.05.2016
comment
@DavidGriffin - Какво не е правилно? Javascript версията на Mifeet или моят отговор? - person Stephen C; 05.05.2016
comment
Съжалявам, бях на телефон и удари връщане, преди да имам предвид -- JavaScript версията на Mifeet не е правилна. Трябва да използвате библиотека, за да приложите правилно Long боравене. Поне библиотеката, която използвах, се увива по същия начин като тази на Java. - person David Griffin; 05.05.2016
comment
Като алтернатива той може да използва битово маскиране след всяка итерация. Очевидно Javascript преобразува число в 32-битово int, преди да извърши побитова операция. - person Stephen C; 05.05.2016