java集合的实现细节
写在前面
本篇文章参考了李刚的《疯狂java：突破程序员基本课的16课》的第三课。是自己在学习完java基础后进行的一次巩固。
Set和Map
从类继承图出发，我们分别来看一下Set和Map的类继承关系。
Set接口
Map接口
很明显的发现两个接口的类继承关系几乎是一样的
Set——–Map
HashSet———HashMap
TreeSet————TreeMap
LinkedHashSet———–LinkedHashMap
这样明显的对应关系绝对不是偶然。
首先Set接口的特点是什么，元素无序且重复。而Map的key的特点呢，也是无序并且不重复的，这样相似的特点意味着Set和Map是可以相互转换的。
我们再来考虑，将Map中的key和value看做一个整体，由于key是无序且不重复的，那么key-value这个整体也是无序不可重复的。即可将key-vaue这个整体看做Set的一个元素，有了这样的一个思路就可以轻松实现Set向Map的转换了。
HashSet和HashMap
首先要知道的一个知识点是：
集合类存放的并不是真正的对象，而是对象的引用。
class Person{
String name;
int age;
public Person(String name,int age) {
this.name=name;
this.age=age;
}
} public static void main(String[] args) {
Person p1=new Person("p1", 18);
Person p2=new Person("p2", 19);
ArrayList list=new ArrayList();
list.add(p1);
list.add(p2);
System.out.println(p1==list.get(0));
System.out.println(p2==list.get(1));
}运行结果
true
true这里以ArrayList为例说明集合。ArrayList是顺序存储每个元素的，那么HashSet和HashMap是怎么存储元素的呢。
1.先分析HashSet
这是HashSet中add方法的源码
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}可以看出HashSet存储元素依然是借助于Map实现的。
2.再来看看HashMap
下面是HashMap的put方法的源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
可以看出，put方法与key的hash值有关。Map存放对象时，首先根据key值计算出元素应该存放的位置，而value则依附于key的位置，也就是说元素存放的位置只与key值有关，这也解释了为什么key值不可以重复，因为如果key值重复将会发生冲突。
HashMap在底层将key-value当做一个整体处理，这个整体就是entry对象。
对于HashSet，他的底层是基于HashMap实现的。所以HashSet和HashMap在实现本质上是相同的。
TreeSet和TreeMap
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}从TreeSet的构造器的源码可以得出结论，TreeSet的底层实现依赖于TreeMap，TreeSet的大部分方法都是直接调用TreeMap的方法实现的。
TreeMap的底层数据结构是红黑树，它将key-value作为entry，将entry作为红黑树的一个节点实现插入和删除操作，由于插入删除都需要遍历树，因此效率不高，但是由于红黑树的特点，可以保持元素的有序性。
Map和List
将Map中的key-value区别看待，所有的key是不可重复的，所可以将所有的key看出一个Set对象，而value却可以重复，因而可将所以的value看做List对象，这样就可以把Map和List也联系起来了。
Map提供get方法，可以通过key值获取values
List提供get方法，可以通过下标获取values
联系:
List相当于所有key都是数字的Map
ArrayList和LinkedList
1.ArrayList和Vector的区别
两者拥有类似的方法，但是Vector是线程安全的。
ArrayList的序列化实现比Vector要安全。
目前Vector已经被ArrayList取代。
2.ArrayList和LinkedList的区别
ArrayList的底层实现实数组而LinkedList的底层实现实双向链表
ArrayList方便查找而插入比较麻烦，LinkedList方便插入而查找需要遍历整个链表。
ArrayList的整体性能优于LinkedList。
选择ArrayList还是LinkedList视使用场景而定，如果需要大量查找则使用ArrayList，如果需要大量的在两端操作数据则使用LinkedList。
Iterator迭代器
Iterator是一个迭代器接口，用来迭代各种Collection集合类，同时他只是一个接口，需要各个集合类提供iterator方法来返回一个迭代器对象，通过迭代器可以实现对集合元素的遍历和删除等操作。
总感觉就要暑假了，大一也快要结束了，所以我希望抓紧每一分每一秒学习新的技术。