Java集合框架

集合框架

所有集合类都位于Java.util包下,Collection接口有两个主要的子接口List和Set,Map不是Collection的子接口,两者是平行的关系,同时Collection接口是继承了Java迭代接口Iterable。Collection使用多态接受子类时,父类不能使用子类特有的方法。

//JDK源码
public interface Collection<E> extends Iterable<E> {
// Query Operations

集合框架
集合框架

List接口

List集合是有序集合,集合中的元素可以重复,访问集合中的元素可以根据元素的索引来访问,通过查看源码可以看出来,List接口继承于Collection接口同时在原有Collection接口的基础上进行了一些扩充。 同时List接口又有两个常用的实现类ArrayList和LinkedList

public interface List<E> extends Collection<E> {

ArrayList

ArrayList是一个动态数组,底层是基于Object[]数组实现的,所以ArrayList的随机访问速度快。不适合于在线性表中间需要频繁进行插入和删除操作,因为每次插入和删除都需要移动数组中的元素。同时ArrayList的操作是线程不安全的,所以一般在单线程使用ArrayList,多线程一般使用Vector或者CopyOnWriteArrayList。

如果在初始化ArrayList时没有指定初始化长度,默认长度为10

此处所指长度10是指Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组的10个空元素,并非逻辑长度
在第一个元素被添加进一个空的ArrayList时,this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA才会被DEFAULT_CAPACITY = 10所填充,逻辑长度为1,剩余9个空元素。

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

JDK1.8中,ArrayList的初始容量为0,第一次添加元素时,会将容量设置为10,如果容量不够,则每次会扩大50%

int newCapacity = oldCapacity + (oldCapacity >> 1);

容量被扩充为原容量的1.5倍,oldCapacity>>1,右移一位,即:oldCapacity除以2

elementData = Arrays.copyOf(elementData, newCapacity);

用Arrays的copyOf方法拷贝原数组内容,并设置新的长度。

可以看到ArrayList扩容需要做一次数组拷贝,如果是反复扩容,肯定会对程序的运行效率产生影响。所以在初始化ArrayList的时候,尽量设置初始化容量,避免其扩容。

private void ensureCapacityInternal(int minCapacity) {
      if (elementData == EMPTY_ELEMENTDATA) {
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }

      ensureExplicitCapacity(minCapacity);
  }

  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;

      //超出了数组可容纳的长度,需要进行动态扩展
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
  }
  
  //这才是动态扩展的精髓,看到这个方法,ArrayList瞬间被打回原形
  private void grow(int minCapacity) {
      int oldCapacity = elementData.length;
      //设置新数组的容量扩展为原来数组的1.5倍
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      //再判断一下新数组的容量够不够,够了就直接使用这个长度创建新数组, 
      //不够就将数组长度设置为需要的长度
      if (newCapacity - minCapacity < 0)
          newCapacity = minCapacity;
      //判断有没超过最大限制
      if (newCapacity - MAX_ARRAY_SIZE > 0)
          newCapacity = hugeCapacity(minCapacity);
      //将原来数组的值copy新数组中去, ArrayList的引用指向新数组
      //这儿会新创建数组,如果数据量很大,重复的创建的数组,那么还是会影响效率,
      //因此鼓励在合适的时候通过构造方法指定默认的capaticy大小
      elementData = Arrays.copyOf(elementData, newCapacity);
  }
  
  private static int hugeCapacity(int minCapacity) {
      if (minCapacity < 0) // overflow
          throw new OutOfMemoryError();
      return (minCapacity > MAX_ARRAY_SIZE) ?
         Integer.MAX_VALUE :
         MAX_ARRAY_SIZE;
 }
}

ArrayList是线程不安全的,在多线程的情况下不要使用。

    //add方法源码
    public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

ArrayList线程不安全体现在两个方面
1).不是一个原子操作,是分两步执行的。

elementData[size++] = e;
//拆解为
elementData[size] = e;
size++;

单线程执行这段代码完全没问题,可是到多线程环境下可能就有问题了。可能一个线程会覆盖另一个线程的值。

列表为空 size = 0。
线程 A 执行完 elementData[size] = e;之后挂起。A 把 "a" 放在了下标为 0 的位置。此时 size = 0。
线程 B 执行 elementData[size] = e; 因为此时 size = 0,所以 B 把 "b" 放在了下标为 0 的位置,于是刚好把 A 的数据给覆盖掉了。
线程 B 将 size 的值增加为 1。
线程 A 将 size 的值增加为 2。

这样子,当线程 A 和线程 B 都执行完之后理想情况下应该是 "a" 在下标为 0 的位置,"b" 在标为 1 的位置。而实际情况确是下标为 0 的位置为 "b",下标为 1 的位置啥也没有。

