Производительность Java: карта против списка

Question

Я построил пагинацию дерева в JSF1.2 и Richfaces 3.3.2, потому что у меня много узлов дерева (что-то вроде 80k), и это медленно ..

Итак, в качестве первой попытки я создаю HashMap со страницей и списком узлов страницы.

Но производительность не достаточно хорошая ...

Так что мне было интересно, если это что-то быстрее, чем HashMap, может быть, список списков или что-то.

У кого-то есть опыт с этим? Что я могу сделать?

Заранее спасибо.

---

EDIT.

Большая проблема заключается в том, что мне нужно проверить права пользователей в дочерних узлах дерева. Я знал, что это большая проблема: эта проверка медленная, потому что я должен идти внутрь узлов, у меня нет хорошего способа узнать, есть ли у пользователя разрешение на узел 10-го уровня, без итерации всех их. Плюс к этому, те же три использовались в большем количестве мест ... Основная причина, по которой я делал это разбиение на страницы, заключается в том, что клиентская сторона будет работать очень медленно из-за структуры, создаваемой richfaces, множеством tr и td, браузер просто сходит с ума от этого. Так что, к сожалению, мне нужно загрузить все узлы и разбить на страницы только на стороне клиента, и мне нужно знать, какой из них быстрее выполнять итерацию ...

Извините, мой плохой английский.

Answer 1

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

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

Answer 2

Используемая структура данных всегда зависит от того, как вам нужно хранить данные и как вам нужно получить к ним доступ.HashMap<K, V> должен иметь постоянную временную сложность доступа к значению при условии ключа.Когда вы вызываете get(key), hashCode() для key вычисляется и используется для получения соответствующего значения.Если у вас нет разных ключей с одинаковым хеш-кодом (в этом случае вы, возможно, что-то делали неправильно, поскольку, хотя и не обязательно, разные объекты должны иметь разные хеш-коды, по крайней мере, в большинстве случаев), это обычно быстро.

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

Если вам нужно связать значения с ключами, a Map это путь.И HashMap должен быть достаточно быстрым.

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

Answer 3

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

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

Answer 4

Я бы решил это с помощью метода вызовов javascript / ajax, который выбирает дочерние узлы.