Ищете хорошее определение карты, и если карты могут быть реализованы с использованием деревьев

Question

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

Но даже после некоторого времени поиска в Google, у меня нет четкого представления о том, что такое карта, чем она отличается от массива или хеш-таблицы, например. Кто-нибудь может дать четкое описание.

Можно ли это, а связанный список записать в виде дерева?

Answer 1

Карта, также известный как Словарь или ассоциативный массив, представляет собой структуру данных, которая позволяет искать значение с помощью ключа.

Карта Java может быть реализована в виде HashMap или TreeMap;это говорит о том, что хеш-карта является одной из возможных реализаций, и да, вы можете реализовать Map как дерево.

Answer 2

Можно ли его (карту) и связанный список записать в виде дерева?

Карты обычно представлены массивами. Чтобы определить, куда запись попадает на карту, вам нужно вычислить ее ключ . Посмотрите здесь для лучшего объяснения.

Деревья (с неопределенным числом узлов) могут быть реализованы с использованием списков (см. здесь для дальнейшего обсуждения). Списки обычно не реализуются как деревья.

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