Java编程思想之容器小结

1.Java中的容器类库

各容器的实现类及java.util.Collections类中的方法参照java doc

 

2.List及其实现：
List可以对应数据结构中的线性表，所以其实现ArrayList、LinkedList也可以对应线性表中的顺序表和链表，相应也就不难推出了两者的特点。
无论列表的大小如何，ArrayList在随机访问（即使用get()和set()方法）上都很快速（当然背后是有数组支撑的），但是在执行插入或删除操作时则开销会随尺寸的增大而变大（因为需要遍历）；LinkedList则相反，在执行插入或删除操作时很快速（只是修改链接），但是在随机访问上则开销会随尺寸的增大而变大（同样是遍历）。</p>

3.Set及其实现：

 

4.Queue及其实现：
LinkedList及PriorityQueue。两者的差异在于LinkedList是按照放入数据的顺序产生数据，而PriorityQueue则是根据某种优先级的顺序产生数据，而这个“某种优先级”即通过继承Comparable接口实现。

5.Map及其实现：

6.关于散列码（以HashMap为例）：
首先，如果要使用自己写的类作为“键”，需要适当的覆盖.equals()方法和.hashCode()方法，前者作为是否是重复键的判断条件，而要了解后者，请往下看。
假设我们有了一个Entry类的数组，该类里面封装了key和value的键值对，我们的目的是通过给定的key来获取对应的value。一般的方法是遍历数组，用.equals()方法来对key进行判等，但是这样做明显效率很低。于是变引入了哈希的方法来寻找“相等”的key，其想法就是你给我一个数组的下标（int类型），我就能快速定位到这个Entry类数组的某个元素，
于是便通过.hashCode()方法来获得这个下标（实际的HashMap对.hashCode()的值做了处理）。于是.hashCode()便责任重大，如何保证不同的key具有不同的hashCode值。
当然，要保证不同的key具有不同的hashCode值（完美散列）比较难，所以会有冲突的情况，即不同的key具有了相同的hashCode值。于是上面的假设需要修改，即我们的数组中的元素不是Entry类型，而是Entry类型的List，如果不同的key具有相同的hashCode，则把他们放入一个List中。带来的问题就是定位的数组中的元素后，仍需要遍历List，而此List的大小取决于你所编写的生成hashCode的算法，所以要尽量避免出现hashCode扎堆的情况，即散列不均匀。
*关于散列的部分属于个人见解，如有不正确的地方烦请指正。