2).ArrayList 默认数组大小为 10。假设现在已经添加进去 9 个元素了,size = 9。
线程 A 执行完 add 函数中的ensureCapacityInternal(size + 1)挂起了。
线程 B 开始执行,校验数组容量发现不需要扩容。于是把 "b" 放在了下标为 9 的位置,且 size 自增 1。此时 size = 10。
线程 A 接着执行,尝试把 "a" 放在下标为 10 的位置,因为 size = 10。但因为数组还没有扩容,最大的下标才为 9,所以会抛出数组越界异常 ArrayIndexOutOfBoundsException

ArrayList实现遍历的几种方法

foreach遍历Lonely

        
List<String> Lonely = new ArrayList<>();
    Lonely.add("Lonely");
    Lonely.add("Hello");
    Lonely.add("World");
    
    for(String s:Lonely){
//也可以使用for(int i = 0;i < Lonely.length();i++)
        System.out.println(s);
    }

链表转为数组进行遍历

String[] Lonelys = new String[Lonely.size()];
    Lonely.toArray(Lonelys);
    for(int i = 0;i < Lonelys.length;i++){
        System.out.println(Lonelys[i]);
    }    

//        for(String s:Lonelys){// 也可以用foreach来写
//            System.out.println(s);
//        }

迭代器进行遍历

Iterator<String> itr = Lonely.iterator();
    while(itr.hasNext()){
        System.out.println(itr.next());
    }

LinkedList

LinkedList的链式线性表适合在数据量大的时候进行频繁的插入删除操作,但是随机访问速度较慢,是从头一个一个元素进行查找
LinkedList是一个双向链表,LinkedList类每个结点用内部类Node表示,LinkedList通过first和last引用分别指向链表的第一个和最后一个元素,当链表为空时,first和last都为NULL值。

LinkedList和ArrayList的区别和联系

1.ArrayList是实现了基于动态数组的数据结构,LinkedList是基于链表结构
2.对于随机访问的get和set方法,ArrayList要优于LinkedList,因为LinkedList要移动指针。
3.对于新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList要移动数据。
4.对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配;而对LinkedList而言,这个开销是 统一的,分配一个内部Entry对象。
5.在ArrayList集合中添加或者删除一个元素时,当前的列表所所有的元素都会被移动。而LinkedList集合中添加或者删除一个元素的开销是固定的。
6.LinkedList集合不支持 高效的随机随机访问(RandomAccess),因为可能产生二次项的行为。
7.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

LinkedList的内部实现

1.数据存储是基于双向链表实现的。
2.插入数据很快。先是在双向链表中找到要插入节点的位置index,找到之后,再插入一个新节点。 双向链表查找index位置的节点时,有一个加速动作:若index < 双向链表长度的1/2,则从前向后查找; 否则,从后向前查找。
3.删除数据很快。先是在双向链表中找到要插入节点的位置index,找到之后,进行如下操作:node.previous.next = node.next;node.next.previous = node.previous;node = null 。查找节点过程和插入一样。
4.获取数据很慢,需要从Head节点进行查找。
5.遍历数据很慢,每次获取数据都需要从头开始。

LinkedList也是线程不安全的

LinkedList和ArrayList一样也是线程不安全的,解决方法有下边这几个:
1)Collections.synchronizedList(new LinkedList())
2)LinkedList和ArrayList换成线程安全的集合,如CopyOnWriteArrayList,ConcurrentLinkedQueue......
3)Vector(内部主要使用synchronized关键字实现同步)

LinkedList实现遍历的几种方法

for遍历Lonely(随机访问)

List<String> Lonely = new LinkedList<>();
    Lonely.add("Lonely");
    Lonely.add("Hello");
    Lonely.add("World");
    int size = Lonely.size();
    for (int i = 0; i < size; i++) {
        System.out.println(Lonely.get(i));
    }

foreach遍历Lonely

        for(String s:Lonely){
        System.out.println(s);
    }

迭代器遍历Lonely

Iterator<String> itr = Lonely.iterator();
    while(itr.hasNext()){
        System.out.println(itr.next());
    }

使用LinkedList实现堆栈

import java.util.LinkedList;
public class JdbcTest {
private LinkedList linkedList=new LinkedList();
 
//压栈
public void  push(Object value){//压
    linkedList.addFirst(value);
}

//出栈
public Object pop(){//弹
    Object value=linkedList.getFirst();
    linkedList.removeFirst();
    return value;
}

//容器大小
public int size(){
    return linkedList.size();
}
public static void main(String[] args) {

//堆栈:是一种先进后出的数据结构(容器),就像弹夹一样。
    JdbcTest Lonely=new JdbcTest();
    Lonely.push("12");
    Lonely.push("13");
    Lonely.push("14");
    Lonely.push("15");
 
    while(Lonely.size()!=0){
        System.out.println(Lonely.pop());
    }
  }
}

