概述
FInt是一個用Java編寫的集合工具包,以下簡稱FI。因為Java自帶的集合包(java.util)不能直接操作基本數據類型,而必須使用基本類型的“包裝”類,這多少會影響程序性能或造成一些不便。FI實現了鍵或值是整數類型的集合工具包,但別的數據類型沒有實現, 因為要實現所有數據類型的話,類的數目會很大,如果全靠手工編寫的話工作量也是很大的,而且也難維護,因此如果以后真要實現的話,考慮使用類似于模板的方法。
下載方法
構成簡介
FI主要提供了面向整數的集合、映射、列表的接口以及相應的迭代器。
FI主要使用了三種方式實現了上面的接口:
- AVL樹,所有以AVL開頭的類。一般來說它的查找性能比紅黑樹略好,但對于要頻繁地插入刪除的情況,性能不如紅黑樹。
- 紅黑樹,所有以RB開頭的類。Java系統庫的中的TreeMap實現也是采用紅黑樹。
- 哈希表,所有以Hash開頭的類。由于采用了和Java系統庫中HashMap不同的沖突解決辦法,在沖突比較嚴重(裝載因子設得偏大)時仍有較好的性能,因此在沒有特殊情況時,推薦選用這些類。當然,基于哈希表的類比其他的類要占用更多的空間,但可根據情況調節裝載因子來達到空間和時間的平衡。
- BitVector,它基本上算是一個系統庫中BitSet的替代品,但不同的是,它也實現了整數集合接口IntSet,由于受位組實現方式的限制,集合只能保存非負整數。其缺點很明顯,當集合中有一個數值很大的元素時,將導致內存的的極大浪費。不過其也有無與倫比的優點,就是插入和搜索速度都極快,基本上要比其他實現方式快一個數量級以上,因此在元素的值都比較小且非負的情況下推薦使用。
- 整數列表,基本上就是系統庫中等價類的“整數版”而已。
訪問者模式:Visitor。
FI提供了多種訪問者接口,一般來說,在滿足需要的前提下,采用訪問者模式比迭代器模式更高效些。
性能
迄今為止,只拿FInt和系統庫中等價的類做過比較,從簡單的測試來看,集合和映射的插入、搜索操作都比系統庫快。另外因為FI的哈希表采用紅黑樹來處理沖突,因此裝載能力比系統庫要強些(在裝載因子較大時仍有較好的性能)。
至于其他的支持基本數據類型的集合庫,如Trove等,還沒拿FI和它們做過比較。