集合简介

  1. 集合(Collection)就是“由若干个确定的元素所构成的整体”。为了便于处理一组类似的数据,在计算机中引入集合。
  2. 在Java中,如果一个Java对象可以在内部持有若干其他Java对象,并对外提供访问接口,我们把这种Java对象称为集合。显然,Java的数组可以看作是一种集合:

    1. String[] ss = new String[10]; // 可以持有10个String对象
    2. ss[0] = "Hello"; // 可以放入String对象
    3. String first = ss[0]; // 可以获取String对象
  3. 数组有如下限制:1)数组初始化后大小不可变;2)数组只能按索引顺序存取。因此,我们需要各种不同类型的集合类来处理不同的数据。

  4. Java标准库自带的java.util包提供了集合类:Collection,它是除Map外所有其他集合类的根接口。Java的java.util包主要提供了以下三种类型的集合:
  • List:一种有序列表的集合,例如,按索引排列的Student的List;
  • Set:一种保证没有重复元素的集合,例如,所有无重复名称的Student的Set;
  • Map:一种通过键值(key-value)查找的映射表集合,例如,根据Student的name查找对应Student的Map。
  1. Java集合的设计有几个特点:一是实现了接口和实现类相分离,二是支持泛型,我们可以限制在一个集合中只能放入同一种数据类型的元素。
  2. Java访问集合总是通过统一的方式——迭代器(Iterator)来实现,它最明显的好处在于无需知道集合内部元素是按什么方式存储的。
    注意:有一小部分集合类是遗留类,不应该继续使用:
  • Hashtable:一种线程安全的Map实现;
  • Vector:一种线程安全的List实现;
  • Stack:基于Vector实现的LIFO的栈;
  • Enumeration<E>:已被Iterator<E>取代。

    使用List

  1. 在集合类中,List是最基础的一种集合:它是一种有序列表。List的行为和数组几乎完全相同,在添加和删除元素的时候,会非常不方便。因此,在实际应用中,需要增删元素的有序列表,我们使用最多的是ArrayList。实际上,ArrayList在内部使用了数组来存储所有元素。
  2. ArrayList把添加和删除的操作封装起来,让我们操作List类似于操作数组,却不用关心内部元素如何移动。
  3. 我们考察List<E>接口,可以看到几个主要的接口方法:
  • 在末尾添加一个元素:boolean add(E e)
  • 在指定索引添加一个元素:boolean add(int index, E e)
  • 删除指定索引的元素:int remove(int index)
  • 删除某个元素:int remove(Object e)
  • 获取指定索引的元素:E get(int index)
  • 获取链表大小(包含元素的个数):int size()
  1. 实现List接口并非只能通过数组(即ArrayList的实现方式)来实现,另一种LinkedList通过“链表”也实现了List接口。在LinkedList中,它的内部每个元素都指向下一个元素:

    image.png

  2. 我们来比较一下ArrayListLinkedList: | | ArrayList | LinkedList | | :—- | :—- | :—- | | 获取指定元素 | 速度很快 | 需要从头开始查找元素 | | 添加元素到末尾 | 速度很快 | 速度很快 | | 在指定位置添加/删除 | 需要移动元素 | 不需要移动元素 | | 内存占用 | 少 | 较大 |

通常情况下,我们总是优先使用ArrayList

  1. List的特点
  • 允许添加重复的元素
  • 允许添加null
    public class ListTest {
      public static void main(String[] args) {
          List<String> list=new ArrayList<>();
          list.add("apple");//size=1
          list.add("pear"); //size=2
          list.add("apple"); //size=3
          list.add(null); //size=4
          System.out.println(list.size());
          System.out.println(list);
      }
    }
    
  1. 创建LIst的方法
  • 使用ArrayListLinkedList
  • 通过List接口提供的of()方法(JDK9新特性)
    List<Integer> list = List.of(1, 2, 5);
    //但是List.of()方法不接受null值,如果传入null,会抛出NullPointerException异常。
    
  1. 遍历List的方法
  • for循环+索引

    public class Main {
      public static void main(String[] args) {
          List<String> list = new ArrayList<>();
          list.add("apple");//size=1
          list.add("pear"); //size=2
          list.add("banana"); //size=3
          for (int i = 0; i < list.size(); i++) {
              String s = list.get(i);
              System.out.println(s);
          }
      }
    }
    

    但这种方式并不推荐,一是代码复杂,二是因为get(int)方法只有ArrayList的实现是高效的,换成LinkedList后,索引越大,访问速度越慢。

  • 使用迭代器Iterator来访问List

