Пользовательская реализация HashTable в Java?

Question

Пользовательская реализация HashTable в Java?

Я решал проблему Quora, и для моего конкретного решения мне нужна была хеш-таблица (длинные ключи, int-значения) для кэширования значений. Я надеялся, что Java HashMap можно улучшить, потому что я знал свои типы данных для ключей и значений, они были примитивами, а также мое проблемное пространство. Я решил наивно реализовать простую хеш-таблицу, используя структуру "массив-связанного списка" (даже мой связанный список был моим собственным классом узлов, который я реализовал). Но я заметил, что моя собственная наивная реализация была примерно в 4 раза медленнее, чем универсальный Java HashMap. Я также попытался использовать библиотеку Trove LongToIntMap, чтобы посмотреть, что они делают. У кого-нибудь есть хорошие предложения по созданию настраиваемой хеш-таблицы Long to Int в Java, которая значительно превосходит Java HashMap?

1

java generics hashmap hashtable trove4j

Источник

user471136 20 авг '11 в 06:24

2 ответа

Другие вопросы по тегам java generics hashmap hashtable trove4j

user309683 20 авг '11 в 06:37 2011-08-20 06:37 · Answer 1 · 2011-08-20 06:37

Взгляните на FastMap от Javolution. Исходный код доступен здесь.

1

Источник

user309683 20 авг '11 в 06:37

user139985 20 авг '11 в 06:40 2011-08-20 06:40 · Answer 2 · 2011-08-20 06:40

Я также попытался использовать библиотеку Trove LongToIntMap, чтобы посмотреть, что они делают.

Вы пытались посмотреть на код, чтобы увидеть, как они это делают?

Невозможно точно сказать, что вы сделали неправильно в своей реализации, не глядя на код. Однако одним из возможных улучшений может быть замена LinkedList<Integer> с пользовательским типом "список целых", который использует int[] представлять списки. В зависимости от API хеш-таблицы вы сможете избежать затрат на представление значений в виде объектов (в частности, Integerс). (И как следствие, вы получите лучшую производительность и использование пространства, НЕ реализовав API, который имеет универсальные типы для ключей и / или типов значений.)

Что бы это ни стоило, одна ошибка, которая может привести к снижению производительности, заключается в пренебрежении реализацией изменения размера хеш-таблицы. Без изменения размеров, сложность get а также put операции на столе будут O(N) скорее, чем O(1)... потому что длина цепочки хеширования будет расти пропорционально количеству записей в хеш-таблице.

Наконец, вы должны четко понимать, оптимизируете ли вы производительность или использование пространства. Оптимальное решение будет другим....