Учитывая набор сегментов строки, есть ли способ вычислить хэш-код, чтобы он был равен хэш-коду объединенной строки?

#java #hash

#java #хэш

Вопрос:

Рассмотрим:

 String[] segments = {"asdf", "qwerty", "blahblah", "alongerstring", "w349fe3434"};
String fullString = "asdfqwertyblahblahalongerstringw349fe3434";

Существует ли эффективный способ объединить хэш-коды () каждого элемента в сегментах таким образом, чтобы он был равен хэш-коду полной строки?

Очевидно, что если я перебираю каждый символ во всех сегментах, я могу получить тот же результат, что и fullString.hashCode() , но это не использует преимущества кэшированных хэш-кодов в каждом из объектов segment string. Я хотел бы избежать зацикливания на каждом символе каждого сегмента. Также я не могу кэшировать зацикленный хэш-код для сегментов, потому что наборы сегментов могут быть объединены для создания полной строки.

Итак, в принципе, я хотел бы что-то, что делает это:

 int segmentHash = 0;
for(int i = 0; i < segments.length; i  )
{
    segmentHash = combine(segmentHash, segments[i].hashCode());
}
assert(segmentHash == fullString.hashCode());

Возможно?

Ответ №1:

Удивительно, но да.

Смотря, как вычисляется хэш-код String ( s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1] ), вам нужно выполнить следующее:

для добавления одного сегмента: умножьте хэш-код начального сегмента на 31 ^ L, где L — длина второго сегмента, и добавьте хэш-код второго сегмента
проделайте то же самое итеративно для остальных сегментов.

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

1. Ого, конечно. 🙂 Обратите внимание, что оператор ^ здесь является возведением в степень, а не XOR .

2. @Mark: да, в основном, поэтому это работает. Интересно, был ли фактический алгоритм выбран именно с этой целью: иметь возможность вычислять хэш из хэша для частей. (Возможно, потому, что некоторые части разных строк могут совместно использоваться компилятором?)

3. Я, вероятно, тупоголовый, но, похоже, у меня это не работает: int hash = 0; for(int i = 0; i < сегменты. длина; i ) { if (i == 0) hash = segments[0].hashCode(); else hash = (int) Math.pow(31, segments[i].длина()) * хэш сегменты [i].hashCode(); } редактировать: кажется, что это работает до 3 сегментов, но для 4 или более это не так.

4. или используя возведение в квадрат int fac=1,t=31,l=segments[i].length();while(l!=0){fac*=(lamp;1==1)?t:1;t*=t;l/=2;}

5. работает также, если «(int) Math.pow(31, segments[i].length())» в версии кода deliciousirony заменен на «новый BigInteger(«31″).pow(segments[i].length()).intValue()»

Ответ №2:

Строка имеет четко определенный хэш-код

он вычисляется как

 int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i <  len; i  ) {
    h = 31*h   val[off  ];
}
hash = h;

(со смещением начала строки и подсчетом длины строки

итак, если вы хотите сделать это самостоятельно:

 int hash=0;
for(String str;segments){
    for(int i=0;i<str.length();i  ){
        hash=hash*31 str.charAt(i);
    }
}

редактировать: или работать по предложению Влада

 int hash = 0; 
for(int i = 0; i < segments.length; i  ) { 
    int fac=1,t=31,l=segments[i].length();
    while(l!=0){
        fac*=(lamp;1==1)?t:1;
        t*=t;
        l/=2;
    }
    hash = fac * hash   segments[i].hashCode(); 
}