一，List集合

1.简介

  • 继承collection接口，List代表一个元素有序、且可重复（包括null）的集合，集合中的每个元素都有其对应的顺序索引
  • · List默认按元素的添加顺序设置元素的索引
  • · 提供了一些通过索引来操作集合中指定位置元素的方法

**

2、List实现类

1. ArrayList

  • · 基于动态数组实现，初始容量10，添加一个元素时，如果超出当前数组的容量，就扩容1.5倍，
  • · 插入、删除元素时，需移动元素，效率较低；查找元素效率高
  • · 非线程安全

2. LinkedList

  • · 是个双向链表，可以被当作栈、队列或双端队列来使用
  • · 插入、删除元素时，效率较高；查找元素要遍历链表，效率较低
  • · 非线程安全

3. Vector：线程安全的动态数组，效率低（已过时，不建议使用）
4. Stack：继承Vector，基于动态数组实现的一个线程安全的栈（后进先出）

3、遍历List的四种方法

初始化数据：

  1. List<String> list = new ArrayList<String>();
  2. list.add("aaa");
  3. list.add("bbb");
  4. list.add("ccc");


方法一：foreach循环遍历

  1. for(String attribute : list) {
  2.     System.out.println(attribute);
  3. }


方法二：for循环遍历

  1. for(int i = 0 ; i < list.size() ; i++) {
  2.     System.out.println(list.get(i));
  3. }

方法三：Iterator（集合类的通用遍历方式）

  1. Iterator it = list.iterator();
  2. while(it.hasNext()) {
  3.     System.ou.println(it.next);
  4. }

集合 - 图1

方法四：ListIterator（使用同Iterator）

  • · ListIterator接口继承了Iterator接口，提供了专门操作List的方法
    1. istIterator<String> listIterator = list.listIterator();
    2. while (listIterator.hasNext()){
    3.   System.out.println(listIterator.next());
    4. }

    4、ListIterator与Iterator的区别

  1. 使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。
  2. ListIterator有add方法，可以向List中添加对象，而Iterator不能。
  3. ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。
  4. ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。

  5. 都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。

    5、使用List的总结

  6. Arrays.asList(…)方法返回一个只读的List对象，不可修改、删除，是Arrays类中的一个内部类

  7. List集合按属性排序：使用Collections.sort()方法，自定义一个比较器

    6.常用方法

    ```java public class TestList { public static void main(String[] args) {

    1.  List<Integer> list=new ArrayList<>();
    2.  List<Integer> list1=new ArrayList<>();
    3.  list1.add(1);
    4.  list1.add(2);
    5.  list1.add(7);
    7.  list.add(1);
    8.  list.add(2);
    9.  list.add(3);
    10.  list.add(4);
    11.  list.add(5);
    12.  list.add(6);
    13.  System.out.println(list.contains(4));
    14.  System.out.println(list.addAll(list1));
    15.  System.out.println(list.indexOf(1));
    16.  System.out.println("------------");
    17.  list.removeAll(list1);

    // System.out.println(list.lastIndexOf(1));

    1.  Object[] objects = list.toArray();

    // System.out.println(objects[1]);

    1.  for(Integer i:list){
    2.      System.out.println(i);
    3.  }

    } }

  3. <a name="UJAD9"></a>
  4. # 二.Set集合
  5. <a name="ngp23"></a>
  6. ## 1.简介
  7. Set集合中的元素是无序的且不可重复， 如果试图把两个相同元素加入同一个Set集合中，则添加操作失败，add()方法返回false，且新元素不会被加入。
  8. ```java
  9. public static void main(String[] args) {
  10.         Set<Integer> set=new TreeSet();
  11.         set.add(3);
  12.         set.add(1);
  13.         set.add(5);
  14.         set.add(2);
  15.         for (Integer i:set){//没有get方法，所以用foreach
  16.             System.out.println(i);
  17.         }
  18.     }
  19.     结果：1 2 3 5

2、HashSet类

HashSet底层数据结构是哈希表，因此具有很好的存取和查找性能。
哈希表：一个元素为链表的数组，综合了链表（存储速度快）和数组（查询速度快）的优点。

1.HashSet的存取原理

  1. 调用对象的hashCode()方法，获得要存储元素的哈希值。
    2. 将哈希值与表的长度(即数组的长度)进行求余运算得到一个整数值，该值就是新元素要存放的位置(即是索引值)。

如果索引值对应的位置上没有存储任何元素，则直接将元素存储到该位置上。
如果索引值对应的位置上已经存储了元素，则执行第3步。
3.遍历该位置上的所有旧元素，依次比较每个旧元素的哈希值和新元素的哈希值是否相同。

如果有哈希值相同的旧元素，则执行第4步。
如果没有哈希值相同的旧元素，则执行第5步。
4.比较新元素和旧元素的地址是否相同

