本文将详细的聊一下Collection 相关的一些细节
前面说到了Collection包含List、Set等(queue这里不详谈)，前面也说到了List是有序可重复，Set是无序不重复，这是两个特点。那我们就先这两个点总结一下，是怎么实现这两个特点的。
List最常用的是ArrayList/LinkList，ArrayList通过数组的新增进行排序，LinkList通过线性双向线链表实现排序(1.7以前是通过环形的双向链表)
Set最常用的HashSet和LinkedHashSet是通过Hash散列保证唯一性，但是link通过链表的方式实现了Set的有序性，这个是个体的差异，还有一个TreeSet，也是一个个体差异，通过红黑树实现有序和唯一性。
下面详细说一下ArrayList和LinkList的一些特点和区别
ArrayList和LinkList最大的区别就是数据结构，ArrayList是数组，LinkList是链表。从数据结构上看，ArrayList的查询会快一点，因为LinkList的查询走的是链表，需要逐个去查找，而数组本身具有下标索引。
网上说的ArrayList相对新增、删除会慢一点，目前主要的依据是数组结构的新增和删除是用过copy来实现的(保证内存连续)，而链表是通过上一个元素的指向实现。但是有人做过实测证明，在高版本的jdk中体现并不是很明显。所以这个说法是有待商榷的。
ArrayList的扩容：
- 新增扩容，如需扩容，则在原有容量的基础上扩容1.5倍，再把原对象复制过去，再讲需要新增的对象放入N+1的位置；
- 删除降容，将需要删除的下标的位置标记为N，将N+1到数组长度的所有元素复制到N到数组长度-1的位置，然后删除最后一个位置的数据（如果是根据对象删除则需要遍历数组，效率会比较低，所以尽量走下标删除）
LinkList的一些特点
LinkList是线性双线链表(1.7及以上)，每一个LinkList节点对象都包含 first头结点和last尾结点
添加节点时，会调用 linkLast 在尾节点处新增一个节点，如果是按照下标新增节点，需要额外修改上一个节点的下节点指向。
删除节点时，都会统一调用 unlink 方法来释放上一个节点的下节点指向和下一个节点的上节点指向。
值得一提的是，LinkList也实现了 queue ，因为他的数据结构和队列比较类似，都有首节点和尾结点标记，也可以作为队列来使用。
然后来说说Set，HashSet是依靠hashCode和equels来实现唯一性，首先会根据对象的hashCode进行一次重复性校验，如果发现重复，再对对象的equals进行一次校验，如果两次校验都表明重复，那就重复了。在做对象比较和去重实，很多情况都是针对对象的个别或特定的几个属性值去重，这时，我们就需要重写hashCode和equals(如果不重写，那判断的是两个对象的内存地址)。
如上所述，HashSet其实质是一个初始化容量为16的、key和value相同的 HashMap 。其值存在HashMap的key上。 LinkedHashSet 其实质是一个同样的LinkedHashMap。
TreeSet，它的数据结构是红黑树，也就是二叉树(弱平衡二叉树，绝对平衡二叉树性能相对低一点)，所以它是有序的，它的有序是使用比较器实现，如不自定义比较器，将按照默认排序。 TreeSet对象的类必须实现Comparable接口。
转载请注明：迷路的老鼠 » java里集合这些事情-Collection
