Сравнение, если два списка строк равны с использованием hashcode?

Question

Я пишу приложение сервера клиентов Java/JEE. У меня было требование, чтобы файлы, присутствующие на сервере, соответствовали файлам, присутствующим на клиенте. Я только пытаюсь проверить, есть ли точное совпадение с именами файлов и количеством файлов в определенном каталоге.

Пример того, что требуется:

Server 
    DirectoryA 
     FileA 
     FileB 
     FileC 

Client 
    DirectoryA 
     FileA 
     FileB 
     FileC 

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

Вот мой текущий подход использует REST API и клиент REST:

Сервер:

1. Найти список файлов в целевом каталоге
2. Создать контрольную сумму для каталога по используя хэш-код, полученный по именам файлов, и суммируя его с номером 31.

Клиентов:

1. При получении запроса для проверки целостности целевого каталога, клиент берет контрольную сумму, предоставленный сервером и работает один и тот же алгоритм для генерации контрольной суммы на локальном каталоге. `
2. Если контрольная сумма соответствует клиенту, он отвечает за успех сервера.

Правильно ли этот подход?

Answer 1

Правильно ли этот подход?

Этот подход является правильным, но предлагаемая реализация не является (ИМО).

Я предполагаю, что "суммируя 31" означает что-то вроде этого

int hash = 0; 
    for (String name : names) 
     hash = hash * 31 + name.hashCode(); 

значений Hashcode Java 32 битовые. Если мы предположим, что имена файлов распределены равномерно, это означает, что существует вероятность того, что один из 2^32 будет иметь два одинаковых хэша разных типов имен файлов (как указано выше). Другими словами, «хеш-столкновение».

Алгоритм, который ошибочно делает один раз в 4 миллиарда раз, вероятно, неприемлем. Хуже того, если алгоритм известен, то кто-то может создать тривиально ситуацию (т. Е. Набор имен файлов), где алгоритм дает неправильный ответ.

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

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