如果地址值相同则用新的元素替换老的元素。停止比较。
如果地址值不同，则新元素调用equals方法与旧元素比较内容是否相同。

如果返回true，用新的元素替换老的元素，停止比较。
如果返回false，则回到第3步继续遍历下一个旧元素。
5.说明没有重复，则将新元素存放到该位置上并让新元素记住之前该位置的元素。

2.HashSet的特点

集合中的元素值可以是null
hashSet不是同步的，如果多个线程同时访问一个Set，只要有一个线程修改了Set中的值，就必须进行同步处理，通常通过同步封装这个Set对象来完成同步，如果不存在这样的对象，可以使用Collections.synchronizedSet()方法完成。

3.为什么不直接使用数组，而用HashSet呢？

因为数组的索引是连续的而且数组的长度是固定的，无法自由增加数组的长度。而HashSet就不一样了，HashCode表用每个元素的hashCode值来计算其存储位置，从而可以自由增加HashCode的长度，并根据元素的hashCode值来访问元素。而不用一个个遍历索引去访问，这就是它比数组快的原因。

4.LinkedHashSet类

LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时使用链表维护元素的次序，这样使得元素看起来是以插入的顺序保存的，也就是说当遍历集合LinkedHashSet集合里的元素时，集合将会按元素的添加顺序来访问集合里的元素。
输出集合里的元素时，元素顺序总是与添加顺序一致。但是LinkedHashSet依然是HashSet，因此它不允许集合重复。

3.TreeSet类

1.内部存储机制

TreeSet内部实现的是红黑树，默认整形排序为从小到大
re.png

2.TreeSet提供了额外的方法

//如果TreeSet采用了定制顺序，则该方法返回定制排序所使用的Comparator，如果TreeSet采用自然排序，则返回null；
Comparator comparator();
//返回集合中的第一个元素；
Object first();
//返回集合中的最后一个元素；
Object last();
//返回指定元素之前的元素。
Object lower(Object e);
//返回指定元素之后的元素。
Object higher(Object e);
//返回此Set的子集合，含头不含尾；
SortedSet subSet（Object fromElement，Object toElement）;
//返回此Set的子集，由小于toElement的元素组成；
SortedSet headSet(Object toElement);
//返回此Set的子集，由大于fromElement的元素组成;
SortedSet tailSet(Object fromElement);

  1. public class TreeSetDemo {
  2.     public static void main(String[] args) {
  3.         testTreeSet();
  4.     }
  5.     public static void testTreeSet(){
  6.         TreeSet<Integer> nums = new TreeSet<>();
  7.         //向集合中添加元素
  8.         nums.add(5);
  9.         nums.add(4);
  10.         nums.add(2);
  11.         nums.add(15);
  12.         nums.add(-4);
  13.         //输出集合，可以看到元素已经处于排序状态
  14.         System.out.println(nums);//[-4, 2, 5, 15]
  15.         System.out.println("集合中的第一个元素："+nums.first());//集合中的第一个元素：-4
  16.         System.out.println("集合中的最后一个元素："+nums.last());//集合中的最后一个元素：15
  17.         System.out.println("集合小于4的子集，不包含4："+nums.headSet(4));//集合小于4的子集，不包含4：[-4, 2]
  18.         System.out.println("集合大于等于-4的子集："+nums.tailSet(-4));//集合大于5的子集：[2, 5, 15]
  19.         System.out.println("集合中大于等于-3，小于4的子集："+nums.subSet(-3,4));//集合中大于等于-3，小于4的子集：[2]
  20.         System.out.println("该元素之前的一个元素："+nums.lower(2));//-4
  21.         System.out.println("该元素之后的一个元素："+nums.higher(2));//4
  23.     }
  24. }

自然排序

