请教大数据集分类的问题

现有一个大约有600万条记录的数据集，想要将每条记录根据某个特性进行分类。大概估计约有50－100万个类。这些都保存在内存中以便使用。因此对于这个Java容器的要求是添加和查找这两个基本的操作。现在使用的是ArrayList，发现性能不够理想，当容器容量扩大的时候，添加和查找的计算复杂性也上升了不少；另外试过Hashtable，但是发现虽然查找和添加是恒定的，但是平均所需时间比ArrayList不见得低，甚至更高。想请教一下大家，有没有更好的选择呢？谢谢了额。