单列集合框架体系Collection

2019-08-09 00:00:00 集合框架单列

单列集合框架体系

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}

相关文章