Объяснение о хешировании и его использовании для сжатия данных

Question

Я сталкиваюсь с приложением, которое использует хеширование, но я до сих пор не могу понять, как оно работает. Вот моя проблема, хеширование используется для генерации некоторого индекса, и с этими индексами я обращаюсь к различным таблицам, и после того, как я добавляю значение каждой таблицы, которую получаю с помощью индексов, я получаю свое окончательное значение. Это сделано, чтобы уменьшить требования к памяти. Вход в функцию хеширования выполняет XOR между случайным постоянным числом и некоторыми параметрами из приложения.

Это типичное приложение хеширования? Я не понимаю, как с помощью хэширования мы можем уменьшить требования к памяти? Кто-нибудь может уточнить это?

Спасибо

Answer 1

Одно только хеширование не имеет ничего общего с памятью.

То, для чего это часто используется, является хеш-таблицей. Хеш-таблицы работают путем вычисления хеша того, от чего вы пользуетесь ключом, который затем используется как индекс в структуре данных.

Хеширование позволяет уменьшить ключ (строку и т. Д.) До более компактного значения, такого как целое число или набор битов.

Это может быть экономия памяти, на которую вы ссылаетесь - сокращение большого ключа до простого целого числа.

Обратите внимание, что хэши не уникальны! Хороший алгоритм хеширования минимизирует коллизии, но они не предназначены для уменьшения до уникального значения - это невозможно (например, если ваш хеш выдает 32-битное целое число, ваш хеш будет иметь только 2 ^ 32 уникальных значений). *

Answer 2

Это может быть объяснено, если хеширование выполняется не для создания истинной хеш-таблицы, а для создания индекса в таблице строк / блоков памяти. Если в ваших данных была одна и та же строка (или последовательность памяти) 20 раз, а затем вы заменили все 20 экземпляров этой строки только ее индексом хеш-таблицы, вы можете таким образом добиться сжатия данных. Однако если в каждой таблице содержится фактическая цепочка столкновений для каждого хеш-значения, то, что я только что описал, не то, что происходит; в этом случае причиной хеширования, скорее всего, будет ускорение выполнения (путем предоставления быстрого доступа к сохраненным значениям), а не сжатие.

Answer 3

В большинстве хороших реализаций хеширования память неэффективна, в противном случае потребовалось бы больше вычислений - и это точно упустило бы точку хеширования.

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

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

Answer 4

Это фильтр Блума , о котором вы говорите? При этом используются хэш-функции, чтобы получить эффективный способ проверки членства в наборе. Если это так, см. Ссылку для объяснения.