性能优化:Trove集合库 - 小毛的胡思乱想

性能优化:Trove集合库 - 小毛的胡思乱想

Trove相当于把JDK集合类都针对原生类型处理了一遍，例如int，常见的类有 TIntList、TIntObjectMap、TObjectIntMap、TIntSet，可想而知，维护Trove的工作量是挺大的。

Trove还提供了开放寻址法的Map,Set,LinkedList实现,可以参考Enhance Collection Performance with this Treasure Trove的做法,类似于:

Trove不推荐JDK的entryXX的做法，而是采用了forEach的回调方式。 代码显得更好看些，另外内存方面也有优势，因为使用entryXX的做法，需要创建一个新的数组。

• 自定义Hash策略

我们知道，在JDK集合类里边，有时候是没法自定义Hash策略的，例如String。 不过Trove提供了自定义Hash策略的功能，让你可以根据数据特性进行优化。

• 直接使用原生类型,而不是包装类型

JDK5的自动封箱机制，让我们可以暂时忽略原生类型和包准类型的区别。自动封箱机制只是一种语法糖，实际上并没有提高效率。 直接使用原生类型替代包装类型，明显可以占用更小的内存、运行起来也更有效率。对于基本类型的集合组合，Trove都提供了 等价的集合类。

• 使用开放寻址法，而不是链地址法

大多数的JDK集合类都是采用链地址法实现的，它需要一个地址表，并且元素之间需要链表结点，而Trove采用开放寻址法， 虽然需要保持足够的空闲位置(装载因子小于0.5),但因为不需要链表结点，所以总体上内存占用要更少，性能还要更快一些。

• HashSet不再通过内置HashMap实现

JDK的HashSet是通过内置一个HashSet来实现的，所以白白浪费了value的空间。 Trove提供的THashSet和其他基本类型的HashSet,都不再采用这种方式，直接使用开放地址存储。

• 采用素数长度大小的数组

为了最大程度避免hash冲突，除了保持较小的装载因子，还采用了素数长度大小的数组。具体见gnu.trove.impl.PrimeFinder

Read full article from 性能优化:Trove集合库 - 小毛的胡思乱想