Java 集合框架浅析
文章目录
这里只解析一些常用的、比较重要的一些集合类,并且作者水平有限,有些地方可能解析不到位或者解析错误,还望各位读者指出错误。
Collection
List
ArrayList
LinkedList
Vector
Stack
Queue
Deque
LinkedList
Set
SortedSet
HashSet
TreeSet
Map
HashMap
HashTable
TreeMap
WeakHashMap
Java集合的一个大体框架,针对常用的方法来对集合类进行解析(JDK1.8)
List
List就是一个接口,继承了接口Iterator,是为了获得迭代器(Iterator),用于遍历集合中的数据
定义了一些集合常用的方法add(0)、remove()等等
List--ArrayList
ArrayList底层数据结构是数组实现,非线程安全
成员变量:
transient Object[] elementData; //这就是ArrayList类中存放数据的数组
private int size; //记录的是当前在数组中可插入的索引值,表示的是当前数组的元素个数,并不表示当前数组的实际大小
常用方法解析:
1.construct
public ArrayList(); //没有指定大小的集合,elementData = {},在第一次执行add()方法的时候,就会设置数组的大小为10(DEFAULT_CAPACITY)
public ArrayList(Collection<? extends E> c); //参数一个集合,然后将参数复制到elementData上
public ArrayList(int initialCapacity); //参数集合大小,创建对象的时候就将数组的大小通过参数传进来,创建数组:elementData = new Object[initialCapacity];
2.add
public boolean add(E e);
//添加element之前,先调用ensureCapacityInternal(size+1),比较数组空间大小和当前的索引值,如果当前要插入的索引值大于数组的大小,就要执行grow(minCapacity)方法,
//就是加大数组空间grow(minCapacity)是这样实现的,将得到oldCapacity=elementData.length,然后newCapacity=oldCapacity+(oldCapacity>>1),也就是在原来数组空间的大小之上再
//加上原来的一半,具体还是得看代码
public void add(int index,E element);
//在指定的索引出插入值,首先要判断索引是否越界,条件是(index>size || index<0),符合任意条件,就抛出索引越界异常,因为这里是跟size比较,size是当前要插入到数组中的索引值,并非
//数组的实际大小,这么做是为了防止这个浪费空间,如果size=10,index=100(假如数组实际大小超过100),那这样就会导致index为10~99之间的空间浪费了
public boolean addAll(Collection<? extends E> c);
public void addAll(int index,Collection<? extends E> c);
//这两个方法与上面类似,不再赘述
3.remove
public E remove(inde index);
//index >= size,抛出数组索引越界异常
//否则:E oldValue=elementData[index],将该索引位置后面的元素(直到index=size-1)都往前移动,并且elementData[--size]=null,然后返回oldValue
public boolean remove(Object o);
//首先遍历elementData,判断o是否在elementData中,没有则返回false
//否则:记录当前的index,然后调用fastRemove()方法
private void fastRemove(int index);
//这个跟remove(index)方法有些类似,也是将当前索引位置后面的元素往前移动,并且elementData[--size]=null;
List--LinkedList
LinkedList,顾名思义,其实就是一个双向链表,这也表明了LinkedList可以存储无数个元素,只要空间允许(因为地址不连续,只要有空间,就可以用来开辟节点,然后连上链表),非线程安全,非线程安全
成员变量:
transient int size = 0; //当前链表中的元素个数
transient Node<E> first; //表头节点,Node是内部类,之后三个属性,E item(值),Node<E> next(下一个节点),Node<E> prev(前一个节点);
transient Node<E> last; //表尾节点
常用方法解析:
1.construct
public LinkedList(); //空实现
public LinkedList(Collection<? extends E> c); //执行上面的空方法,然后addAll(c),将c添加到链表中
2.add
public boolean add(E e);
//直接调用linkLast(e) 方法,然后返回true
//看一下linkLast(E e)方法,这个方法实现的就是在双向链表的表尾添加一个元素,这个具体可以去搜索一下双向链表
public void add(int index,E e);
//首先判断index是否越界,判断标准就是index>=0 && index<=size
//如果index=size,相当于在表尾添加节点,直接调用linkLast(e);
//否则:调用linkBefore(e,node(index))函数,node(index)函数的作用是为了获取到当前所在索引的节点,因为链表每个节点的地址不是连续的,所以无法使用索引,这里的index只是标识了在这个
//链表中的第几个
//再看一下linkBefore(e,nodex(index))函数,通过node(index)获取当前索引的节点,接下来要新增的节点就处在当前节点的前面,具体实现搜索双向链表插入节点
public boolean addAll(Collection<? extends E> c);
public void addAll(int index,Collection<? extends E> c);
//类似
public void linkFirst(E e);
//从表头添加节点
public void linkLast(E e);
//从表尾添加节点
3.remove
public E remove();
//调用removeFirst();
public E remove(int index);
//判断index的合法性
//定位到index所在的节点,然后删除该节点
public boolean remove(Object o);
//判断o是否在链表中,如在链表中,即可删除
public E removeFirst();
//删除链表的头节点
public E removeLast();
//删除链表的尾节点
List--Vector
Vector与ArrayList类似,底层数据结构也是数组,但是Vector是线程安全的
成员变量:
protected Object[] elementData; //存放数据的数组 //被protectd修饰的成员变量,子类可以使用,例如Stack
protected int elementCount; //数组中的实际元素个数
protected int capacityIncrement; //数组容量的每次增量大小
常用方法解析;
1.construct
public Vector(); --> 调用this(10);
public Vector(int initialCapacity); --> 调用this(initialCapacity,0),数组容量的增量没有指定的话,就为0,在每次给数组重新设置容量的时候,容量为原来的2倍
public Vector(int initialCapacity,int capacityIncrement); 每次给数组重设容量的时候,新容量=旧容量+增量
public Vector(Collection<? extends E> c); //将集合c中的数据复制到elementData
2.add
//与ArrayList除了线程安全,其余大同小异
public synchronized boolean add(E e);
public void add(int index,E element);
//调用了synchronized void insertElement(E obj,int index)
public synchronized void addElement(E obj);
3.remove
public synchronized void removeElementAt(inde index);
public synchronized boolean removeElement(Object obj);
public synchronized E remove(int index);
List--Vector--Stack
Stack继承自Vector,是一个栈,进栈元素添加在数组最后面,出栈将最后一个元素弹出,push()和pop()方法体内调用的都是父类Vector的方法,所以也是线程安全的
常用方法解析:
1.construct
public Stack(); //空方法实现
2.public E push(E item);
//实际上调用的是父类的addElement(E e)方法,并返回item
public synchronized E pop();
//调用peek()方法获取栈顶元素,然后调用父类的removeElement(int index)方法删除栈顶元素,并返回栈顶元素
public synchronized E peek();
//返回栈顶元素
Queue
Queue是一个接口,队列
Queue--Deque
Deque也是一个接口,继承了Queue接口,并定义相当多的方法
Queue--Deque--LinkedList
LinkedList实现了Deque接口,非线程安全,要创建一个队列,就让一个Queue引用指向LinkedList对象,队列的特点就是先进先出,跟排队买东西时一样的,
LinkedList在上面已经说过了,不再赘述
Set
Set是一个不包含重复元素的Collection接口,Set最多只能有一个null元素
Set--SortedSet
也是一个接口
Set--HashSet
底层数据结构居然是用HashMap实现的,也就造成了元素是无序的,也就无法通过索引来获取值,不包含重复数据,非线程安全
每次调用add(E e)方法的时候,都是直接把参数e当作数据容器map的key(从这可以看出来为什么HashSet不能包含重复值了),PRESENT当作value
并且要遍历HashSet只能通过获取迭代器来讲HashSet中的元素迭代出来
成员变量:
HashMap<E,Object> map; //存放数据的容器
private static final Object PRESENT = new Object(); //就是为了填充map的value的那个位置,没有其他任何作用
常用方法解析:
1.construct
public HashSet(){
map = new HashMap<>(); } //hashmap没有指定容量
public HashSet(int initialCapacity){
map = new HashMap<>(initialCapacity); } //指定初始化容量
public HashSet(int initialCapacity,float loadFactor){
map = new HashMap<>(initialCapacity,loadFactor); } //指定初始化容量,并
public HashSet(int initialCapacity,float loadFactor,boolean dummy){
map = new LinkedHashMap<>(initialCapacity,loadFactor); }
public HashSet(Collection<? extends E> c){
map = new HashMap<>(Math.max((int)(c.size()/.75f)+1,16)); }
2.add
public boolean add(E e){
return map.put(e,PRESENT) == null;
}
//很简单,就是把要插入的元素当作HashMap的key,而HashMap的key是不能重复的,所以HashSet是不能包含重复值的
3.remove
public boolean remove(Object o){
return map.remove(o) == PRESENT;
}
4.iterator
public Iterator<E> iterator(){
return map.keySet.iterator();
}
//通过迭代器遍历HashSet中的元素
Map
Map是一个Key-Value的数据存储结构,是一个接口,定义了大量的接口方法
Map--HashMap
HashMap是Map的实现类,可以看到HashMap的底层也是使用数组实现的,但不同的是,数组的每个元素又是一个链表的头节点,所以HashMap的底层数据结构是数组+单向链表(如果链表的节点数量过多,则使用红黑树)来实现的,非线程安全
成员变量:
transient int size; //当前数组中的元素个数 (transient关键字)
transient Node<K,V>[] table; //存放数据的容器,是一个散列表(数组+单向链表),数组中的每个元素都是一个链表的头节点,
transient Set<Map.Entry<K,V>> entrySet; //
final float loadFactor; //负载因子,定义为:散列表的实际数目/散列表的容量,如果size > loadFactor*capacity,那就需要扩容了,默认是0.75,
//负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(n),
//因此,如果负载因子越大,对空间的利用率很高,然后后果就是查找效率的降低,集中表现就是对链表的迭代遍历会变慢;如果负载因子太小,那么散列表的数据过于稀疏,对空间造成
//严重浪费
transient int modCount; //修改次数,由于HashMap是非线程安全的,所以如果在使用迭代器的过程中,如果有其他线程修改了map,那么将抛出ConcurrentModificationException,
//这就是所谓的fail-fast策略,这一实现就是在内部类迭代器中添加成员变量expectedModCount来记录当前的modCount,然后再迭代的过程中判断modCount和expectedModCount
//是否相等,不相等就表明有其他线程修改了该map
常用方法解析
1.construct
public HashMap(); //构建一个初始容量为16,负载因子为0.75的HashMap
public HashMap(int initialCapacity); //构建一个初始容量为initialCapacity,负载因子为0.75的HashMap
public HashMap(int innitialCapacity,floadloadFactor); //指定初始容量和负载因子创建一个HashMap
2.put
public V put(K key,V value){
return putVal(hash(key),key,value,false,true); //调用putVal方法
}
public V putVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict);
//1.若table是否为空或者长度为0,则调用resize()方法,则给数组(table)重设大小
//2.否则获取table的长度n,并(n-1)&hash获得该元素在table中的索引,并获取当前索引位置的元素p,若该元素为空,则直接将新元素放在table上
并且如果(++size > threshold) = true,那么调用resize()方法,重置数组大小,并返回null(因为该索引处没有节点,所以为null),方法结束
//3.否则的话,若(p.hash == hash && ((k=p.key)==key || (key!=null && key.equals(k)))),这个判断语句是在判断原索引上的key和要插入的key是否是同一个key,
如果是的话,则赋值为临时变量e
//4.否则说明要遍历以p为链表头节点的链表,遍历过程中每个节点的key都要判断和新增的key是否一样,若一样,赋值给临时变量e
//5.否则,将当前的key和value构造成一个Node<K,V>对象,然后从这个链表的头节点前插入
//6.注意还没结束,e!=null为true(e相当于是旧值),则返回e.value
//7.否则 如果(++size > threshold) = true,那么调用resize()方法,重置数组大小,并返回null(因为该索引处没有节点,所以为null),方法结束
//注意:1)这里获取key所在table中的索引值算法,请看这个:http://pengranxiang.iteye.com/blog/543893
2)如果链表过长,会将链表转换成红黑树
3.final Node<K,V>[] resize();
//1.若oldCap(原来数组的大小)大于MAXIMUM_CAPACITY,也就是超过最大值,那就没办法了,随你去碰撞了
//2.否则:newCap = oldCap<<1,扩大2倍
4.remove
public V remove(Object key){
Node<K,V> e;
reutrn (e = removeNode(hash(key),key,null,false,true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash,Object key,Object value,boolean matchValue,movable);
//1.若table==null || table.length<=0,则直接返回null,方法结束
//2.否则:通过((n=table.length-1) & hash)获取到该key所在数组中的索引,并将该索引处的元素赋值给p,
若(p.hash=hash && ((k=p.key)==key || (key !=null && key.equals(k)))) = true,说明该索引所在的位置正在是要删除的节点,然后将该节点赋值给临时变量node
//3.否则:遍历以p为头节点的链表,找到对应的节点,然后赋值给临时变量node,将node的前一个节点赋值给p
//注意:node是要删除的节点,p是node的前一个节点(如果node是链表的头节点,那么p=null),链表的具体操作可以看这个方法
Map--HashTable
HashTable也是Map的实现类,跟HashMap差不多,线程安全的
HashMap和HashTable的区别
1.HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
2.HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了
ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
3.另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出
ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和
Iterator的区别。
4.由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
5.HashMap不能保证随着时间的推移Map中的元素次序是不变的。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论