Я также пытался использовать библиотеку Trove LongToIntMap, чтобы посмотреть, что они делают.
Вы пытались посмотреть на код, чтобы увидеть, как они это делают?
Невозможно точно сказать, что вы сделали неправильно в своей реализации, не взглянув на код. Однако одним из возможных улучшений может быть замена LinkedList<Integer> пользовательским типом «список целых чисел», который использует int[] для представления списков. В зависимости от API вашей хеш-таблицы вы сможете избежать затрат на представление ваших значений в виде объектов (в частности, Integer s). (И как следствие, вы получите лучшую производительность и использование пространства, НЕ реализовав API, который имеет универсальные типы для ключей и / или типов значений.)
Для чего бы то ни было, одной ошибкой, которая может привести к снижению производительности, является пренебрежение реализацией изменения размера хеш-таблицы. Без изменения размера сложность операций get и put для таблицы будет O(N), а не O(1) ..., поскольку длина цепочки хеш-функций будет расти пропорционально количеству записей в хеш-таблице.
Наконец, вы должны четко представлять себе, оптимизируете ли вы производительность или использование пространства. Оптимальное решение будет другим ....