Почему объект не может иметь позицию массива, связанную с ним, вместо использования хэш-карты?

#hashmap

Вопрос:

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

Однако, почему мы не можем иметь свойство объекта, соответствующее его положению в памяти, чтобы мы могли ссылаться на это при поиске объекта. Что касается вставки, мы могли бы иметь счетчик, хранящий количество объектов, чтобы вставка могла быть O(1).

Почему это невозможно?

1. Итак, вы хотите сказать, что мне нужна ссылка на объект, чтобы я мог получить свойство, которое позволяет мне узнать положение в памяти, чтобы я мог получить ссылку на объект?

2. Возможно, я неправильно понимаю хэш-карты. Обычно, если бы мы искали город, мы бы использовали его название как свойство объекта города, верно? Затем мы бы хэшировали его имя, чтобы найти объект. Мне интересно, не используем ли мы вместо этого свойство position , которое затем сообщит, где находится объект city, а затем мы сможем получить доступ к другим значениям.

3. Если у вас есть свойство position , то у вас уже должен быть экземпляр объекта. Тогда не было бы необходимости искать объект, поскольку он у вас уже есть.

4. Разве не нужен какой-то ключ для поиска объекта в хэш-карте? Разве у нас нет этого ключа, но нет экземпляра?

5. Да, но бессмысленно помещать этот ключ в свойство объекта. Вам нужно знать, как получить ключ, не имея объекта в первую очередь.

Ответ №1:

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

Хеширование этого не делает! Что он делает, так это вычисляет число по значению объекта. Даже в том случае, если Object::hashCode он не переопределен, код все равно не является адресом объекта в памяти.

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

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

1. Я не имел в виду, что он преобразуется непосредственно в адрес объекта, а скорее значение будет хэшировано во что-то, что каким-то образом приведет к полному объекту.

2. Не существует известного практического алгоритма, который генерировал бы идентификатор, однозначно сопоставляемый со ссылкой на объект, без использования чего-то вроде HashMap «под колпаком» для реализации сопоставления. (Но если вы сможете найти или изобрести такой алгоритм … )