单列集合框架体系Collection

单列集合框架体系

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

list接口主要特征：

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

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;
    }

 

 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++;
    }

 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是把当前数据存进数据对应数组连接的链表的末端。保证元素的不可重复性。

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

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

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);
        }
    }
}

 

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}