引入

     使用数组储存值时，储存数据方便，但是操作数据不方便。

常用集合框架类

ArrayList **** LinkedList ** HashSet *** HashMap *****

 

集合框架结构

集合框架图

          如下所示：

      集合框架都包含如下内容：

接口是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。实现类是集合接口的具体实现。例如：ArrayList、LinkedList、HashSet、HashMap。算法是实现集合接口的对象里的方法执行的一些有用的计算。如Collections、Arrays。

常用类

Collection接口

List接口

    ArrayList

    LinkedList

Set接口

    HashSet

List接口List 接口存储一组可重复，有序（插入顺序）的对象。Set接口Set 接口存储一组唯一，无序的对象。SortedSet 继承于Set保存有序的集合。MapMap 接口存储一组键值对象，提供key（键）到value（值）的映射。SortedMap继承于 Map，使 Key 保持在升序排列。Collections集合框架的工具类Arrays 

 

Collection

概述

        Collection是最基本的集合接口， 里面储存一组不唯一，无序的对象。一个Collection代表一组Object，即Collection的元素。

子接口

        Collection有三个子接口：

List接口

         List接口储存一组可重复，有序（按照元素插入顺序）的对象。使用此接口能够精确控制每个元素插入的位置以及访问元素。集合中第一个元素下标从0开始。List和数组类似，可以动态增长，根据实际储存的元素的长度自动增长List的长度。

         List的实现类有：ArrayList、LinkedList、Vector。List扩展了Collection，重载了很多方法。

Set接口

         Set接口储存一组不重复，无序的对象。检索效率低下，删除和插入效率高。删除和插入不会引起元素位置的改变。

         Set实现类有：HashSet、TreeSet。

Queue接口

       队列分类：

单端队列（Queue）单端队列可以看做特殊的线性表，其访问特征就是先进先出，后进后出原则，即只能从线性表一端添加（offer）元素，从另一端取出（poll）元素。双端队列（Deque)

双端队列Deque是一个接口，继承自Queue。其特征为队列两端都可以入队和出队。

注意：如果将Deque限制为只能从一端出队和入队（后进先出），则可以实现栈一样的效果。

       LinkedList实现了Deque接口（用于队列经常要进行插入、删除等操作，而LinkedList在这方面效率高）。

常用方法

boolean add(E e)

           向当前集合中添加一个元素。集合中保存的是元素的地址引用，若外部引用对元素进行修改，则集合中元素也会跟着被修改。

boolean addAll(Collection<? extends E> c)

           将指定集合中所有的元素，添加到当前集合中。true表示添加成功；false表示添加失败。

boolean contains(Object o)

           判断当前集合中是否包含给的的元素，返回true则包含；false则不包含。注意：是否包含取决于集合中是否存在元素与给定元素调用equals方法比较是否为true。

boolean containsAll(Collection s)

           判断当前集合中是否包含给的集合中的所有元素。返回true则包含；false则不包含。是否包含取决于集合中是否存在元素与给定集合中所有元素调用equals方法比较是否为true。

int size()

          返回当前集合中元素的个数。

boolean isEmpty()

           判断当前集合是否为空集合（空集合指集合中不存在元素）。true代表空集合；false代表不是空集合。

void clear()

          清空当前集合中的所有元素。

boolean remove(Object o)

         删除当前集合中的指定的元素（若存在多个相同的元素，则删除第一次equals为true的元素）。返回true表示删除成功；返回false表示删除失败。

         注意：是否删除成功取决于集合中是否存在元素与给定元素调用equals方法比较是否为true。

boolean removeAll(Collection<?> c)

        从当前集合中删除指定集合中所有元素。

        注意：是否删除成功取决于集合中是否存在元素与给定集合中所有元素调用equals方法比较是否为true。

Iterator<E> iterator()

        所有Collection的实现类都实现了iterator()方法，该方法返回遍历当前集合的Iterator迭代器

Iterator itr = collection.iterator(); while(itr.hasNext()){ 元素值 = itr.next(); }

        建议使用字符串字面量使用.equals方法进行比较，以防止出现NullPointerException异常。

        迭代器里面保存的是集合中的元素，操作迭代器元素就是操作集合里面的元素，如下所示：

public class Test3 { public static void main(String[] args) { ArrayList<String> list = new ArrayList<>(); list.add("1"); Iterator iterator = list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next() == list.get(0)); } } } 结果为：true

        注意：通过迭代器遍历集合时，若想要删除元素时，不能通过原集合的方法删除，只能使用迭代器的方法删除。

