Дерево бинарного поиска и хеш-таблица с точки зрения памяти

Question

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

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

Answer 1

Бинарное дерево поиска - это не что иное, как связанный список с 2 указателями на узел.Требуемая память имеет порядок O (n), т. Е. Соответствует количеству элементов, хранящихся в ней.Хэш-карта, с другой стороны, обычно реализуется как массив.Таким образом, на нем всегда есть свободное место.Прочитайте здесь о том, как хэш-карта реализована в java .: http://java -performance.info / memory-потребление-of-java-data-types-2 /

HashMap построен поверх массива объектов Map.Entry.Реализация гарантирует, что длина этого массива всегда равна как минимум max (размер, емкость) / load_factor.Коэффициент загрузки по умолчанию для HashMap составляет 0,75, а емкость по умолчанию - 16. Коэффициент загрузки указывает, какая часть массива может использоваться для хранения, и это значение находится в диапазоне от 0 до 1. Чем выше коэффициент загрузки, тем меньше места тратится впустую, ноHashMap начинает работать медленнее из-за увеличения частоты столкновений.Чем меньше коэффициент загрузки, тем больше памяти тратится впустую, но производительность HashMap увеличивается из-за меньшей вероятности коллизий.