Iterator对象有两个方法:boolean hasNext()判断是否有下一个元素,E next()返回下一个元素。

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple");//size=1
        list.add("pear"); //size=2
        list.add("banana"); //size=3
        for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            System.out.println(s);
        }
    }
}

由于Iterator遍历是如此常用,所以,Java的for each循环本身就可以帮我们使用Iterator遍历。

for (String s : list) {
     System.out.println(s);
}
  1. List和Array的转换

    1. List—>Array

      1. 调用toArray()方法直接返回一个Object[]数组,这种方法会丢失类型信息,所以实际应用很少。

        Object[] array=list.toArray();
        for (Object s:array){
        System.out.println(s);
        }
        

        ii. 给toArray(T[])传入一个类型相同的ArrayList内部自动把元素复制到传入的Array中。

        public class Main {
        public static void main(String[] args) {
        List<Integer> list = List.of(12, 34, 56);
        Integer[] array = list.toArray(new Integer[3]);
        for (Integer n : array) {
           System.out.println(n);
        }
        }
        }
        

        注意:如果传入的数组不够大,那么List内部会创建一个新的刚好够大的数组,填充后返回;如果传入的数组比List元素还要多,那么填充完元素后,剩下的数组元素一律填充null
        b. Array—>List

      2. 通过List.of(T...)方法(JDK9)

      3. 对于JDK 11之前的版本,可以使用Arrays.asList(T...)方法把数组转换成List
        Integer[] array1 = { 1, 2, 3 };
        List<Integer> list2 = Arrays.asList(array);
        System.out.println(list2);
        
        注意,如果我们调用List.of(),它返回的是一个只读List,对只读List调用add()remove()方法会抛出UnsupportedOperationException

        编写equals方法

  2. 要正确使用Listcontains()indexOf()这些方法,放入的实例必须正确覆写equals()方法,否则,放进去的实例,查找不到。我们之所以能正常放入StringInteger这些对象,是因为Java标准库定义的这些类已经正确实现了equals()方法。

  3. 如何正确编写equals()方法?equals()方法要求我们必须满足以下条件:
  • 自反性(Reflexive):对于非nullx来说,x.equals(x)必须返回true
  • 对称性(Symmetric):对于非nullxy来说,如果x.equals(y)true,则y.equals(x)也必须为true
  • 传递性(Transitive):对于非nullxyz来说,如果x.equals(y)truey.equals(z)也为true,那么x.equals(z)也必须为true
  • 一致性(Consistent):对于非nullxy来说,只要xy状态不变,则x.equals(y)总是一致地返回true或者false
  • null的比较:即x.equals(null)永远返回false
  1. 以Person为例,定义“相等”的逻辑含义。对于Person类,如果name相等,并且age相等,我们就认为两个Person实例相等。 ```java public class Main { public static void main(String[] args) {
     List<Person> list = List.of(
         new Person("Xiao Ming"),
         new Person("Xiao Hong"),
         new Person("Bob")
     );
     System.out.println(list.contains(new Person("Bob"))); // TRUE
    
    } }

class Person { public String name; public int age;

public Person(String name) {
    this.name = name;
}

public boolean equals(Object o) {
    if (o instanceof Person) {
        Person p = (Person) o;
        boolean nameEquals = false;
        if (this.name == null && p.name == null) {
            nameEquals = true;
        }
        if (this.name != null) {
            nameEquals = this.name.equals(p.name);
        }
        return nameEquals && this.age == p.age;
    }
    return false;
}

}

如果`Person`有好几个引用类型的字段,上面的写法就太复杂了。要简化引用类型的比较,我们使用`Objects.equals()`静态方法:
```java
public boolean equals(Object o) {
    if (o instanceof Person) {
        Person p = (Person) o;
        return Objects.equals(this.name, p.name) && this.age == p.age;
    }
    return false;
}