Iterator itr = collection.iterator(); while(itr.hasNext()){ 元素值 = itr.next(); itr.remove(); //itr.remove(); //错误，只能删一次 }

 

增强for循环

     增强for循环是JDK1.5推出的，也叫forEach循环。用于遍历集合和数组。

      其底层也是通过迭代器遍历，但使用增强for循环获取不了迭代器，因此不能使用迭代器进行删除，所以增强for循环只用于遍历集合或数组。

ArrayList

底层实现原理

      ArrayList实现List接口，底层由数组实现的，可以以O(1)时间复杂度对元素进行随机访问，故查询性能高，添加、删除性能低。

     部分源码如下：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ private static final long serialVersionUID = 8683452581122892189L; private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; transient Object[] elementData; // non-private to simplify nested class access private int size; public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } ...... }

构造方法

public ArrayList()

 

public ArrayList(int initialCapacity)

 

public ArrayList(Collection<? extends E> c)

 

常用方法

添加

public boolean add(E e)

向列表中添加指定元素 获取

public E get(int index)

获取并返回指定下标的元素 修改

public E set(int index, E element)

将指定下标的元素修改位指定元素 删除

public E remove(int index)

删除指定下标的元素

public boolean remove(Object o) 

从列表中删除指定的元素 取子集

public List<E> subList(int fromIndex, int toIndex)

从列表中截取指定开始下标到结束下标的子集

注意：

1.Java区间范围是包含头不包含尾，故子集包含fromIndex下标元素，不包含toIndex下标元素

2.子集和原集合指向同一个对象引用，故对子集操作，原集合也会跟随变化

列表转数组

 public Object[] toArray()

返回一个Object类型的数组

 public <T> T[] toArray(T[] a) 

返回一个T类型的数组。 数组转列表

Arrays.asList(T... a)（public static <T> List<T> asList(T... a) ）

通过数组转换得到的List集合为只读集合，即不能对其修改。

 

Set

Set源码及结构

      Set接口源码如下所示：

public interface Set<E> extends Collection<E> { int size(); boolean isEmpty(); boolean contains(Object o); Iterator<E> iterator(); Object[] toArray(); boolean add(E e); boolean remove(Object o); boolean containsAll(Collection<?> c); boolean addAll(Collection<? extends E> c); boolean retainAll(Collection<?> c); boolean removeAll(Collection<?> c); void clear(); boolean equals(Object o); int hashCode(); @Override default Spliterator<E> spliterator() { return Spliterators.spliterator(this, Spliterator.DISTINCT); } }

 

HashSet

底层实现原理

     HashSet底层由HashMap实现的，故储存的数据也是无序且不重复的。但只使用了HashMap的key部分，其value为默认值。如下所示：

public boolean add(E e) { return map.put(e, PRESENT)==null; } public boolean remove(Object o) { return map.remove(o)==PRESENT; }

HashSet源码及结构

      HashSet接口源码如下所示：

public class HashSet<E>extends AbstractSet<E> implements Set<E>, Cloneable,java.io.Serializable{ static final long serialVersionUID = -5024744406713321676L; private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); /** * 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接口源码结构如下所示：

 

 

Quque

单端队列Queue

       Queue接口源码如下所示：

public interface Queue<E> extends Collection<E> { boolean add(E e); boolean offer(E e); E remove(); E poll(); E element(); E peek(); }

       可以看出，Queue接口继承自Collection，其结构如下所示：

      其常用方法如下所示：

元素入队列 boolean offer(T e)将给定元素添加到队尾中，返回true表示入队成功；返回false入队失败。 元素出队列

E poll()

将队列的队首元素从队列中移除并返回。 查看队首元素 E peek()返回队首元素。不会将队首元素从队列中移除。

双端队列Deque（可以实现栈的效果）

     Deque接口源码如下所示：

public interface Deque<E> extends Queue<E> { ...... }

     可以看出，Deque接口继承自Queue，其结构如下所示：

     其常用方法如下所示：

元素进栈 void push(T e)将给定元素添加到栈顶 元素出栈 E pop()将栈顶元素从栈中移除并返回 查看栈顶元素 E peek()返回栈顶元素。不会将栈顶元素从队列中移除。 查看栈内元素的个数 public int size()返回栈内元素的个数。

 

LinkedList

底层实现原理

       LinkedList是List和Deque接口的一种实现，其底层由链表实现的，查找某个元素的时间复杂度是O(n)。 故查询效率低，添加、删除效率高。

      部分源码如下：

public class LinkedList<E>extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first; transient Node<E> last; public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); } private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } 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++; } ...... }

 

Map

概念

     Map是一个接口，存储一组键值对对象，提供key（键）到value（值）的映射。

     Map储存着无序

源码及结构

      Map接口源码如下所示：

public interface Map<K,V> { ...... }

      Map接口源码结构如下所示：

注意事项

         key不能重复，value可以重复

常用方法

添加key-value V put(K key, V value)

将给定的key-value键值对添加到Map集合中。

注意：若存在key相同，则新的value值会替换并返回原有旧的value值；

            若不存在key，则将该key-value键值对添加进去，并且返回null。

查询key-value V get(Object key)

返回指定key对应的value值

注意：若存在key，则返对应的value值

            若不存在key，则返回null。

删除key-value V remove(Object key)

删除指定的key-value并返回对应的value值

注意：若存在key，则删除该key-value并返对应的value值

            若不存在key，则返回null。

获取key-value个数 int size()

返回Map集合中键值对的个数

清空Map集合 void clear()

移除Map集合中所有的键值对

Map集合的遍历

       主要有三种方式，如下所示：

public class Test4 { public static void main(String[] args) { Map<String, Integer> map = new HashMap<String, Integer>(); map.put("张三", 20); map.put("无小忌", 19); map.put("张飞", 23); map.put("张翠山", 41); map.put("赵敏儿", 18); //1.遍历所有entry键值对 Set<Entry<String, Integer>> entries = map.entrySet(); for (Entry<String, Integer> entry : entries) { String key = entry.getKey(); Integer value = entry.getValue(); System.out.println("key:" + key + " value:"+value); } //2.遍历所有的key值得到value值 Set<String> kSet = map.keySet(); for (String key : kSet) { Integer value = map.get(key); System.out.println("key:" + key + " value:"+value); } //3.遍历所有的value值 Collection<Integer> values = map.values(); for (Integer integer : values) { System.out.print(integer + " "); } } }

HashMap

概念

       HashMap实现Map接口，存储一组键值对对象。基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

       HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。 每当往hashmap里面存放key-value对的时候，都会为它们实例化一个Entry对象，这个Entry对象就会存储在前面提到的Entry数组table中。Entry具体存在table的那个位置是 根据key的hashcode()方法计算出来的hash值（来决定）。

源码及结构

       HashMap接口源码如下所示：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { private static final long serialVersionUID = 362498820763181265L; ...... }

       HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

底层原理

       HasMap综合了ArrayList和LinkedList，底层由数组和链表组成。有如下特点：

1.添加key-value时，若HashMap中存在该key，则新的value会将旧的value值替换。因此，key值要尽可能保证唯一。2.HashMap储存的数据是无序的。因为HashMap在储存key-value时，会通过key%数组长度设置其位置。3.查询指定key对应的value值时，若给定的key值在Map集合中不存在，则返回null。

       HashMap的储存结构如下所示：

重写equals方法

       对于重写equals方法的对象，一般都要重写继承自Object类的hashCode方法（Object类的hashCode方法是返回该对象所在内存地址的整数形式）

重写hashCode方法

       重写hashCode方法需要注意两点：

1.与equals方法的一致性，即equals返回true的两个对象其hashCode返回值应该相同。2.hashCode返回数值要复合hash算法的要求。若很多对象的hashCode返回值都相同，则会大大降低hash表的效率，通常可以使用eclipse提供的工具自动生成hashCode方法。

HashTable

概念

       Hashtable也是JDK1.0引入的类，同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

源码及结构

       HashTable接口源码如下所示：

public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, Cloneable, java.io.Serializable { /** * The hash table data. */ private transient Entry<?,?>[] table; /** * The total number of entries in the hash table. */ private transient int count; ...... }

      Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

