Суть: на моëм сайте есть возможность закачки изображений. Дабы при закачке одного и того же изображения несколько раз в разные альбомы не тратилось зря место на харде, у всех закачек вычисляется SHA1, и сервер проверяет наличие в каталоге файла с именем, идентичным полученному хешу. Если файл есть, на него просто вешается ещë одна ссылка, если нет, то он сохраняется с именем своего хеша. Всë бы хорошо, но результат SHA1 довольно длинный для адресной строки, а вычисление занимает немало времени. Хотелось бы сократить имена вдвое, ускорить вычисление, но всë ещë исключить возможность подбора коллизий. Поэтому md5, а тем более контрольные суммы отпадают. Есть мысль обрезать сам SHA1, взяв вторую вторую половину хеш-строки, но это не решает проблему скорости. Итак, какой же алгоритм взять?
-
2Чем короче хеш, тем больше коллизий. Вы хотите невозможного.– andreymal12 апр 2021 в 1:42
-
Для сокращения длины имени файла можно использовать base64, а не hex (как многие используют по умолчанию)– Alexey Ten12 апр 2021 в 4:48
-
base64 урезает длину ненамного, а путаницы получается с ним больше. Если вдруг какой то софт посчитает, что регистр URI не имеет никакого значения даже в части пути на сервере, то всë сломается. Алсо, мне иногда самому приходилось мучаться, вводя вручную такие адреса. I и l, O и 0.– arelive12 апр 2021 в 4:56
1 ответ
Если важна именно скорость, то предлагаю использовать xxHash, он невероятные скорости развивает (около 30 GiB/sec), есть 128-битный и 64-битный варианты. Коллизий очень мало, сравнимо с SHA. Единственный недостаток это не криптостойкость, т.е. его не сложно обратить, SHA например криптостойкий и его сложно обратить.
Ниже привожу примеры использования хеша на C++ и Python. Для С++ достаточно скачать один хедер xxhash.h. Для Python один раз устанавливаем пакет pip install xxhash
. Для C++ я реализовал вспомогательную функцию xxh3_128_hexdigest()
, которая на Python уже есть в модуле xxhash
, функция получения хекс-строки с хешем.
C++:
#include <iostream>
#include <string>
#include <sstream>
#include <cstdint>
#include <iomanip>
#include <algorithm>
#define XXH_INLINE_ALL
#include "xxhash.h"
inline std::string ToHex(void const * data, size_t size) {
std::stringstream ss;
ss << std::uppercase << std::hex;
for (size_t i = 0; i < size; ++i)
ss << std::setfill('0') << std::setw(2) << size_t(((uint8_t const *)data)[i]);
return ss.str();
}
inline std::string xxh3_128_hexdigest(void const * data, size_t size) {
auto h = XXH3_128bits(data, size);
std::reverse(((uint8_t*)&h) + 0, ((uint8_t*)&h) + sizeof(h));
return ToHex(&h, sizeof(h));
}
int main() {
std::string data = "Hello, World!";
std::cout << xxh3_128_hexdigest(data.data(), data.size()) << std::endl;
}
Python:
import xxhash
print(xxhash.xxh3_128_hexdigest('Hello, World!'.encode('ascii')).upper())
Вывод:
531DF2844447DD5077DB03842CD75395
Если интересно как работает xxhash, то привожу ниже код основной функции (взятый здесь) 32-битной 2-й версии хеша (уже вышла 3-я версия, xxh3_128_hexdigest() выше использует 3-ю версию), код ниже лучше не использовать, используйте xxh3_128_hexdigest() как в коде выше:
static const uint32_t Prime1 = 2654435761U;
static const uint32_t Prime2 = 2246822519U;
/// rotate bits, should compile to a single CPU instruction (ROL)
static inline uint32_t rotateLeft(uint32_t x, unsigned char bits)
{
return (x << bits) | (x >> (32 - bits));
}
/// process a block of 4x4 bytes, this is the main part of the XXHash32 algorithm
static inline void process(const void* data, uint32_t& state0, uint32_t& state1, uint32_t& state2, uint32_t& state3)
{
const uint32_t* block = (const uint32_t*) data;
state0 = rotateLeft(state0 + block[0] * Prime2, 13) * Prime1;
state1 = rotateLeft(state1 + block[1] * Prime2, 13) * Prime1;
state2 = rotateLeft(state2 + block[2] * Prime2, 13) * Prime1;
state3 = rotateLeft(state3 + block[3] * Prime2, 13) * Prime1;
}