欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单列集合框架体系Collection

程序员文章站 2022-05-03 22:16:56
单列集合框架体系 List 集合体系 主要实现类 依次为 ArrayList,LinkedList,Vector 。 List接口主要特征: 有序,可重复,有索引,底层容量是动态扩容的。(代码以JDK 1.8为例) ArrayList:是List接口的主要实现类,底层用数组实现: ,transien ......

单列集合框架体系

list 集合体系 主要实现类 依次为 arraylist,linkedlist,vector 。

list接口主要特征:

  有序,可重复,有索引,底层容量是动态扩容的。(代码以jdk 1.8为例)

单列集合框架体系Collection

arraylist:是list接口的主要实现类,底层用数组实现: ,transient object[] elementdata; 

     线程不安全的,查询快,增加,删除 慢(相对于linkedlist)

     jdk1.7默认初始长度是10,jdk1.8默认长度是0 ,在调用添加方法之后,才进行长度初始化(值是 10)。

     扩容是在当前的数据容量比集合内部数组长度大时,进行扩容,扩容时会先复制原有的数组,然后创建新数组,把原有数组放入新数组中,新数组长度扩围原有的1.5倍,如果

     发现数组长度还是不够用,那么直接把当前的实际容量赋值给新数组的容量
private static final int max_array_size = integer.max_value - 8;
private static final object[] defaultcapacity_empty_elementdata = {};
public arraylist() {
        this.elementdata = defaultcapacity_empty_elementdata;
    }
