java集合框架分析(工作两年后)

一 ArrayList，可自动扩充容量的动态数组

  以前金蝶中间件的研发总经理张勇和其他人都说过，java的集合框架源码写的很牛B，看了ArrayList后，开始明白他们的意思了。
  ArrayList基于数组实现，然后，初始化，add，remove的方法，都很具有逻辑性，需要推敲才能理解好，所以代码会巧妙，而且Sun的人写代码比较简洁
  所以ArrayList的代码有两个特点：
  1.每个方法有算法逻辑
  2.每个方法很简洁，没什么冗余代码

 

二 LinkedList 双向循环列表

LinkedList是基于双向---循环的列表，双向循环的特性用的很彻底
所以head元素被用到的地方很多，add，addBefore()和remove这些方法都用到了
非常具有算法逻辑！值得借鉴！
http://www.iteye.com/topic/553199

 

三 Hashmap 数组+链表实现(第三年)

http://uuubd.iteye.com/blog/1447129
http://zhangshixi.iteye.com/blog/672697

负载因子默认是7.5，如果越大，空间利用率越好，但会增加查询时间也越多
hash数据的空间利用率越高，但是为什么查询时间越多呢？
答：简单原因是：不管负载因子多大，都存在hash冲突，但负载因子大的时候，冲突
在同一个位置上的对象越多，所以，遍历链表时查询的时间花的更多
举个特殊例子：
hashmap已知条件如下：
1.初始大小16
2.hash数组长度为16
3.负载因子为0.75(0.25)
4.hashmap最多容纳12(4)个对象
但是如果发生冲突时，所有对象，但hash到同一个位置上，
当负载因子为0.75，需要遍历的链表长度为4
当负载因子为0.75，需要遍历的链表长度为12
由此看出负载因子越大，查询时间越多

补充一点：也许你会觉得hash到同一个位置上的情况太特殊了，不够信服力，但是我的同事鲍超告诉我，但负载因子越大，冲突的概率越大，无冲突的概率却小
这点可以通过分步(不是分类，这是高中数学统计概的方法，复习一下)的方式来计算概率
有空自己计算一下，我明白了，再过一段时间，我自己在纸上再算一次

哈哈，终于明白负载因子越大，空间利用越大，但查询时间也会越多，所以默认0.75是折中的做法啦！！！