集合分为Collection / Map

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Wvcc6h9X-1621563875247)(C:\Users\yangzhou\AppData\Roaming\Typora\typora-user-images\image-20210512092940322.png)]

• Collection对象之间没有指定的顺序，允许有重复元素和多个null元素对象；

  它是Set和List接口的父类，是一种最通用型的集合接口。

集合的分类

• List：有序列表(可以有重复元素)集合
• Set：没有重复元素的集合
• Map：通过键值对查找映射表的集合——需要排序用 TreeMap

集合细分

• List——有序存储
  • LinkedList：双向链表结构，适合插入删除(线程不安全)
    • LinkedList 查找慢的原因是找每个元素要从头开始遍历
  • ArrayList：动态数组结构，适合随机访问(线程不安全)
  • Vector：数组结构，Stack 是 Vector 的实现类(线程安全)
• Set——不可重复
  • 不可重复的实现：往HashSet中存放元素时，默认会对数据和集合中的数据进行比较，首先会比较它们的Hashcode
    • 如果 hashcode 不同，则直接插入
    • 当Hashcode相同时
      • 再进行equals()比较，如果返回true则证明两个元素相同，将不对该元素进行存放
      • 如果是false，则会进行散列，然后存放。
  • hashcode 的产生
    • 每个对象肯定有一个物理地址，将物理地址对应的整数通过 hash 函数，就得到一个 hashcode，也就是 hash 表中的位置(hashcode 值相同，说明在同一个散列存储结构中)
  • HashSet 使用 hash 表(数组)存储元素
    • 不需要自动排序就用LinkedHashSet
  • TreeSet 底层是 TreeMap，在 TreeSet 中存入数据，相当于存入 TreeMap 的 key 值，在 TreeSet 排序存储后，就有value 值了。
• Map——key 值不可重复
  • HashMap 线程不安全，效率高，允许 key 和 value 为 null
    • HashMap 在 JDK 1.8 以前的版本中，HashMap 的实现是数组+链表，当有大量元素时，链表会很长，遍历起来很麻烦
    • JDK 1.8 以后，HashMap的实现依靠 数组+红黑树 或 数组+链表。添加元素时，若桶中链表元素超过8个，链表就会转换成红黑树；删除元素和扩容时，若桶中结构为红黑树并且树中元素较少时，进行剪枝或还原成链表（少于6个）。遍历查找的时间复杂度为 O(logn),性能较高。
  • HashTable 是线程安全的，这个类中一些方法加入了 synchronized 关键字
    是线程安全的，这个类中一些方法加入了 synchronized 关键字
  • TreeMap ——非线程安全，基于红黑树对所有 key 排序