Почему HashSet не может просто использовать внутри битовый массив вместо HashMap, чтобы сэкономить место?
Я вижу, что HashSet в Java внутренне использует HashMap, чтобы проверить, содержит ли HashSet элемент или нет. Разве он не может просто использовать растровое изображение для хранения всех результатов хеширования из строк. Например. Строка abc хэшируется, чтобы сказать, что индекс 12, и мы можем просто установить этот индекс, чтобы показать, что он присутствует. Это сэкономит много места по сравнению с HashMap, поскольку нам не нужно хранить фактические ключи в данных.
Обратите внимание, что EnumSet действительно использует «битовый массив»: такой подход хорошо работает для перечислений, потому что они плотно упакованы (без пробелов) и, по большей части, довольно малы (большинство перечислений имеют менее 64 элементов, и поэтому могут быть упакованы в одно длинное; но для хранения наборов больших перечислений вам просто нужны дополнительные длинные).
Ответы 1
Если бы HashSet использовался только для поиска contains(), подобная оптимизация была бы возможна. Это все равно было бы опасно, потому что всегда могут возникнуть коллизии хешей. Я думаю, что вы ищете Фильтр Блума (обратите внимание, что фильтр Блума не дает точных ответов, он просто исключает ложные отрицательные значения).
Набор хэшей — это коллекция, а коллекция должна иметь возможность извлекать сохраненные значения. Хэши необратимы, вы не можете вычислить исходную строку из ее хэша.
abcможет превратиться в12. Но то же самое будет и с почти бесконечностью других струн. Максимальная длина строки равнаInteger.MAX_VALUE— существует гораздо больше перестановок массива такого размера, чем диапазон или хэш-код. Итак, с вашим предложением о наборе битов, как вы справляетесь с коллизиями?