使用LinkedList实现队列

package com.test.www.test;

import java.util.LinkedList;
 
public class d1 {
private LinkedList<Object> link;

public d1(){
    link = new LinkedList();
}

public void myAdd(Object obj){
    link.addFirst(obj);
}
public Object myGet(){
    return link.removeLast();
}

public boolean isNull(){
    return link.isEmpty();
}
//队列:先进先出,当多个任务分配给打印机时,为了防止冲突,创建一个队列,把任务入队,按先入先出的原则处理任务。
//当多个用户要访问远程服务端的文件时,也用到队列,满足先来先服务的原则。
public static void main(String[] args)
{
    d1 d2 = new d1();
    d2.myAdd("Lonely01");
    d2.myAdd("Lonely02");
    d2.myAdd("Lonely03");
    d2.myAdd("Lonely04");
    while (!d2.isNull())
    {
        System.out.println(d2.myGet());
    }
}
}

Set接口

Set集合是无序集合,集合中的元素不可以重复,访问集合中的元素只能根据元素本身来访问(也是集合里元素不允许重复的原因),最多只能有一个null元素。虽然Set中元素没有顺序,但是元素在set中的位置是有由该元素的HashCode决定的,其具体位置其实是固定的。

public interface Set<E> extends Collection<E> {
// Query Operations
//从JDK源码来看,Set接口是直接继承了Collection接口的
/**
 * Returns the number of elements in this set (its cardinality).  If this
 * set contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
 * <tt>Integer.MAX_VALUE</tt>.

此外需要说明一点,在set接口中的不重复是由特殊要求的。
举一个例子:对象A和对象B,本来是不同的两个对象,正常情况下它们是能够放入到Set里面的,但是如果对象A和B的都重写了hashcode和equals方法,并且重写后的hashcode和equals方法是相同的话。那么A和B是不能同时放入到Set集合中去的,也就是Set集合中的去重和hashcode与equals方法直接相关。

HashSet

HashSet是set接口的实现类,也是我们最常用的set集合储存的是无序,唯一的对象由于是无序的所以每组数据都没有索引。很多list可用的方法他都没有凡是需要通过索引来进行操作的方法都没有,所以也不能使用普通for循环来进行遍历,只有加强型for和迭代器两种遍历方法。
从JDK源码来看,HashSet的底层是基于HashMap实现的,而HashMap中key是不允许重复的,和Set集合的特性相符。至于去重详细的实现细节这里就暂时不贴了,有时间详细的写一下

 private transient HashMap<E,Object> map;
/**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
    map = new HashMap<>();
}

HashSet实现遍历的几种方式

转换为数组遍历

    Set<String> Lonely = new HashSet<>();
    Lonely.add("Lonely");
    Lonely.add("Hello");
    Lonely.add("World");
    String[] str = new String[Lonely.size()];
    str = Lonely.toArray(str);
    for(String s:str){// 也可以使用普通for循环遍历
        System.out.println(s);
    }

直接使用foreach遍历

    for(String str:Lonely){
        System.out.println(str);
    }

使用迭代器遍历

    Iterator<String> ite = Lonely.iterator();
    while(ite.hasNext()){
        System.out.println(ite.next());
    }

Map接口

Map集合中保存Key-value对(键值对)形式的元素,访问时只能根据每项元素的key来访问其value。由于Map集合是实现了一堆K/V(键值对)的组合,Map中的成员方法由一个关键字(key)和一个值(value)构成。因为是K/V的对象集合,所以Map中不能有重复的key,因为一个key对应着一个值。Map存储元素使用put方法,Collection使用Put方法,Map目前有一个比较常用的实现类:HashMap。Map接口不继承于Collection接口,两者是平行关系。

集合框架简化图
集合框架简化图

HashMap

HashMap底层实现为 数组+链表+红黑树 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
散列法(Hashing)是一种将字符组成的字符串转换为固定长度(一般是更短长度)的数值或索引值的方法,称为散列法,也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快,这种方法一般用来在数据库中建立索引并进行搜索,同时还用在各种解密算法中。
数组:存储区间连续,占用内存严重,寻址容易,插入删除困难;
链表:存储区间离散,占用内存比较宽松,寻址困难,插入删除容易;
Hashmap综合应用了这两种数据结构,实现了寻址容易,插入删除也容易。
HashMap数据结构图

添加新评论

评论列表