1、概念

Java中的集合是工具类，可以存储任意数量的具有共同属性的对象。 应用场景

  1. 无法预测存储数据的数量
  2. 同时存储具有一对一关系的数据
  3. 需要进行数据的增删改查
  4. 数据重复的问题

2、体系结构

5.4、Java集合 - 图1

1、Collection

  1. boolean add（E e）：添加元素到集合中
  2. void clear（） ：移除集合中的所有元素，对集合进行清空操作
  3. boolean contains（Object o）：判断集合中是否包含给定的对象
  4. boolean isEmpty() : 判断集合是否为空，为空则返回true
  5. Iterator iterator():迭代器，进行集合遍历
  6. boolean remove(Object o)：移除集合中的给定元素。
  7. int size():求集合当中元素的数量。
  8. Object[] toArray():将集合转换成数组。

2、List（列表）

  1. List是元素有序并且可以重复的集合，成为序列。
  2. List可以精确控制每个元素的插入位置，或删除某个位置的元素。（适合插入和删除）。
  3. List 的两个主要实现类是ArrayList和LinkedList。
  4. List接口中的方法
    1. E get(int index):返回列表当中指定位置的列表元素
    2. int indexOf(Object o):返回给定元素在集合中的索引位置
    3. default void sort(Comparator<? super E> c):对列表进行排序

3、ArrayList

  1. ArrayList底层是以数组实现的。
  2. 动态增长，以满足应用程序的需求。
  3. 因为是基于一片连续的存储空间去存储的，所以在列表的尾部处插入和删除数据非常高效。中间的位置插入或者删除数据就需要进行大量的数组复制，这种情况下消耗时间和资源就会较多。
  4. 更适合查找和更新元素
  5. ArrayList中的元素可以为null
  6. ArrayList中的方法
    1. 构造方法
      1. 不带参数：默认创建容量为10的空集合。
      2. ArrayList(Collection<? extends E> c):
      3. ArrayList(int initialCapacity):规定初始容量。
    2. 成员方法

4、HashSet

  • 元素无序并且不可以重复
  • 只允许一个null元素

5、HashMap

  • 键不能重复
  • 允许使用null值和null键
  • HashMap中的Entry对象是无序排列的

6、Iterator接口以统一的方式对各种集合元素进行遍历

  • hasNext()方法检测集合中是否还有下一个元素
  • next()方法返回集合中的下一个元素

    3、集合中接口和类的特点总结

    一、Collection
    主要用于存储类的对象
    Collection下又是三个接口，分别是List、Queue和Set，List和Queue中可以存储有序且重复的数据，Set中存储的数据是无序且不重复的。
  1. List接口的主要实现类包括ArrayList和LinkedList，LinkedList同时也实现了Queue接口，ArrayList的底层实现是数组，因此在内存中是连续存在的。查询速度快，但增加和删除速度慢。LinkedList底层是基于双向链表的，增加和删除速度快，查询速度慢。
  2. Set接口的主要实现类又HashSet和TreeSet

HashSet是基于哈希表实现的，数据是无序的，HashSet元素可以是null，但只能又一个null。
TreeSet是基于二叉树实现的，可以实现数据的自动排序，确保集合元素处于排序状态，不允许放入空值。
HashSet的性能优于TreeSet，一般情况建议使用HashSet，如果需要使用排序功能建议使用TreeSet

二、Map

主要用于存储键值对的数据
Map的主要实现类包括HashMap和TreeMap，其中HashMap基于哈希表实现，TreeMap基于红黑树实现。
HashMap适用于在Map中插入、删除和定位元素。
TreeMap适用于按自然顺序和自定义顺序对键值对进行遍历
HashMap比TreeMap性能好，所以HashMap使用的更多一些，如果需要对数据进行排序可以使用TreeMap

4、HashMap的复杂度

获取 查找 添加、删除 空间
ArrayList O(1) O(1) O(n) O(N)
LinkedList O(N) O(N) O(1) O(N)
HashMap O(N.Bucket_size) 约等于1 O(N.Bucket_size) O(N.Bucket_size) O(N)

HashMap是对Array和Link的折衷处理，Array与List可以说是两个速度方法的极致，Array注重于数据的获取，而处理修改（添加，删除）的效率非常低；Link由于是每个对象保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。
在JDK8中，由于使用了红黑树来处理较大的链表开销，所以hash这边可以更加省力了，只用计算hashCode并移动到低位就可以了。

5、Java中几个常用的哈希码（hashCode）的算法

  1. Object类的hashCode，返回对象经过处理的内存地址，由于每个对象的内存地址都不一样，所以哈希码也不一样。这个是native方法，取决于JVM的内部设计，一般是某种C地址的偏移。
  2. String类的hashCode，根据String类包含的字符串的内容，根据一种特殊算法返回哈希值，只要字符串的内容相同，返回的哈希码也相同。
  3. Integer等包装类，返回的哈希码就是Integer