使用Objects.equals()比较两个引用类型是否相等的目的是省去了判断null的麻烦。两个引用类型都是null时它们也是相等的。

使用Map

  1. Map这种键值(key-value)映射表的数据结构,作用就是能高效通过key快速查找value(元素)。
  2. Map<K, V>是一种键-值映射表,当我们调用put(K key, V value)方法时,就把keyvalue做了映射并放入Map。当我们调用V get(K key)时,就可以通过key获取到对应的value。如果key不存在,则返回null。和List类似,Map也是一个接口,最常用的实现类是HashMap
  3. 如果只是想查询某个key是否存在,可以调用boolean containsKey(K key)方法。
  4. Map中不存在重复的key,value可重复,因为放入相同的key,只会把原有的key-value对应的value给替换掉。

    public class MapTest {
     public static void main(String[] args) {
         Person p = new Person("liu", 22);
         Map<String, Person> map = new HashMap<>();
         map.put("liu", p);//将“liu”和Person实例映射并关联
         Person target = map.get("liu"); //通过key查找并返回映射的Person实例
         System.out.println(target == p); //true,同一个实例
         System.out.println(target.age); //22
         Person another=map.get("Bob");
         System.out.println(another); //未找到,返回null
         System.out.println(map.containsKey("liu"));
     }
    }
    
  5. 遍历Map

  • 键找值方式:要遍历key可以使用for each循环遍历Map实例的keySet()方法返回的Set集合,它包含不重复的key的集合

    public static void main(String[] args) {
      Map<String, Integer> map = new HashMap<>();
      map.put("apple", 123);
      map.put("pear", 456);
      map.put("banana", 789);
      for (String key : map.keySet()) {
          Integer value = map.get(key);
          System.out.println(key + " = " + value);
      }
    }
    
  • 键值对方式:同时遍历keyvalue可以使用for each循环遍历Map对象的entrySet()集合,它包含每一个key-value映射

    public static void main(String[] args) {
      Map<String, Integer> map = new HashMap<>();
      map.put("apple", 123);
      map.put("pear", 456);
      map.put("banana", 789);
      for (Map.Entry<String, Integer> entry : map.entrySet()) {
          String key = entry.getKey();
          Integer value = entry.getValue();
          System.out.println(key + " = " + value);
      }
    }
    
  1. MapList不同的是,Map存储的是key-value的映射关系,并且,它不保证顺序。在遍历的时候,遍历的顺序既不一定是put()时放入的key的顺序,也不一定是key的排序顺序。

    HashMap&HashCOde

  2. HashMap之所以能根据key直接拿到value,原因是它内部通过空间换时间的方法,用一个大数组存储所有value,并根据key直接计算出value应该存储在哪个索引。

  3. HashMap:存储数据采用的哈希表结构,元素的存取顺序不能保证一致。由于要保证键的唯一、不重复,需要重写键的hashCode()方法、equals()方法。
  4. Map的内部,对key做比较是通过equals()实现的,正确使用Map必须保证:作为key的对象必须正确覆写equals()方法。通过key计算索引的方式就是调用key对象的hashCode()方法,它返回一个int整数。HashMap正是通过这个方法直接定位key对应的value的索引,继而直接返回value
  5. 正确使用Map必须保证:
    1. 作为key的对象必须正确覆写equals()方法,相等的两个key实例调用equals()必须返回true
    2. 作为key的对象还必须正确覆写hashCode()方法,且hashCode()方法要严格遵循以下规范:
    • 如果两个对象相等,则两个对象的hashCode()必须相等;
    • 如果两个对象不相等,则两个对象的hashCode()尽量不要相等。

即对应两个实例ab

  • 如果ab相等,那么a.equals(b)一定为true,则a.hashCode()必须等于b.hashCode()
  • 如果ab不相等,那么a.equals(b)一定为false,则a.hashCode()b.hashCode()尽量不要相等。
    1. 我们把不同的key具有相同的hashCode()的情况称之为哈希冲突。在冲突的时候,一种最简单的解决办法是用List存储hashCode()相同的key-value。显然,如果冲突的概率越大,这个List就越长,Mapget()方法效率就越低。