多用多学之Java中的Set,List,Map详解
很长时间以来一直代码中用的比较多的数据列表主要是List，而且都是ArrayList，感觉有这个玩意就够了。ArrayList是用于实现动态数组的包装工具类，这样写代码的时候就可以拉进拉出，迭代遍历，蛮方便的。
也不知道从什么时候开始慢慢的代码中就经常会出现HashMap和HashSet之类的工具类。应该说HashMap比较多一些，而且还是面试经典题，平时也会多看看。开始用的时候简单理解就是个键值对应表，使用键来找数据比较方便。随后深入了解后发现
这玩意还有点小奥秘，特别是新版本的JDK对HashMap的改成树后，代码都有点小复杂咯。
Set开始用的较少，只是无意中在一个代码中发现一个TreeSet，发现这个类可以自带顺利，感觉蛮有点意思，才慢慢的发现这也是个好工具啊。
代码写的多了就感觉到基础的重要性，所以在此写一篇小文简单的整理一下对集合的一些知识。
好了，简单的整理一下：
•List：即是列表，支持数组、链表的功能，一般都是线性的
•Map：即是映射表，存储的是键与值的对应关系
•Set：即是集合的意思，主要是用于排重数据及排序
先来看看List
List是用于存放线性数据的一种窗口，比如：用于数组的ArrayList和用于链表的LinkedList。
ArrayList
这是一个数组列表，不过提供了自动扩容的功能，实现List接口，外部操作都是通过接口申明的方法访问，这样即安全又方便。
ArrayList的关键就是自动扩容，在对象初始化时可以设定初始容量，也可以按默认的容量。如果对数组大小没有特别明确可以不指定初始大小，如果明确的话可以指定一个大小，这样减少动态扩容时产生的卡顿。说到这就要说一下扩容是怎么实现的了，看下面的代码：
privatevoidgrow(intminCapacity){
//overflow-consciouscode
intoldCapacity=elementData.length;
intnewCapacity=oldCapacity+(oldCapacity>>1);
if(newCapacity-minCapacity<0)
newCapacity=minCapacity;
if(newCapacity-MAX_ARRAY_SIZE>0)
newCapacity=hugeCapacity(minCapacity);
//minCapacityisusuallyclosetosize,sothisisawin:
elementData=Arrays.copyOf(elementData,newCapacity);
}
grow是在ArrayList在添加元素或者一些容易检查时会触发的一个方法。主要过程：
1、得到数组的长度，并对其进行右移，这样就相当于oldCapacity/2，得到新的长度
2、如果这个长度小于最小容量那么直接就用最小容易
3、如果大于了最大容易则取一个最大值，这里会调用一个hugeCapacity方法，主要是比较minCapacity与MAX_ARRAY_SIZE的，如果minCapacity大于MAX_ARRAY_SIZE则取Integer.MAX_VALUE，否则就取MAX_ARRAY_SIZE，有意思的是MAX_ARRAY_SIZE取的是Integer.MAX_VALUE-8;并不知道这样做的意义是什么
4、最后就是调用一个复制方法将现有数复制到一个新的数组中。
因为有这个复制过程，如果数组比较大，那么老是触发扩容当然就会出现卡顿的情况。所以如果一开始就知道最大值而且很容易增长到这个值，那么开始初始化时就指定大小会有一定的作用。
LinkedList
这是针对链表的工具类，链表的优秀是添加删除啥的比较快，但是查找会慢一些。
至于代码好像也没什么特别的，就是一串指针链接起来，当然Java中就使用对象来代替，建立一个Node的对象，Node本身指向了前一个Node和后一个Node，这就是链表的结构：
privatestaticclassNode<E>{
Eitem;
Node<E>next;
Node<E>prev;
Node(Node<E>prev,Eelement,Node<E>next){
this.item=element;
this.next=next;
this.prev=prev;
}
}
然后用两个Node指向头和尾就完成了，下面的代码：
/** *Pointertofirstnode. *Invariant:(first==null&&last==null)|| *(first.prev==null&&first.item!=null) */ transientNode<E>first; /** *Pointertolastnode. *Invariant:(first==null&&last==null)|| *(last.next==null&&last.item!=null) */ transientNode<E>last;
看一个add操作：
/**
*Linkseaslastelement.
*/
voidlinkLast(Ee){
finalNode<E>l=last;
finalNode<E>newNode=newNode<>(l,e,null);
last=newNode;
if(l==null)
first=newNode;
else
l.next=newNode;
size++;
modCount++;
}
过往就是：
1、获取到最后的Node并放在l中
2、创建一个新的Node，将数据取到这个Node中，创建过程会将新Node的prev指向l，这样就接上了链
3、然后将last指向这个新Node
4、然判断l是否null，如果是null说明是空链表，新node就是第一个元素，这样first也要指向newNode
5、如果不为空则将l的next指向newNode
6、累加计数器
删除操作也是这种Node的前后Node指向移动操作。
再来看看Map
Map是键与值做一个映射表的应用，主要的实现类：HashMap,HashTable,TreeMap
HashMap和HashTable
使用hash算法进行键值映射的就是HashMap啦，HashTable是带有同步的线程安全的类，它们两主要的区别就是这个。原理也类似，都是通过桶+链来组合实现。桶是用来存Key的，而由于Hash碰撞的原因值需要用一个链表来存储。
•桶的意义在于高效，通过Hash计算可以一步定位
•链表的意义在于存取重复hash的数据
具体的原理以前写过一篇《学习笔记：Hashtable和HashMap》
只不过看JDK1.8的HashMap换了存储结构，采用红黑树的结构，这样可能是解决链表查找效率问题吧？具体没有细研究。
TreeMap
看过TreeMap的代码后发现还是使用的树结构，红黑树。由于红黑树是有序的，所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。
因为采用了树结构存储那么添加和删除数据时会麻烦一些，看一下put的代码：
publicVput(Kkey,Vvalue){
Entry<K,V>t=root;
if(t==null){
compare(key,key);//type(andpossiblynull)check
root=newEntry<>(key,value,null);
size=1;
modCount++;
returnnull;
}
intcmp;
Entry<K,V>parent;
//splitcomparatorandcomparablepaths
Comparator<?superK>cpr=comparator;
if(cpr!=null){
do{
parent=t;
cmp=cpr.compare(key,t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
else{
if(key==null)
thrownewNullPointerException();
@SuppressWarnings("unchecked")
Comparable<?superK>k=(Comparable<?superK>)key;
do{
parent=t;
cmp=k.compareTo(t.key);
if(cmp<0)
t=t.left;
elseif(cmp>0)
t=t.right;
else
returnt.setValue(value);
}while(t!=null);
}
Entry<K,V>e=newEntry<>(key,value,parent);
if(cmp<0)
parent.left=e;
else
parent.right=e;
fixAfterInsertion(e);
size++;
modCount++;
returnnull;
}
1、先是检查根节点是否存在，不存在说明是第一条数据，直接作为树的根
2、判断是否存在比较器，如果存在则使用比较器进行查找数据的存放位置，如果比较器返回结果小于0取左，大于0取右，否则直接替换当前节点的值
3、如果不存在比较器则key直接与节点的key比较，比较和前面方法一样
4、接下来就是在找到的parent上创建一个子节点，并放入左或者右子节点中
5、fixAfterInsertion是对节点进行着色
6、累加器处理
在remove操作时也会有点麻烦，除了删除数据外，还要重新平衡一下红黑树。
另外，TreeMap实现了NavigableMap<K,V>接口，所以也提供了对数据集合的一些返回操作。
最后看看Set
Set主要是两类应用：HashSet和TreeSet。
HashSet
字面意思很明确，使用了Hash的集合。这种集合的特点就是使用Hash算法存数据，所以数据不重复，存取都相对较快。怎么做到的呢？
publicbooleanadd(Ee){
returnmap.put(e,PRESENT)==null;
}
原来是存在一个map对象中，再看map是个啥？
privatetransientHashMap<E,Object>map;
是个HashMap，了解HashMap的就明白，这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的，所以在HashMap中只会存在一份。
了解了这点其他的东西就非常明白了。
TreeSet
这个集合是用于对集合进行排序的，也就是除了带有排重的能力外，还可以自带排序功能。只不过看了TreeSet的代码发现，其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。
publicTreeSet(){
this(newTreeMap<E,Object>());
}
所以，这里可能更关注的是TreeSet是如何排重呢？看一下add的方法吧：
publicbooleanadd(Ee){
returnm.put(e,PRESENT)==null;
}
和HashSet有点类似，都是基于Map的特性来实现排重。确实简单而且有效。
以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了，希望大家多多支持毛票票~