单列集合框架体系Collection

2019-08-16 09:42:59来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

单列集合框架体系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}

 


原文链接:https://www.cnblogs.com/mishaka/p/11129574.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:mybatis中多条件模糊查询不显示数据的问题

下一篇:企业微信机器人