TreeSet会调用集合元素的compareTo(Objec obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列，这就是自然排序。

自定义排序：

Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现该接口的类必须实现该方法，实现了该接口的类必须实现该方法，实现接口的类就可以比较大小了。当调用一个一个对象调用该方法与另一个对象进行比较时， compareTo(Object obj)如果返回0表示两个对象相等；如果返回正整数则表明obj1大于obj2,如果是负整数则相反。

案列

实现存储Person类的集合，排序方式，按年龄大小，如果年龄相等，则按name字符串长度，如果长度相等则比较字符。如果name和age都相等则视为同一对象。

三,Map集合

1.简介

Map 未继承 Collection，而是独立的接口，Map 是一种把键对象和值对象进行映射的集合，它的每一个元素都包含了一对键对象和值对象，Map 中存储的数据是没有顺序的， 其 key 是不能重复的，它的值是可以有重复的。
Map 接口常见的四个实现类：Hashtable，HashMap，TreeMap，LinkedHashMap；

2.Map集合的特点

1.能够存储唯一的列的数据(唯一，不可重复)
2.能够存储可以重复的数据(可重复)
3.值的顺序取决于键的顺序
4.键和值都是可以存储null元素的

3.HashMap集合

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）
此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
HashMap如何运行的：
HashMap在Map.Entry静态内部类实现中存储key-value对。HashMap使用哈希算法，在put和get方法中，它使用hashCode()和equals()方法。当我们通过传递key-value对调用put方法的时候，HashMap使用Key hashCode()和哈希算法来找出存储key-value对的索引。Entry存储在LinkedList中，所以如果存在entry，它使用equals()方法来检查传递的key是否已经存在，如果存在，它会覆盖value，如果不存在，它会创建一个新的entry然后保存。当我们通过传递key调用get方法时，它再次使用hashCode()来找到数组中的索引，然后使用equals()方法找出正确的Entry，然后返回它的值。

特点：
键无序，唯一，类似于Set集合
值有序，可重复，类似于List
底层数据结构是哈希表，保证键唯一
允许键为null，值为null

遍历

  1. public class TestMap {
  2.     public static void main(String[] args) {
  3.         HashMap<String,String> map=new HashMap<>();
  4.         HashMap<String,String> map1=new HashMap<>();
  5.         map.put("name","zhangsan");
  6.         map.put("age","45");
  7.         map1.put("name","zhang");
  8.         map1.put("age2","45");
  9.         System.out.println("第一种遍历");
  10.         Set<String> strings = map.keySet();//把键值放入到set集合中
  11.         for(String str:strings){
  12.             System.out.println(str+"="+map.get(str));
  13.         }
  14.         System.out.println("第二种遍历");
  15.         Set<Map.Entry<String, String>> entries = map.entrySet();
  16.         Iterator<Map.Entry<String, String>> iterator = entries.iterator();
  17.         while(iterator.hasNext()){
  18.             Map.Entry<String, String> entry = iterator.next();
  19.             String key=entry.getKey();
  20.             String value=entry.getValue();
  21.             System.out.println(key+"="+value);
  23.         }
  24.         map.putAll(map1);
  25.         System.out.println("第三种遍历方法");
  26.         for(Map.Entry<String,String> entry:entries){
  27.             System.out.println(entry.getKey()+"="+entry.getValue());
  28.         }
  29.         System.out.println("第四种方法");
  30.         for(String str:map.values()){
  31.             System.out.println(str);
  32.         }
  33. //        map.clear();
  34.         System.out.println(map.containsKey("name"));
  36. //        System.out.println(map.remove("name"));
  37. //        System.out.println(map.remove("name","zhangsan"));//false 与remove传递一个参数差不多
  38. //        System.out.println(map.get("name"));
  39. //        System.out.println("第三种遍历方法");
  40. //        for(Map.Entry<String,String> entry:entries){
  41. //            System.out.println(entry.getKey()+"="+entry.getValue());
  42. //        }
  43.     }
  44. }

HashMap和Hashtable的区别

HashMap是不安全的不同步的效率高的 允许null键和null值
Hashtable是安全的同步的效率低的 不允许null键和null值
底层都是哈希表结构

4.LinkedHashMap集合

Map 接口的哈希表和链接列表实现，具有可预知的迭代顺序，相当于一个栈，先 put 进去的最后出来，先进后出。

特点：
键有序，唯一，
值有序，可重复，类似于List
底层数据结构是哈希表和链表，哈希表保证键唯一，链表保证键有序

5.TreeMap集合

基于红黑树 (red-black tree) 数据结构实现，按 key 排序，默认的排序方式是升序。

总结：

如果List 和Map存储的元素都比较多。那么在取元素方面，List要慢很多。 但是这也不是绝对的，因为List底层基于数组，如果你明确的知道你要取的元素在哪个下标上，那么List也是相当的快。但是如果你不清楚，只能通过迭代内部全部元素然后进行条件判断查找，那么List就要慢的多，因为他要从头到尾一个个的元素去查，直到找到满足你的要求的那个元素，而Map则不需要迭代，因为Map有键，直接取键对应的值。 对于添加元素，List是在数组的结尾追加，当容量不够时，创建一个新的更长的数组然后将旧的全部拷贝过来。Map和他的方式差不多，也是容量不足的时候需要重新创建新的然后拷贝，但是当发生删除元素时，List简直就是灾难。假设你有10000个元素，你删除首个元素，在删除完毕以后 List中的所有元素都必须进行一次移动操作，向前位移。。。而Map则不需要。

大概就是这样，如果你考虑一个长度比较可预测的保存元素的集合，并且很少有删除操作，大部分是进行全部迭代的操作，那么用List会比较合适。
如果你的List还要经常增删，那么用LinkedList比较合适。
如果你要快速查找，取值，用HashMap比较合适。
如果同时要保证，元素放进去的顺序和取出来的顺序一致用LinkedHashMap。