Вы правильно всё поняли. Действительно вырождает, тогда добавлю весовую оценку и для этого случая. Не хочу использовать TreeSet из-за того, что наличие цепочек в моём дереве улучшает асимптотику операций, а в TreeSet используются операции с гарантированными сложностями методов. Хотя вашу идею с использованием TreeSet/TreeMap и переискиванием минимального элемента стоит попробовать и сравнить с тем, что у меня получится.
Спасибо за замечания. Исправил ошибки с методом, connectNodes, после исправления ошибок коллекция стала работать немного быстрее, но результаты в таблице решил не трогать, проверил асимптотику и добавил её оценку. Над тестированием коллекции ещё работаю.
Да, дельное замечание, просто структуру писал как раз под этот самый конкретный случай и мне понадобится и нормальный хэш от элемента.
В будущем возможно доведу до ума, а так пока хочу протестировать под свою задачу.
Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
Я реализовал дерево, в котором каждый узел может быть получен из массива на основании ключа — в моём случае хэш-кода элемента.
Ну и вконце-концов я не хэш-таблицу написал.
По поводу 1го пункта именно неэффективное удаление произвольного элемента меня и не устраивает. С пунктом 2 соглашусь. По поводу 3-го я указал, что нужно описать хэш-функцию без коллизий для заданного размера коллекции. Напомню, что в начале статьи я указал для чего писал коллекцию, думаю для матрицы m на n не трудно написать хэш-функцию без коллизий, для элемента хранящего целочисленные координаты точки. За 4-й пункт огромное спасибо, исправлюсь.
Я думал насчет использования min-heap вместо бинарного дерева, но мне показалось, что использование обычного дерева позволит использовать для сравнения любые наборы данных. К тому же, что и min-heap и бинарное дерево имеют одинаковую асимптотику. Использование стандартной коллекции же не даст высокой производительности так как они реализованы для наиболее общих случаев и не используют дополнительные знания о структуре элементов. Что касаемо TreeMap, getFirstEntry наверное и имеет асимптотику O(log n), а вот getFirstKey должен иметь асимптотику как и у TreeSet, т.е. O(1), хотя я могу и ошибаться(чего очень хотелось бы ведь тогда я имею выигрыш в производительности и по этому методу).
А будут ли непроходимые типы местности и будет ли разрешение конфликтов при перемещенти юнитов?
В будущем возможно доведу до ума, а так пока хочу протестировать под свою задачу.
Я реализовал дерево, в котором каждый узел может быть получен из массива на основании ключа — в моём случае хэш-кода элемента.
Ну и вконце-концов я не хэш-таблицу написал.
Я думал насчет использования min-heap вместо бинарного дерева, но мне показалось, что использование обычного дерева позволит использовать для сравнения любые наборы данных. К тому же, что и min-heap и бинарное дерево имеют одинаковую асимптотику. Использование стандартной коллекции же не даст высокой производительности так как они реализованы для наиболее общих случаев и не используют дополнительные знания о структуре элементов. Что касаемо TreeMap, getFirstEntry наверное и имеет асимптотику O(log n), а вот getFirstKey должен иметь асимптотику как и у TreeSet, т.е. O(1), хотя я могу и ошибаться(чего очень хотелось бы ведь тогда я имею выигрыш в производительности и по этому методу).