java 集合框架以及实现原理

iterator中的三个方法：

• hasNext() 如果仍有元素可以迭代，则返回true。

• next() 返回迭代的下一个元素。

• remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素（可选操作）。

  public static void main(String[] args) {
      List list1 = new ArrayList<>();
      list1.add("abc0");
      list1.add("abc1");
      list1.add("abc2");
  ​
      // while循环方式遍历
      Iterator it1 = list1.iterator();
      while (it1.hasNext()) {
          System.out.println(it1.next());
      }
  ​
      // for循环方式遍历
      for (Iterator it2 = list1.iterator(); it2.hasNext(); ) {
          System.out.println(it2.next());
      }
  ​
  }

a) ListIterator接口

    ListIterator是一个功能更加强大的迭代器， 它继承于Iterator接口，只能用于各种List类型的访问。可以通过调用listIterator()方法产生一个指向List开始处的ListIterator， 还可以调用listIterator(n)方法创建一个一开始就指向列表索引为n的元素处的ListIterator。
    特点:
    允许我们向前、向后两个方向遍历 List；
    在遍历时修改 List 的元素；
    遍历时获取迭代器当前游标所在位置。
常用的API:
    add(E e) 将指定的元素插入到列表 （可选操作）。
    hasNext() 如果此列表迭代器在前进方向还有更多的元素时，返回 true。
    hasPrevious() 如果此列表迭代器在相反方向还有更多的元素时，返回 true。
    next() 返回列表中的下一个元素和光标的位置向后推进。
    nextIndex() 返回调用 next()后返回的元素索引。remove() 删除列表中调用next()或previous()的返回最后一个元素。
    set(E e) 用指定元素替换列表中调用next()或previous()的返回最后一个元素。

b) Collection接口（单列集合）

• List：有序(元素存入集合的顺序和取出的顺序一致)，元素都有索引。元素可以重复。

• Set：无序(存入和取出顺序有可能不一致)，不可以存储重复元素。必须保证元素唯一性。

List集合

ArrayList

linkedList

Vector

Set集合

HashSet：

如何判断集合中的元素唯一:当加入对象时，首先根据HashCode值来判断，看是否有重复的，如果发现有重复的，在调用equals方法判断对象的中是否相等，如果两次判断都为true，则不会加入；

TreeSet：

linkedHashSet：

总结：
HashSet是一个通用功能的Set，而linkedHashSet 提供元素插入顺序保证，TreeSet是一个SortedSet实现，由Comparator 或者 Comparable指定的元素顺序存储元素。

c) Map接口（多列集合）

    Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。
    Map 的常用实现类：HashMap、TreeMap、HashTable、linkedHashMap、ConcurrentHashMap

 HashMap ，TreeMap，HashTable的区别：

扩容机制：（底层为数组实现的才需要扩容）

**ArrayList集合扩容：使用无参构造产生的数组的默认初始大小为10，（ oldCapacity + (oldCapacity >> 1)）每次在原数组的基础上增加原数组的1/2; 相当于位运算中的右移1位。

**HashSet集合扩容(底层为hashMap实现)： 默认初始大小为16，加载因子为0.75（当集合中元素数量超过原数组的0.75时，进行扩容），每次扩容的增量为原数组的一倍，16-->32;

**Vector集合扩容：当集合元素数量超过集合容量长度时，进行扩容，每次扩容为原数组的一倍，即加载因子为1 如：10-->20;

**HashMap扩容：默认容量为16，当元素的个数超过总容量的0.75倍时，进行扩容 即加载因子为0.75； 每次扩容为元容量的1倍；

**HashTable扩容：默认容量为11，当元素个数超过总容量的0.75倍时，进行扩容，每次增加为原容量的（1倍+1）；

注意：collection和collections的区别：

    Collections是个java.util下的类，是针对集合类的一个工具类,提供一系列静态方法,实现对集合的查找、排序、替换、线程安全化（将非同步的集合转换成同步的）等操作。
    Collection是个java.util下的接口，它是各种集合结构的父接口，继承于它的接口主要有Set和List,提供了关于集合的一些操作,如插入、删除、判断一个元素是否其成员、遍历等。

• 数组 -> 集合：asList方法，将数组转换成list集合。

String[] arr ={"abc","kk","qq"};
List list =Arrays.asList(arr);//将arr数组转成list集合。

• 集合 -> 数组：用的是Collection接口中的toArray()方法;

  public static void main(String[] args) {
      int[] arr1 = { 1, 2, 3, 4, 5 };
      List intList = Arrays.asList(arr1);
      // intList size: 1
      System.out.println(String.format("intList size: %s", intList.size()));
  ​
      Integer[] arr2 = { 1, 2, 3, 4, 5 };
      List integerList = Arrays.asList(arr2);
      // integerList size: 5
      System.out.println(String.format("integerList size：%s", integerList.size()));
  }

  ​

  注意：在使用asList()时尽量不要将基本数据类型数组转List.asList转换得到的ArrayList不是java.util.ArrayList

  原因：

  此处ArrayList是Arrays的内部类,并没有add方法,add方法是父类AbstractList的,但是没有具体实现, ​ 而是直接抛出UnsupportedOperationException异常.

  //错误写法
  public static void main(String[] args) {
      String[] arr = {"abc", "kk", "qq"};
      List list = Arrays.asList(arr);
      // 添加一个元素,抛出异常UnsupportedOperationException
      list.add("bb");
  }
  //正确写法
  public static void main(String[] args) {
      String[] arr = {"abc", "kk", "qq"};
      // 使用new ArrayList包裹一层
      List list = new ArrayList<>(Arrays.asList(arr));
      list.add("bb");
  }
  ​