博客分类：
1、Java集合框架的基础接口有哪些？
Collection为集合层级的根接口。一个集合代表一组对象，这些对象即为它的元素。Java平台不提供这个接口任何直接的实现。
Set是一个不能包含重复元素的集合。这个接口对数学集合抽象进行建模，被用来代表集合，就如一副牌。
List是一个有序集合，可以包含重复元素。你可以通过它的索引来访问任何元素。List更像长度动态变换的数组。
Map是一个将key映射到value的对象.一个Map不能包含重复的key：每个key最多只能映射一个value。
一些其它的接口有Queue、Dequeue、SortedSet、SortedMap和ListIterator。
2、HashMap和HashTable有何不同？
（1）HashMap允许key和value为null，而HashTable不允许。
（2）HashTable是同步的，而HashMap不是。所以HashMap适合单线程环境，HashTable适合多线程环境。
（3）在Java1.4中引入了LinkedHashMap，HashMap的一个子类，假如你想要遍历顺序，你很容易从HashMap转向LinkedHashMap，但是HashTable不是这样的，它的顺序是不可预知的。
（4）HashMap提供对key的Set进行遍历，因此它是fail-fast的，但HashTable提供对key的Enumeration进行遍历，它不支持fail-fast。
（5）HashTable被认为是个遗留的类，如果你寻求在迭代的时候修改Map，你应该使用CocurrentHashMap。
HashMap和Hashtable的区别
都属于Map接口的类，实现了将惟一键映射到特定的值上。
一.历史原因:
Hashtable是基于陈旧的Dictionary类的，HashMap是Java 1.2引进的Map接口的一个实现
二.同步性:
Hashtable是线程安全的，也就是说是同步的，而HashMap是线程序不安全的，不是同步的
HashMap 类没有分类或者排序。它允许一个 null 键和多个 null 值。
Hashtable 类似于 HashMap，但是不允许 null 键和 null 值。
Hashtable 比 HashMap 慢，因为它是同步的。
怎样使HashMap同步
HashMap可以通过Map m = Collections.synchronizedMap（hashMap）来达到同步的效果。
3、如何决定选用HashMap还是TreeMap？
对于在Map中插入、删除和定位元素这类操作，HashMap是最好的选择。然而，假如你需要对一个有序的key集合进行遍历，TreeMap是更好的选择。基于你的collection的大小，也许向HashMap中添加元素会更快，将map换为TreeMap进行有序key的遍历。
4、ArrayList和Vector有何异同点？
ArrayList和Vector在很多时候都很类似。
（1）两者都是基于索引的，内部由一个数组支持。
（2）两者维护插入的顺序，我们可以根据插入顺序来获取元素。
（3）ArrayList和Vector的迭代器实现都是fail-fast的。
（4）ArrayList和Vector两者允许null值，也可以使用索引值对元素进行随机访问。
以下是ArrayList和Vector的不同点。
（1）Vector是同步的，而ArrayList不是。然而，如果你寻求在迭代的时候对列表进行改变，你应该使用CopyOnWriteArrayList。
（2）ArrayList比Vector快，它因为有同步，不会过载。
（3）ArrayList更加通用，因为我们可以使用Collections工具类轻易地获取同步列表和只读列表。
ArrayList和Vector的区别
ArrayList与Vector主要从二方面来说.
一.同步性:
Vector是线程安全的，也就是说是同步的，而ArrayList是线程序不安全的，不是同步的。
由于Vector支持多线程操作，所以在性能上就比不上ArrayList了。
三.数据增长:
ArrayList和Vector都有一个初始的容量大小，当存储进去它们里面的元素个数超出容量的时候，就需要增加ArrayList和Vector的存储空间，每次增加存储空间的时候不是只增加一个存储单元，是增加多个存储单元。
Vector默认增加原来的一倍，ArrayList默认增加原来的0.5倍。
Vector可以由我们自己来设置增长的大小，ArrayList没有提供相关的方法。
5、LinkedList与ArrayList有什么区别
两者都实现的是List接口，不同之处在于：
（1）、ArrayList是基于动态数组实现的，LinkedList是基于链表的数据结构。
（2）、get访问List内部任意元素时，ArrayList的性能要比LinkedList性能好。LinkedList中的get方法是要按照顺序从列表的一端开始检查，直到另一端
（3）、对于新增和删除操作LinkedList要强于ArrayList，因为ArrayList要移动数据
LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
List list = Collections.synchronizedList(new LinkedList(…));
6、Array和ArrayList有何区别？什么时候更适合用Array？
Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array是指定大小的，而ArrayList大小是固定的。
Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。尽管ArrayList明显是更好的选择，但也有些时候Array比较好用。
（1）如果列表的大小已经指定，大部分情况下是存储和遍历它们。
（2）对于遍历基本数据类型，尽管Collections使用自动装箱来减轻编码任务，在指定大小的基本类型的列表上工作也会变得很慢。
（3）如果你要使用多维数组，使用[][]比List&List&&&更容易。
7、ArrayList和LinkedList有何区别？
ArrayList和LinkedList两者都实现了List接口，但是它们之间有些不同。
（1）ArrayList是由Array所支持的基于一个索引的数据结构，所以它提供对元素的随机访问，复杂度为O(1)，但LinkedList存储一系列的节点数据，每个节点都与前一个和下一个节点相连接。所以，尽管有使用索引获取元素的方法，内部实现是从起始点开始遍历，遍历到索引的节点然后返回元素，时间复杂度为O(n)，比ArrayList要慢。
（2）与ArrayList相比，在LinkedList中插入、添加和删除一个元素会更快，因为在一个元素被插入到中间的时候，不会涉及改变数组的大小，或更新索引。
（3）LinkedList比ArrayList消耗更多的内存，因为LinkedList中的每个节点存储了前后节点的引用。
8、哪些集合类提供对元素的随机访问？
ArrayList、HashMap、TreeMap和HashTable类提供对元素的随机访问。
9、EnumSet是什么？
java.util.EnumSet是使用枚举类型的集合实现。当集合创建时，枚举集合中的所有元素必须来自单个指定的枚举类型，可以是显示的或隐示的。EnumSet是不同步的，不允许值为null的元素。它也提供了一些有用的方法，比如copyOf(Collection c)、of(E first,E…rest)和complementOf(EnumSet s)。
10、哪些集合类是线程安全的？
Vector、HashTable、Properties和Stack是同步类，所以它们是线程安全的，可以在多线程环境下使用。Java1.5并发API包括一些集合类，允许迭代时修改，因为它们都工作在集合的克隆上，所以它们在多线程环境中是安全的。
11、并发集合类是什么？
Java1.5并发包（java.util.concurrent）包含线程安全集合类，允许在迭代时修改集合。迭代器被设计为fail-fast的，会抛出ConcurrentModificationException。一部分类为：CopyOnWriteArrayList、 ConcurrentHashMap、CopyOnWriteArraySet。
12、BlockingQueue是什么？
Java.util.concurrent.BlockingQueue是一个队列，在进行检索或移除一个元素的时候，它会等待队列变为非空；当在添加一个元素时，它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分，主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间，或消费者有可用的对象，因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现，比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。
13、队列和栈是什么，列出它们的区别？
栈和队列两者都被用来预存储数据。java.util.Queue是一个接口，它的实现类在Java并发包中。队列允许先进先出（FIFO）检索元素，但并非总是这样。Deque接口允许从两端检索元素。
栈与队列很相似，但它允许对元素进行后进先出（LIFO）进行检索。
Stack是一个扩展自Vector的类，而Queue是一个接口。
14、Collections类是什么？
Java.util.Collections是一个工具类仅包含静态方法，它们操作或返回集合。它包含操作集合的多态算法，返回一个由指定集合支持的新集合和其它一些内容。这个类包含集合框架算法的方法，比如折半搜索、排序、混编和逆序等。
15、Comparable和Comparator接口是什么？
如果我们想使用Array或Collection的排序方法时，需要在自定义类里实现Java提供Comparable接口。Comparable接口有compareTo(T OBJ)方法，它被排序方法所使用。我们应该重写这个方法，如果“this”对象比传递的对象参数更小、相等或更大时，它返回一个负整数、0或正整数。但是，在大多数实际情况下，我们想根据不同参数进行排序。比如，作为一个CEO，我想对雇员基于薪资进行排序，一个HR想基于年龄对他们进行排序。这就是我们需要使用Comparator接口的情景，因为pareTo(Object o)方法实现只能基于一个字段进行排序，我们不能根据对象排序的需要选择字段。Comparator接口的compare(Object o1, Object o2)方法的实现需要传递两个对象参数，若第一个参数比第二个小，返回负整数；若第一个等于第二个，返回0；若第一个比第二个大，返回正整数。
16、Comparable和Comparator接口有何区别？
Comparable和Comparator接口被用来对对象集合或者数组进行排序。Comparable接口被用来提供对象的自然排序，我们可以使用它来提供基于单个逻辑的排序。
Comparator接口被用来提供不同的排序算法，我们可以选择需要使用的Comparator来对给定的对象集合进行排序。
17、我们如何对一组对象进行排序？
如果我们需要对一个对象数组进行排序，我们可以使用Arrays.sort()方法。如果我们需要排序一个对象列表，我们可以使用Collection.sort()方法。两个类都有用于自然排序（使用Comparable）或基于标准的排序（使用Comparator）的重载方法sort()。Collections内部使用数组排序方法，所有它们两者都有相同的性能，只是Collections需要花时间将列表转换为数组。
18、当一个集合被作为参数传递给一个函数时，如何才可以确保函数不能修改它？
在作为参数传递之前，我们可以使用Collections.unmodifiableCollection(Collection c)方法创建一个只读集合，这将确保改变集合的任何操作都会抛出UnsupportedOperationException。
19、我们如何从给定集合那里创建一个synchronized的集合？
我们可以使用Collections.synchronizedCollection(Collection c)根据指定集合来获取一个synchronized（线程安全的）集合。
20、集合框架里实现的通用算法有哪些？
Java集合框架提供常用的算法实现，比如排序和搜索。Collections类包含这些方法实现。大部分算法是操作List的，但一部分对所有类型的集合都是可用的。部分算法有排序、搜索、混编、最大最小值。
21、Java集合框架相关的有哪些最好的实践？
（1）根据需要选择正确的集合类型。比如，如果指定了大小，我们会选用Array而非ArrayList。如果我们想根据插入顺序遍历一个Map，我们需要使用TreeMap。如果我们不想重复，我们应该使用Set。
（2）一些集合类允许指定初始容量，所以如果我们能够估计到存储元素的数量，我们可以使用它，就避免了重新哈希或大小调整。
（3）基于接口编程，而非基于实现编程，它允许我们后来轻易地改变实现。
（4）总是使用类型安全的泛型，避免在运行时出现ClassCastException。
（5）使用JDK提供的不可变类作为Map的key，可以避免自己实现hashCode()和equals()。
（6）尽可能使用Collections工具类，或者获取只读、同步或空的集合，而非编写自己的实现。它将会提供代码重用性，它有着更好的稳定性和可维护性。
22、在Java中，HashMap是如何工作的？
HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法，在put和get方法中，它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候，HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中，所以如果存在entry，它使用equals()方法来检查传递的key是否已经存在，如果存在，它会覆盖value，如果不存在，它会创建一个新的entry然后保存。当我们通过传递key调用get方法时，它再次使用hashCode()来找到数组中的索引，然后使用equals()方法找出正确的Entry，然后返回它的值。下面的图片解释了详细内容。
其它关于HashMap比较重要的问题是容量、负荷系数和阀值调整。HashMap默认的初始容量是32，负荷系数是0.75。阀值是为负荷系数乘以容量，无论何时我们尝试添加一个entry，如果map的大小比阀值大的时候，HashMap会对map的内容进行重新哈希，且使用更大的容量。容量总是2的幂，所以如果你知道你需要存储大量的key-value对，比如缓存从数据库里面拉取的数据，使用正确的容量和负荷系数对HashMap进行初始化是个不错的做法。
gaojingsong
浏览: 357932 次
来自: 深圳
你好，哥们还有源码 ？能给看下 ？
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'Posts - 139,
Articles - 0,
Comments - 9
Simonme 博客
15:01 by chen.simon, ... 阅读,
Google后发现大多数文章都是通过LinkedList类实现，当然JDK有自带的Stack类
容器（集合）框架如下：&
集合类存放于java.util包中。集合类存放的都是对象的引用，而非对象本身。
集合类型主要有3种：set(集）、list(列表）和map(映射)。
Collection接口
│├LinkedList
│├ArrayList
顺序结构动态数组类
│└Vector
│ └Stack 栈
├Hashtable
&Collection&--Set&--HashSet
&Collection&--Set&--HashSet&--LinkedHashSet
&Collection&--Set&--SortedSet（也是接口）&--TreeSet
LinkedList, 查阅JDK
。实现所有可选的列表操作，并且允许所有元素(包null)
LinkedList类还为在列表的开头及结尾get,remove和insert元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈，队列或双端队列
提供了通常的push和pop操作，以及取堆栈顶点的peek方法，测试堆栈是否为空的empty方法，在堆栈中查找项并确定离栈顶的距离，共五个方法。
JDK中实现这个类本身继承自Vector这个类(since
栈和队列都属于线性结构，是两种在运算上受到某些限制的特殊线性表，他们比一般线性表更简单。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，称为栈顶(top)，另一端为固定的一端，称为栈底
栈顶，栈底，空栈，栈的特性，
退栈，进栈
初始化栈，进栈push，出栈pop，，取栈顶元素（即是查看下一个要出栈的元素，也叫peek），判断空
用LinkedList实现stack
package org.simoncook.
import java.util.LinkedL
public class MyStack {
&&&&&&& private
LinkedList ll = new LinkedList();
&&&&&&& public
void push(Object obj){
&&&&&&&&&&&&&&& //将指定元素插入此列表的开头。
&&&&&&&&&&&&&&& ll.addFirst(obj);
&&&&&&& public
Object pop(){
&&&&&&&&&&&&&&& //移除并返回此列表的第一个元素.
&&&&&&&&&&&&&&& return
ll.removeFirst();
&&&&&&& public
Object peek(){
&&&&&&&&&&&&&&& //
返回此列表的第一个元素。
&&&&&&& &&&&&&& return ll.getFirst();
&&&&&&& public
boolean empty(){
&&&&&&&&&&&&&&& return
ll.isEmpty();
数据结构队列
/blog/more.asp?name=eaglebetter&id=17232
队列（Queue）的定义
队列的特性队列的实例队 列的基本运算
（1） 入队操作：InQueue（q，x）
（2）出队操作：OutQueue（q，x）
（3）读队头元 素：ReadFront（q，x）
（4）显示队列中元素ShowQueue（q）
（5）判队空操作：QEmpty（q）
（6）判 队满操作：QFull（q）
（7）求队列长度Qlen（q）
实现代码：
package com.gc.
import java.util.*;
public class MyQueue {
&private LinkedList ll=new LinkedList();
//入队操作
&public void put(Object o){
&&ll.addLast(o);
&//使用removeFirst()方法，返回队列中第一个数据，然后将它从队列 中删除
//出队操作
&public Object get(){
&&return ll.removeFirst();
&public boolean empty(){
&&return ll.isEmpty();
Java???u??stackM?CQueueGoogleZ??jh?Oq?LinkedList???A?MJDK?Stack?^?JDKX?e]X^[pUGX?s_java.util]CX?sO?HAD?HCX?Dn3Gset(^Blist(C^Mmap(Mg)CCollectionfuList fxuLinkedList ?xuArrayList ???????x|Vector Vqx |Stack ?MapfuHashtableuHashMap|Setf&Collection&--Set&--HashSet&Collection&--Set&--HashSet&--LinkedHashSet&Collection&--Set&--SortedSet]]Of^&--TreeSetLinkedList, d?JDKListf?C??C??i?C@A}B?(]null)LinkedList???bC???get,removeMinsertF?@RWkC?@???C@?A?C??C`N??OPBJDKStack?Fq`pushMpop@AH???peekkA???O_?emptykAb?d?}w??ZA@?kCJDK??????Vector???(since JDK1.0)?u? ?w???M?C?_??AO?b?WYS?AL?@???C?(stack)O?JM?ub?P@?@S?C?JM?@A????(top)At@?Tw@A?????A?A?A?SAh?A????:l?A??pushAX?popAA??]YOdU@?nX?A]speek^AP?LinkedList??stack?DnO?? ??pushAX?popAA???L?kpackage org.simoncook.import java.util.LinkedLpublic class MyStack {&& &&& &private LinkedList ll = new LinkedList();&& &&& &public void push(Object obj){&& &&& &//?wJC??C&& &&& &ll.addFirst(obj);&& &}&& &&& &public Object pop(){&& &&& &//}^C@?.&& &&& &return ll.removeFirst();&& &}&& &&& &public Object peek(){&& &&& &// ^C@?C&& &&& &return ll.getFirst();&& &}&& &&& &public boolean empty(){&& &&& &return ll.isEmpty();&& &}}?u??C?/blog/more.asp?name=eaglebetter&id=17232?C]Queue^w??CS?C?? C?]1^ J?@GInQueue]qAx^]2^X?@GOutQueue]qAx^]3^??? GReadFront]qAx^]4^??CShowQueue]q^]5^P?@GQEmpty]q^]6^P ??@GQFull]q^]7^D?C?Qlen]q^??N?Gpackage com.gc.import java.util.*;public class MyQueue {&private LinkedList ll=new LinkedList();//J?@&public void put(Object o){& ll.addLast(o);&}&//removeFirst()kA^?C@??uAMZ???C ?//X?@&public Object get(){& return ll.removeFirst();&}&&public boolean empty(){& return ll.isEmpty();&}19432人阅读
源码与设计模式（12）
我们的世界不应该只有“胡萝卜”
进入正题之前容我先扯点别的。
最近突然想到了一个驴子和胡萝卜不得不说的故事。说是一个人坐在驴子背上，用一根长杆绑着一根胡萝卜，然后把胡萝卜悬到驴子的面前，驴子以为只要向前走一步就可以吃到胡萝卜，于是不停地向前走，可是它始终无法吃到这根萝卜。
一千个读者就有一千个哈姆雷特，当然不同的人对这个故事也会有不同的理解。比如我们为了生活拼命地工作，却永远达不到财务自由，我们是不是也像一只忙碌的“驴子”呢？
所以，我们的世界不应该只有“胡萝卜”。
不识庐山真面目，只缘身在此山中。有时候跳出来，用“上帝视角”来看看这个我们存在的世界，说不定会有不一样的发现。生活如此，学习也是如此。
数据结构和算法与Java集合框架
接下来我们再来看一个故事。本故事纯属虚构，如有雷同，纯属你抄我。
地点：A公司办公室
人物：小明——一个工作一年的Android小菜鸟；B大大——A公司Android开发负责人，Android高级开发工程师
起因：小明想到A公司工作，由B大大对他进行面试。
经过：B大大说，小明啊，你刚毕业一年，算法应该还不错，咱们先来一个简单的吧。有一个迷宫，由n行m列的单元格组成，每一个单元格要么是空地要么是障碍物，障碍物是不能穿过的。任取两个不是障碍物并且不相同的点p和q，怎么找到p到q的最短路径呢？
小明支支吾吾，边挠头边说，那个B大大，我上学的时候贪玩没有好好学数据结构和算法，毕业后工作中也基本没有用到过，所有不怎么会了。。。
B大大露出一副安慰的表情，说，恩，可以理解。那咱们问点工作中常用的吧。
小明顿时来了精神，一顿小鸡啄米似的点头。
B大大说，那你先说说你工作中接触到的数据结构吧。
小明张口就来，数组、ArrayList、Map。
B大大又等了一会，看小明实在没有了下文，又继续问道，那你了解Java集合框架的设计思路吗？
小明说，设计思路？为什么要了解，没时间啊，老夫写代码就是一把梭！复制、粘贴，拿起键盘就是干！效率刚刚的。
B大大心里一万只羊驼飞奔而过，嘴角抖了抖，说，那个小明，咱们今天的面试就先到这吧，有结果了我再让Hr通知你好吧。
然后，然后就没有然后了。
虽然这个故事是虚构的，但是不难找出来现实版的小明求职记。那么从这个故事我们可以反思一些什么呢？
首先个人认为数据结构和算法、设计模式这些属于内功，俗话说练拳不练功，到老一场空，有了这些内功我们才能更好的去使用各种招式，否则只是徒有其形罢了。要知道一个花架子是没有多少战斗力的。
其次，了解了源码里的设计思路，用起来才能更得心应手，同时也能提高自己的设计能力。而且就像开篇说的，我们要善于从宏观的角度去看一些事情，这样才能看到更多，收获更多。当然成长为高级工程师，迎娶白富美，走向人生巅峰不是梦啦。
数据结构和算法
这里我不打算再过多的重复数据结构和算法的定义、算法的时空复杂度这些问题，只过一下各个数据结构的特性。因为算法对数据结构的通用操作类似，基本都包括插入、查找、删除、遍历和排序等，所以我们重点关注下这些操作上的性能。
数组：优点是查找快，如果知道下标，可以非常快的存取。缺点是插入慢，删除慢，大小固定。
有序数组：优点是比无序数组查找快。缺点是插入和删除慢，大小固定。
栈：提供后进先出方式的存取。缺点是存取其他项很慢。
队列：提供先进先出方式的存取。缺点是存取其他项很慢。
链表：优点是插入快，删除快。缺点是查找慢。
二叉树：优点是查找、插入、删除都快（如果树保持平衡）。缺点是删除算法复杂。
红-黑树：优点是查找、插入、删除都快，树总是平衡的。缺点是算法复杂。
2-3-4树：优点是查找、插入、删除都快，树总是平衡的，类似的树对磁盘存储有用。缺点是算法复杂。
哈希表：优点是如果关键字已知，则存取极快，插入快。缺点是删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分。
堆：优点是插入、删除快，对最大数据项的存取很快。缺点是对其他数据项存取慢。
图：对现实世界建模。有些算法慢且复杂。
Java中集合框架的总体设计
良好的设计总是相似的。它使用一个好用的接口来封装一个特定的功能，它有效的使用CPU与内存，等等。
我们常用的数据结构有线性表、栈、队列等线性结构，还有集合以及哈希表，所以我们只讨论这几种结构的设计。
在分析Java集合框架的设计思路之前，我们先来认真思考一个问题，如果让你去设计Java的集合框架，你会怎么做？
小明的做法
如果是小明来设计的话，我猜他会选择一种简单粗暴的方式，分别去写几个类来实现线性表、栈、队列、集合以及哈希表。好，那么问题来了。
假如用户想自定义一个用自己方式实现的线性表，那么他该如何操作？
假如开始用户使用了无序的线性表，然后因为某个需求要改成有序的，那么用户需不需要进行很大改动呢？
假如小明要对已有的Api进行升级，要加入无序线性表的另一种更高性能的实现，他需要改动多少东西？
其实把三个问题总结一下无非就是维护和扩展成本的问题。
我们的思路
首先我们先来参考一下其他功能的设计思路，比如Android中的View类族和Context类族。我们分析一下他们的代码的结构层次。
View类族的类图如下
Context类族的类图如下
我们来分下一下这两个模块设计上相似的地方
整体的代码结构都像一棵树，有一个唯一的根节点，这个根节点封装了这个类族的公有特性
有一层抽象类或者类似抽象类作用的类，它们实现了通用的方法。方便用户扩展自己的业务。
有具体的实现，用户可以直接使用这些具体实现。
这些相似的地方其实可以归纳为三个结构层次
一个高度抽象的根节点接口，可以再抽象出一组带有具体操作的接口来实现我们的根节点
一组抽象类，实现带有具体操作接口的部分方法，方便用户快速扩展自己的业务。
具体的实现，方便用户直接调用。
这个套路在Android源码中是很常见的，这样做的好处也显而易见，比较易于维护和扩展。
源码的实现思路
然后我们来看看是不是像我们说的那样，Java的集合框架也是这种套路呢？
我们来看下集合框架的类图
这张图是我从网上找的，不过不影响我们的分析。如果有侵权，请告诉我，我会删除。
从这张图我们可以很清晰的看出来，套路一模一样有没有。
首先由于Map和Collection的相似点很少，所以这两部分的根节点是分开的。
我们拿Collection这部分来说，首先定义了一组接口。Collection是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，它主要又分为：List、Set和Queue，分别对应线性表、集合、队列，实现对应的接口，则有了对应数据结构的特性。这是第一个结构层次。
然后又定义了一组抽象类，我们拿AbstractCollection类来说，先看下注释
* This class provides a skeletal implementation of the &tt&Collection&/tt&
* interface, to minimize the effort required to implement this interface. &p&
这个类实现了Collection接口的骨架，用户继承这个类可以用最小化的时间来实现一个集合。
其他的抽象类也都是各个数据结构的骨架，用户可以自定义自己的集合。
最后第三个层次就是具体的实现类了，比如我们常用的ArrayList、LinkedList等等。比如LinkedList实现了List和Queue接口，那么它既有队列先进先出的特性，又有List可以通过位置访问元素的特性。
源码的具体实现
Collection部分
Collection是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，它主要又分为两大部分：List和Set。
Collection接口
* The root interface in the &i&collection hierarchy&/i&.
A collection
* represents a group of objects, known as its &i&elements&/i&.
* collections allow duplicate elements and others do not.
Some are ordered
* and others unordered.
The JDK does not provide any &i&direct&/i&
* implementations of this interface: it provides implementations of more
* specific subinterfaces like &tt&Set&/tt& and &tt&List&/tt&.
This interface
* is typically used to pass collections around and manipulate them where
* maximum generality is desired.
集合层次结构的根。一个集合包含一组元素对象。有一些集合允许重复元素，有一些不允许；有一些集合元素是有序的有一些不是。
定义的方法：
int size()
boolean isEmpty()
boolean contains(Object o)
Iterator iterator()
Object[] toArray()
T[] toArray(T[] a)
boolean add(E e)
boolean remove(Object o)
boolean containsAll(Collection c)
boolean addAll(Collection c)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
void clear()
Iterator接口
迭代器接口，用于遍历集合。
boolean hasNext()
default void remove()
default void forEachRemaining(Consumer action)
AbstractCollection抽象类
* This class provides a skeletal implementation of the &tt&Collection&/tt&
* interface, to minimize the effort required to implement this interface. &p&
* To implement an unmodifiable collection, the programmer needs only to
* extend this class and provide implementations for the &tt&iterator&/tt& and
* &tt&size&/tt& methods.
(The iterator returned by the &tt&iterator&/tt&
* method must implement &tt&hasNext&/tt& and &tt&next&/tt&.)&p&
* To implement a modifiable collection, the programmer must additionally
* override this class's &tt&add&/tt& method (which otherwise throws an
* &tt&UnsupportedOperationException&/tt&), and the iterator returned by the
* &tt&iterator&/tt& method must additionally implement its &tt&remove&/tt&
* method.&p&
* The programmer should generally provide a void (no argument) and
* &tt&Collection&/tt& constructor, as per the recommendation in the
* &tt&Collection&/tt& interface specification.&p&
* The documentation for each non-abstract method in this class describes its
* implementation in detail.
Each of these methods may be overridden if
* the collection being implemented admits a more efficient implementation.&p&
这个类实现了Collection接口的骨架，用户继承这个类可以用最小化的时间来实现一个集合。
如果我们需要实现一个简单的集合，只需要重写iterator()、int size()和add(E o)方法。同时这个集合的特性取决于我们的实现方式。
线性表(List):零个或多个数据元素的有限序列。
* An ordered collection (also known as a &i&sequence&/i&).
The user of this
* interface has precise control over where in the list each element is
* inserted.
The user can access elements by their integer index (position in
* the list), and search for elements in the list.&p&
一个有序的集合，用户可以通过这个接口精确的控制在哪里插入元素。用户可以通过元素的int下标来拿到元素和查找List中的元素。可以有重复元素。
List接口的扩展方法：
add(int index, E element)
addAll(int index, Collection c)
E get(int index)
int indexOf(Object o)
int lastIndexOf(Object o)
ListIterator listIterator()
ListIterator listIterator(int index)
E remove(int index)
default void replaceAll(UnaryOperator operator)
E set(int index, E element)
default void sort(Comparator c)
ListIterator接口
* An iterator for lists that allows the programmer
* to traverse the list in either direction, modify
* the list during iteration, and obtain the iterator's
* current position in the list. A {@code ListIterator}
* ha its &I&cursor position&/I& always
* lies between the element that would be returned by a call
* to {@code previous()} and the element that would be
* returned by a call to {@code next()}.
一个为List设计的迭代器，允许用户从任意方向遍历List，在遍历的过程中修改List，并且获得迭代器的当前位置。
ListIterator的扩展方法：
boolean hasPrevious()
E previous()
int nextIndex()
int previousIndex()
void set(E e)
void add(E e)
集合(Set):是标记着具有某些相关联或相互依赖的一系列离散数据。
* A collection that contains no duplicate elements.
More formally, sets
* contain no pair of elements &code&e1&/code& and &code&e2&/code& such that
* &code&e1.equals(e2)&/code&, and at most one null element.
As implied by
* its name, this interface models the mathematical &i&set&/i& abstraction.
一个不包含重复元素的集合。所谓不重复是指不能有两个元素e1.equals(e2)，并且至多包含一个null元素。
Set接口只包含继承自Collection的方法，并增加了重复的元素被禁止约束性。
集还增加了对equals和hashCode操作的行为更强的契约，允许Set集合实例进行有意义的比较，即使他们的实现类型不同。
队列(Queue):是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
* A collection designed for holding elements prior to processing.
* Besides basic {@link java.util.Collection Collection} operations,
* queues provide additional insertion, extraction, and inspection
* operations.
Each of these methods exists in two forms: one throws
* an exception if the operation fails, the other returns a special
* value (either {@code null} or {@code false}, depending on the
* operation).
The latter form of the insert operation is designed
* specifically for use with capacity-restricted {@code Queue}
* in most implementations, insert operations cannot
队列的接口，提供了Collection之外的插入、提取和检索操作。这三种操作都有两种形式，一种失败之后会抛出异常，另一种会返回特定的值（null或者false）。
Map是一个映射接口，其中的每个元素都是一个key-value键值对。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。
对应关系f称为散列函数，又称为哈希(Hash)函数。
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或哈希表(Hash table)。
* An object that maps keys to values.
A map cannot co
* each key can map to at most one value.
一个匹配key和value的对象。
包含的主要方法：
int size()
boolean isEmpty()
boolean containsKey(Object key)
boolean containsValue(Object value)
V get(Object key)
V put(K key, V value)
V remove(Object key)
putAll(Map m)
Set keySet()
Collection values()
entrySet()
boolean equals(Object o)
int hashCode()
Map接口中包含一个Entry接口，这是对Map一个条目的封装即一个键值对。可以通过它操作条目的键值。
AbstractMap
实现Map接口的骨架，减小用户创建自定义Map的成本。
如果你想创建一个自己的可以修改的Map，比如重写V put(K key, V value)和V remove(Object key)方法以及实现entrySet().iterator()。
SortedMap接口
* A {@link Map} that further provides a &em&total ordering&/em& on its keys.
* The map is ordered according to the {@linkplain Comparable natural
* ordering} of its keys, or by a {@link Comparator} typically
* provided at sorted map creation time.
This order is reflected when
* iterating over the sorted map's collection views (returned by the
* {@code entrySet}, {@code keySet} and {@code values} methods).
* Several additional operations are provided to take advantage of the
* ordering.
(This interface is the map analogue of {@link SortedSet}.)
提供了进一步对Map的key进行排序的操作。
扩展的方法：
Comparator comparator()
K firstKey()
K lastKey()
SortedMap headMap(K toKey)
SortedMap subMap(K fromKey, K toKey)
SortedMap tailMap(K fromKey)
关注博主是一种态度，评论博主是一种欣赏！！
最后，欢迎大家关注我的微信公众号：CoderTopia。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：185514次
积分：2159
积分：2159
排名：第19304名
原创：38篇
评论：103条
长期为您推荐优秀博文、开源项目、视频等，进入还有好玩的等着你。扫一扫下方二维码或搜索微信号codertopia即可关注：
文章：13篇
阅读：30500
阅读：25335
阅读：33786
(1)(1)(1)(1)(3)(5)(5)(1)(2)(2)(6)(10)(2)(1)
(window.slotbydup = window.slotbydup || []).push({
id: '4740887',
container: s,
size: '250,250',
display: 'inlay-fix'