底层原理线程安全问题

      HashTable是线程安全的，能用于多线程环境中。

HashMap与HashTabl的区别

1.HashMap和HashTable都实现了Map接口2.HashTable允许键和值为null，而HashMap不允许键和值为null3.HashTable是同步的，而HashMap不是。即Hashtable 是线程安全的，而 HashMap 是非线程安全的。

 

Collections集合工具类

     Collections 位于java.util包中，是集合框架的工具类。

排序API

void java.util.Collections.sort(List<T> list)

           对List集合中元素进行排序，元素类型必须要实现Comparable接口，并重写其compareTo(T t)方法。

public int compareTo(Person o)

返回值小于0：前一个数小于后一个数

返回值等于0：两个数相同

返回值大于0：前一个数大于后一个数

注意：基本数据的包装类型都已经实现了Comparable接口和重写了compareTo(T t)方法。同时默认从小到大排序。

void java.util.Collections.sort(List<T> list, Comparator<? super T> c)

        传入一个比较器对对List集合中元素进行排序，比较规则使用比较器的规则。

Comparator位于java.util包中，是一个接口，使用此方法时要定义一个类实现Comparator接口，并重写其

int compare(T o1, T o2)方法（也可以考虑使用匿名内部类方式）。

返回值小于0：前一个数小于后一个数

返回值等于0：两个数相同

返回值大于0：前一个数大于后一个数

     比如比较String，根据字符串的长度从小到大排序：

class StrComparator implements Comparator<String>{ @Override public int compare(String o1, String o2) { return o1.length() - o2.length(); } } public class Test1 { public static void main(String[] args) { List<String> strList = new ArrayList<String>(); strList.add("小明"); strList.add("小"); strList.add("上官欧阳"); Collections.sort(strList, new StrComparator()); System.out.println(strList); } } 运行结果：[小, 小明, 上官欧阳]

     使用匿名内部类方式：

public class Test1 { public static void main(String[] args) { List<String> strList = new ArrayList<String>(); strList.add("小明"); strList.add("小"); strList.add("上官欧阳"); //匿名内部类方式 Collections.sort(strList, new Comparator<String>() { @Override public int compare(String o1, String o2) { return o1.length() - o2.length(); } }); System.out.println(strList); } }

         

 

参考：

https://www.runoob.com