Как хранить целые числа в диапазоне от 0 до 9 всего в 4 битах и использовать то же самое, что и ключ в HashMap?
Меня попросили придумать решение, в котором у вас есть файл, в котором каждая строка представляет 10-значный номер телефона, и нам нужно указать, присутствует ли данный 10-значный номер телефона в файле или нет.
Я придумал структуру Trie Data, в которой каждый дочерний элемент представляет собой не что иное, как карту целого числа в качестве ключа и Trie в качестве значения.
class Trie{
boolean isEnd;
Map<Integer, Trie> map = new HashMap<>();
}
Я также могу использовать int[] arr для хранения дочерних элементов.
Поскольку у нас есть только числа от 0 до 9, мы можем хранить эти числа только в 4 битах. Зачем брать int или Integer в качестве типа данных. Как тут уменьшить память?
Как мы можем хранить эти числа в карте или массиве, но не принимая во внимание, так как в конечном итоге мы потеряем много памяти.
Более того, есть ли лучшее решение, чем Trie?
Мои ключи карты - это не весь номер телефона. Каждая цифра числа является ключевой, а остальные цифры - дочерними,
Хотя вы можете представить цифру всего 4 битами, в Java нет собственного 4-битного типа данных. Таким образом, вы не можете сохранить память таким образом. Однако вы можете хранить две цифры в одном 8-битном значении. Но использование здесь trie, вероятно, не лучший вариант из-за ограничений памяти. Почему не Map<long, boolean>? Конечно, вы тратите один байт boolean на каждое число, но это намного меньше памяти, которую вы будете использовать для хранения указателей в своем дереве.
Ответы 1
Если вы стремитесь к эффективности памяти, я бы посоветовал против использовать trie и порекомендовать другую структуру данных. Насколько я понимаю, вас интересуют только ответы на запросы вида "видел ли я раньше этот номер телефона?" Хотя вы могли бы сделать это, рассматривая телефонные номера как строки и помещая их все в дерево, вы не воспользуетесь преимуществами операций, для поддержки которых предназначены попытки (быстрый поиск префиксов, извлечение элементов в отсортированном порядке и т. д. ), поэтому вы будете платить за то, чем не будете пользоваться.
Кроме того, давайте подумаем об использовании пространства в дереве. Даже если у каждого телефонного номера есть длинный общий префикс, каждому узлу в дереве требуется место для хранения дочерних указателей. Если вы храните хотя бы один (64-разрядный) указатель на узел, вы используете тот же объем пространства, который вы бы использовали для хранения 10-значного номера телефона (который удобно вписывается в 64-разрядное целое число). Если телефонные номера не имеют длинных общих префиксов, вы потенциально храните десять указателей на номер, что приводит к огромному увеличению пространства, независимо от того, насколько велики ключи хеш-таблицы.
Вместо того, чтобы бросать вещи в три, я бы подумал об использовании простой, ванильной хеш-таблицы. В конце концов, хэш-таблицы специально оптимизированы для поддержки запросов о членстве и только запросов о членстве. Хеширование телефонных номеров не должно вызывать особых затруднений, так как их можно упаковать в 64-битные целые числа и хешировать с помощью множества простых методов хеширования. Это позволяет вам контролировать, какой компромисс между временем и пространством вы хотите сделать (большие размеры таблиц увеличивают память и уменьшают время, меньшие таблицы увеличивают время и уменьшают память).
Спасибо за объяснение, не используя trie. Но в хеш-таблице мы также тратим впустую память поля «значение», поскольку мы ее не используем. Во-вторых, как насчет моей первой части вопросов о хранении чисел от 0 до 9 в 4 битах в java? В случае, если вы можете помочь мне в этом.
Хотя верно то, что неиспользуемые значения в хэш-таблице тратят память впустую, давайте проведем некоторые арифметические расчеты. Если используется половина записей в таблице, каждый телефонный номер по существу занимает два машинных слова — одно для используемого слота и одно для неиспользуемого слота. При попытке каждый номер телефона требует места для десяти указателей, даже не учитывая накладные расходы на карту. Это заметная разница в пространстве, которая делает хеш-таблицу намного более эффективной с точки зрения использования памяти.
Он имеет в виду, что хеш-таблица хранит ключ-> значение, где только ключ является полезной нагрузкой. Вместо этого используйте HashSet. По иронии судьбы, HashSet имеет немного больший объем памяти (только на фиксированное количество байтов), поскольку он использует HashMap внутри и не использует поля «значение».
В зависимости от того, как все реализовано, иногда контейнерам на основе хэшей все еще нужны некоторые вспомогательные управляющие слова, связанные с каждой записью, для хранения данных, таких как «этот слот пуст?», «насколько далеко этот элемент от своего домашнего слота?» и т. д. Даже с такими накладными расходами памяти это все же, вероятно, лучший маршрут, чем trie.
Если ваши ключи
Mapявляются числами, и они ограничены небольшим количеством, то массив или список как структура имеют такую же производительность чтения, как и соответствующая карта (O (1)), но с меньшими накладными расходами.