public boolean add(e e) {
  
    ensurecapacityinternal(size + 1);  // increments modcount!!
    elementdata[size++] = e;
    return true;
}
private void ensurecapacityinternal(int mincapacity) {
    ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
private void ensureexplicitcapacity(int mincapacity) {
        modcount++;
       //如果初始值为10 ,现在集合长度为10 ,在添加低11个元素的时候        
         //会符合下面的判断条件,进入扩容机制
        // overflow-conscious code
        if (mincapacity - elementdata.length > 0)
            grow(mincapacity);
    }
private void grow(int mincapacity) {
    // overflow-conscious code
    int oldcapacity = elementdata.length;
   // 先扩大1.5倍,作为新数组的使用长度,通过下面判断是否够用
    int newcapacity = oldcapacity + (oldcapacity >> 1);
    if (newcapacity - mincapacity < 0)
        //扩容1.5倍的新数组长度还是不够用,那么直接把当前的实际容量赋值给新数组的容量
        newcapacity = mincapacity;
    if (newcapacity - max_array_size > 0)
        newcapacity = hugecapacity(mincapacity);
    // mincapacity is usually close to size, so this is a win:
  //调用java.util.arrays 工具包下面的复制数组方法

    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;
    }
public static <t,u> t[] copyof(u[] original, int newlength, class<? extends t[]> newtype) {
        @suppresswarnings("unchecked")
        t[] copy = ((object)newtype == (object)object[].class)
            ? (t[]) new object[newlength]
            : (t[]) array.newinstance(newtype.getcomponenttype(), newlength);
        system.arraycopy(original, 0, copy, 0,
                         math.min(original.length, newlength));
        return copy;
    }

 

单列集合框架体系Collection

 linkedlist:底层是双向链表实现的,有前后元素的地址存储。

transient node<e> first;
transient node<e> last;
private static class node<e> {
        e item;
        node<e> next;
        node<e> prev;

        node(node<e> prev, e element, node<e> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
public boolean add(e e) {
        linklast(e);
        return true;
    }
void linklast(e e) {
        final node<e> l = last;
        final node<e> newnode = new node<>(l, e, null);
        last = newnode;
        if (l == null)
            first = newnode;
        else
            l.next = newnode;
        size++;
        modcount++;
    }

单列集合框架体系Collection

 vector:线程安全的,底层用 object[] elementdata  数组,扩容是原来的2倍长度 这个和arraylist 是不一样的

protected object[] elementdata;
public vector(int initialcapacity) {
        this(initialcapacity, 0);
    }
public synchronized void addelement(e obj) {
        modcount++;
        ensurecapacityhelper(elementcount + 1);
        elementdata[elementcount++] = obj;
    }
private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
     //扩容是原来的2倍长度
        int newcapacity = oldcapacity + ((capacityincrement > 0) ?
                                         capacityincrement : oldcapacity);
        if (newcapacity - mincapacity < 0)
            newcapacity = mincapacity;
        if (newcapacity - max_array_size > 0)
            newcapacity = hugecapacity(mincapacity);
        elementdata = arrays.copyof(elementdata, newcapacity);
    }

 

set集合体系 主要实现类依次为 hashset,linkedhashset,treeset;

  set集合的特点:

    无序不可重复,这个不是指存取的顺序,指的是数据存放在内存中的地址的无序性,简单点说就是没有索引排序,是用hash值来进行判断。

    其中hashset 是set 的主要实现类,如果没有特殊情况的话,一般都使用这个类。

    无序性:不是指随机性,底层是数组+链表(jdk1.8 会把链表转红黑树) 通过hashcode() 计算出对应的hash 值,然后通过hash 值计算出数据存储在数组 对应的 地址上。

    不可重复性:先计算要存储值 的hash 值,通过hash 值来计算在容器中数组存放的位置,如果当前数据的hash 值所在容器的位置没有数据就直接存进去,

          如果有,那么就和容器中的值进行hash 值的比较,如果hash值相同,再计算当前值equals() 容器中该位置的值是否相等,如果相等就代表是同一个元素,就不存进容器中,

          如果hash值不同,则直接存进容器中,jdk1.7 是把当前元素存进数组和链表的连接处(链表前端),jdk1.8是把当前数据存进数据对应数组连接的链表的末端。保证元素的不可重复性。

单列集合框架体系Collection

hashset:可以存储null 值,线程不安全的(简单理解 :就是多线程情况下会不会产生数据不一致的问题,其实安不安全,基本就看是否是 加了锁,或者是底层是不是用cas 机制等来进行处理过),

      jdk1.7底层是 用数组+链表(单向链表)初始长度是 16 

单列集合框架体系Collection

linkedhashset:是hashset 的 子类 通过创建linkedhashset 的构造方法,实际是调用的hashset的私有方法来进行初始化操作,其中的初始化其实直接对应的是linkedhashmap这个类。

        简单点说,实际上就是用linkedhashmap 来进行实现的。底层是双向链表

linkedhashset:源代码截取

public class linkedhashset<e>
    extends hashset<e>
    implements set<e>, cloneable, java.io.serializable {
      public linkedhashset(int initialcapacity, float loadfactor) {
          super(initialcapacity, loadfactor, true);
      }
      public linkedhashset(int initialcapacity) {
           super(initialcapacity, .75f, true);
      }
      public linkedhashset() {
            super(16, .75f, true);
      }
}

hashset 源代码截取:

public class hashset<e>
    extends abstractset<e>
    implements set<e>, cloneable, java.io.serializable
{
    private transient hashmap<e,object> map;    
    hashset(int initialcapacity, float loadfactor, boolean dummy) {
        map = new linkedhashmap<>(initialcapacity, loadfactor);
    }
}

linkedhashmap 源代码截取:

public class linkedhashmap<k,v>
    extends hashmap<k,v>
    implements map<k,v>
{
    static class entry<k,v> extends hashmap.node<k,v> {
        entry<k,v> before, after;
        entry(int hash, k key, v value, node<k,v> next) {
            super(hash, key, value, next);
        }
    }
}

 

单列集合框架体系Collection

treeset:底层使用treemap实现,是一个可以排序的set集合。可以定制排序和比较排序,即实现指定泛型类中实体属性自然排序,也可以通过构造函数来进行指定外部的比较器来进行比较排序。

    需要注意的是,向treeset中添加的数据要是想同类型的。否则会报错。

public class collectiontest {
    public static void main(string[] args) {
        treeset treeset = new treeset();
        treeset.add("123");
        treeset.add(123);

    }
}
//报错信息如下
exception in thread "main" java.lang.classcastexception: java.lang.string cannot be cast to java.lang.integer
    at java.lang.integer.compareto(integer.java:52)
    at java.util.treemap.put(treemap.java:568)
    at java.util.treeset.add(treeset.java:255)
    at collectiontest.main(collectiontest.java:10)

  如果不实现自然排序接口(comparable),直接把值放进treeset 中还是会报错:

public class collectiontest {
    public static void main(string[] args) {
        treeset<user> treeset = new treeset();
        treeset.add(new user("misaka",23));
        treeset.add(new user("mikoto",24));
    }
}

exception in thread "main" java.lang.classcastexception: user cannot be cast to java.lang.comparable
    at java.util.treemap.compare(treemap.java:1294)
    at java.util.treemap.put(treemap.java:538)
    at java.util.treeset.add(treeset.java:255)
    at collectiontest.main(collectiontest.java:9)

 实现comparable代码示例:

public class collectiontest {
    public static void main(string[] args) {
        treeset<user> treeset = new treeset();
        treeset.add(new user("mikoto",24));
        treeset.add(new user("misaka",23));
        iterator<user> iterator = treeset.iterator();
        while (iterator.hasnext()){
            user user = iterator.next();
            system.out.println(user);
        }
    }
}

//省略 get,set,tostring,构造等模板代码
public class user implements comparable{
    public int compareto(object o) {
        if (o instanceof user){
            user user = (user)o;
            integer age = user.getage();
            return  this.age.compareto(age);
        }else {
            throw  new  runtimeexception("类型比较错误");
        }
    }
}

测试结果:
user{name='misaka', age=23}
user{name='mikoto', age=24}

 实现comparator 外部比较器代码示例:

public class collectiontest {
    public static void main(string[] args) {
        comparator<user> comparator = new comparator<user>() {
            public int compare(user o1, user o2) {
                return integer.compare(o1.getage(),o2.getage());
            }
        };

        treeset<user> treeset = new treeset(comparator);
        treeset.add(new user("mikoto",24));
        treeset.add(new user("misaka",23));
        treeset.add(new user("misaka",3));
        treeset.add(new user("misaka",5));
        treeset.add(new user("misaka",6));
        treeset.add(new user("misaka",1));
        iterator<user> iterator = treeset.iterator();
        while (iterator.hasnext()){
            user user = iterator.next();
            system.out.println(user);
        }
    }
}

输出结果:
user{name='misaka', age=1}
user{name='misaka', age=3}
user{name='misaka', age=5}
user{name='misaka', age=6}
user{name='misaka', age=23}
user{name='mikoto', age=24}