主要的数据类型
Java集合类可以总括为三大部分, 分别是List, Set, Map;
当然List, Set, Map接口都继承了Collection接口, 也就是Collection接口, 除了(Arrays, Collections两个工具类没有实现该接口), 该接口是其他所有类的共有接口.
为什么说只有三大部分? Queue, Stack呢?
Deque继承了Queue, Deque的实现类LinkedList, 继承了抽象类AbstractSequentialList, 而AbstractSequentialList也间接实现了List的接口.
Stack的实现是通过Vector来实现, 而Vector继承了抽象类AbstractList;
为什么List, Set, Map的接口下有其抽象类的实现?
初始阶段, 我对此也有点疑惑, 这些集合类肯定要存取一些数据的, 而抽象类是无法进行实例化的, 所以抽象类难道仅仅是接口方法的集合? 那么为什么要定义为抽象类而不是接口呢?
但是看了分析和源码之后, 就比较清晰了.
抽象类中的方法确实不可以操作具体的数据对象, 但是它可以调用List, Set, Map或者它继承的接口中的方法, 而这些方法, 是会被具体的类所实现的.
也就是说, 这些抽象类中的方法, 是对与基础方法的动作的有序调用, 从而为我们提供一些常用的方法. 实现了这些方法代码的复用和约束.
List
LinkedList
LinkedList是一个双向队列, LinkedList中的方法非常的丰富, 你可以将他当作栈, 单向队列或者双向队列来进行使用.
Deque对于Queue接口进行了扩展, Queue是一个单向队列的方法集合, 而Deque增加了双向队列的操作, 在队列的两端既能入队也能出队.
LinkedList是一个链表, 内部的节点由内部类Entry实现, Entry中的属性由包含的值, 下一个节点, 上一个节点.
LinkedList的get(int location), 并不是单纯的遍历链表进行获取, 他会判断location所处的位置是位于前半段还是后半段, 从而判断是从链表的头节点开始遍历还是从尾节点开始遍历.
LinkedList是非线程安全的.
ArrayList
ArrayList是一个”动态”数组, 可以进行动态扩容. 具体的元素对象存在一个Object[]数组中, 扩容的数量为(size * 3) / 2 + 1. 默认的size是10.
ArrayList是非现场安全的.
Vector
Vector和ArrayList存取元素对象的方式很相像, 采用的Object[]进行存储.
Vector相比于ArrayList是线程安全的, 而实现线程安全的方式是通过将sychronized添加到方法上保证了并发调用方法的串行执行.
Vector可以指定每次扩容的大小, 默认是10.
Stack
Stack继承了Vector, “可以说Stack是通过Vector”来实现的, 是对于Vector的进一步封装, 对于Stack新添加的方法, 也加了sychronized, 所以Stack也是线程安全的.
Map
这里先说Map, 因为Set的实现是通过对于Map的封装.
HashMap
HashMap是线程不安全的, key和value都支持是null.
HashMap在jdk1.6中, 使用的是拉链表(也就是数组+链表), 在Jdk1.8中进行了改动, 在数组中存储的链表, 一旦链表的长度超过了8, 就将该链表转化为红黑树(一种平衡的二叉搜索树).
HashMap中有一个加载因子,默认为0.75, 一旦table中的实际大小大于数组长度*加载因子, 就会进行重排整个HashMap(rehash)
HashTable
HashTable直接继承了Map接口, 是Directionary抽象类的子类.
HashTable在实现上与jdk1.6中的HashMap很相似, 都是拉链表.
HashTable是线程安全的, 通过对方法添加sychronized关键字来实现.
HashTable中的key和value都不允许是null.
TreeMap
TreeMap实现了NavigableMap接口, 支持一系列的导航方法, 比如返回有序的key集合.
TreeMap默认根据键值的自然顺序进行排序, 可以传入Comparator进行控制.
TreeMap是非线程安全的.
Set
Set是通过Map实现, value默认都是PRESENT的Object对象.
TreeSet和HashSet都是非线程安全的.
当然可以通过Set s = Collections.sychronizedSet(new HashSet()); 来实现线程安全.
TreeSet
TreeSet通过对TreeMap的封装来实现.
TreeSet是一个有序的Set集合, 你可以使用具体的导航方法, 来返回符合值要求的数据, 比如大于, 小于, 等于方法中参数值的元素, 如果不存在, 返回null
HashSet
HashSet通过对HashMap的封装来实现.
// HashSet是通过map(HashMap对象)保存内容的
private transient HashMap<E,Object> map;
// PRESENT是向map中插入key-value对应的value
// 因为HashSet中只需要用到key，而HashMap是key-value键值对；
// 所以，向map中添加键值对时，键值对的值固定是PRESENT
private static final Object PRESENT = new Object();
参考资料 Java 集合系列01之 总体框架