Как называется такая структура данных?

Question

[historydev]

Есть 2 переменных, одна хранит индексы элементов в хеш-таблице по их id, другая массив с элементами. Что позволяет получать доступ к элементу по id за O(1).

let indexes: HashMap<Uuid, usize>;
let objects: Vec<Object>;

Comments

[res2001]

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

[historydev]

res2001, Да, элементов много, для этого и написал, я посчитал что это достаточно распространённая вещь, чтобы иметь название, но найти его не смог.
- Про доп. хэши не думал, т.к. пока использую лишь id

[Василий Банников]

Вообще преимущество будет не таким уж большим, как ты ожидаешь, хотя оно и правда есть (но в реальной жизни врядли сыграет роль)
https://www.youtube.com/watch?v=ncHmEUmJZf4

Answer 1

[Wataru]

Никак не называется. Можно структуры комбинировать для ваших задач, но это частные случаи применения структур, не настолько частые, чтобы давать этой комбинации какое-то имя. Если уж хочется назвать это как-то, то это все еще будет хеш-таблица с какими-то вспомагательными пристройками для каких-то дополнительных нужных вам свойств (итерация).

И вообще, у вас тут намудрено, почему нельзя сделать просто:
let objects: HashMap<Uuid, Object>;

Тут все такой же O(1) доступ к элементу по id. Зачем вам массив? Вы там добились простой и cache-friendly итерации по всем объектам? Не факт, что это уже не реализовано внутри HashMap. По крайней мере во многих языках можно проитерироваться по всем объектам в стандартной хеш-таблице.

Зато у вас там удаление элемента - это что-то сложное. Особенно, если вы не хотите избежать фрагментации и неиспользованного места в массиве.

Comments

[historydev]

почему нельзя сделать просто:

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

Не факт, что это уже не реализовано внутри HashMap

Не знаю, но производительность значительно выросла.

Зато у вас там удаление элемента - это что-то сложное.

Да, с этим ещё предстоит поработать, пока не знаю как буду реализовывать обновление индексов.
- Но эта операция намного реже, чем итерации, у меня может быть 60-100 итераций в секунду, а в некоторых случаях n^2, т.к. необходимо сравнивать каждый с каждым.

Используется в контексте разработки игр.

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

Мне нужна максимальная производительность и все решения принимаются через эту призму.

[Wataru]

historydev, Ну тогда это решение вполне оправдано. Но названия у него особого нет. Может быть, Хеш-таблица с кешем для итерации. В каких-то языках в стандартных библиотеках хеш-таблицы, скорее всего, прямо так и реализованы. Ибо хранить толстые объекты прямо в слабо заполненной таблице дорого. Там хранят указатели, или индексы, а сами элементы лежат где-то рядом в массиве.

[historydev]

Wataru, Как понять кэшем?

[Wataru]

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

Answer 2

[GavriKos]

Хеш-таблица )

Comments

[historydev]

Нет. Моя структура позволяет так-же итерироваться максимально быстро, т.к. я буду итерироваться не по хеш-таблице, а по массиву. Так-же она позволяет не выполнять поиск по массиву, если мне нужен какой-то элемент - я получу его по id за O(1), а не за O(n) в худшем случае при поиске.

Данные массива хранятся в ряд, а хеш-таблицы разбросаны.
- Что делает итерацию по ней медленной