Java集合

shuyepl 2023-03-21 19:14:53

Categories： Tags：

集合

跟数组一样，用来装一大堆东西的，相对于数组的话，集合有它的优点：

容量可以动态扩展
底层数据结构多样性，适用于不同的使用情况

集合的继承框架图

Collection
├── List
│   ├── ArrayList
│   ├── Vector
│   └── LinkedList
├── Queue
│   ├── PriorityQueue
│   ├── ArrayQueue
│   ├── PriorityBlockingQueue
│   └── LinkedBlockingQueue
├── Set
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
├── Deque
│   ├── ArrayDeque
│   └── LinkedList
└── Map
    ├── HashMap
    ├── HashTable
    ├── LinkedHashMap
    └── TreeMap

集合分为两部分，一部分是Collection，一部分是Map（没有标明接口的都是实现类）

Iterable接口
- Collection接口
  - List接口
    - ArrayList
    - LinkedList（这个类还实现了Deque接口）
    - Vector（较老，线程安全–>较慢，较少适用，可以使用ArrayList替代）
      - Stack
  - Set接口
    - HashSet
    - LinkedHashSet
    - Sortedset接口
      - TreeSet接口
  - Queue
    - PriorityQueue
    - Deque接口
      - ArrayDeque
Map接口
- HashMap
- Hashtable（线程安全–>较慢，较少适用）
  - Properties
- SortedMap接口
  - TreeMap：有序，默认升序，元素要求实现comparable接口，或者在创建TreeMap的时候传入一个Comparator。

集合特点

List：有序可重复

ArrayList：数组实现，查询快，增删慢，数组末尾增删的效率O(1)。默认初始化容量为10，扩容倍数为1.5，懒加载，未添加元素的时候，初始化容量为0的数组，第一次添加元素时才初始化数组的长度为10，扩容的计算方式：int newCapacity = oldCapacity + (oldCapacity >> 1) ，实现了RandomAccess接口，可以快速随机访问数组中的元素（RandomAccess接口是一个标记来接口，里面没有实际的内容，快速随机访问是数组本身的特性。）
LinkedList：双向链表实现，查询慢，增删快（实现了Deque接口）
Vector：底层是数组，初始化容量为10，扩容为原容量两倍，线程安全，较慢，较少适用，可用ArrayList替代

Set：无序不可重复

HashSet：底层是散列表（数组加链表的结构，数组的对象是链表的头结点），执行插入操作的时候，调用元素的hashCode方法，获得hash码，计算出对象的桶位置（数组中的位置），然后在这个位置上的链表中查询是否有和这个元素相同的元素，相同的标准是equals方法是否相同，相同的话就证明这个Set中已有该元素，插入失败；如果不相等，那么执行插入操作。所以hashCode方法和equals方法要一起重写，同时，编写代码的时候一定要保证equals方法相等的时候hashCode要相等，而hashCode相等则不强制要求equals相等。HashSet其实是利用了HashMap的Key来进行实现的。
TreeSet：底层是树结构，放进去的数组是有序的。

Map：无序，键值对存储，键不可重复，值可重复

HashMap：默认最小容量16，最大容量2^31，默认加载因子0.75，扩容为两倍，JDK1.8以前为数组加链表的结构；JDK1.8为数组加链表加红黑树结构，在特定情况下会发生转换，数组中一个位置上的链表长度达到8之后，并且数组的总长度达到了64，该链表就会转换成红黑树，红黑树的元素数量减少到6就会从红黑树转换成链表。数组的长度一定是2的幂次方，允许值和键为null
- 为什么要设置6和8这两个转换的点：6和8中间还有个7，可以防止反复从树转换成为链表以及从链表转换成为树。（这个东西设置成这个样子本来就是为了增加效率的，如果反复转换的话其实效率就被硬拉低了。）红黑树查找的平均时间复杂度是log(n)，而链表是n/2，当长度为8时，链表查找的时间为4，而红黑树为3，所以，转换成红黑树的效率更高，而当长度为6时，链表的查找时间为3，虽然红黑树也很快，但是，生成红黑树这个结构是需要耗费时间的，所以采用链表的方式进行存储。
- 1.8之后解决哈希冲突的方案：原本直接哈希值取模的方式，对于哈希码高位的利用不够，所以现在就是将哈希值的高位（16位）与低位进行异或运算，充分运用哈希值的高16位，使散列表更加的散，减少哈希冲突发生的概率。
Hashtable：初始化容量11，扩容2倍+1，线程安全，不允许key为null

集合方法

看API文档不比看文章里面记录的寥寥几个方法香？

Java 8 中文版 - 在线API中文手册 - 码工具 (matools.com)

迭代器

总结

迭代器就是指Iterator对象，Collection接口的实现类都可以调用iterator方法获取一个迭代器对象，用来进行遍历操作，在操作迭代器对象的时候记得一点，如果在遍历的过程中调用了非迭代器的方法对集合进行了增删改操作记得重新更新迭代器对象，不然会报错 ConcurrentModificationException，要想在不报错的情况下进行删除操作的话可以使用迭代器对象的相关方法。

对于List接口来说，它还有一个listIterator方法，这个方法返回一个ListIterator接口可以接收的对象，而ListIterator接口继承自Iterator接口，除了Iterator接口本身提供的方法外，ListIterator还扩展了很多自身的方法，可以对集合（这里讲的是List接口下的集合）进行更加灵活的操作，详细看API文档

Java 8 中文版 - 在线API中文手册 - 码工具 (matools.com)

对于迭代器的一点想法

~~这个部分有点小啰嗦的~~

迭代器就是一个“指针”，这个指针在刚开始创建好迭代器对象时指向是整个集合（指List接口下的，下面不再反复说了）第一个元素的前面一个位置，之后它调用一次next方法或者调用一次previous方法就跳一个位置，每次跳的时候都是跳到两个元素之间的间隙里面，同时每次跳的时候都会将它跳过的那个对象拿在手里，调用remove操作或者set操作都是对这个拿在手里的对象进行操作；创建一个指定下标的ListIterator的时候，这个指针指向列表中对应下标元素的前面一个间隙里。

Comparable接口和Comparator接口

简单比较

这两个接口的作用都是给元素添加排序的参考依据，这两个接口提供参考依据的方式有点差别

类实现Comparable接口并且重写compareTo方法
比较器对象继承自Comparator接口，并且重写compare方法

自己的总结：compareTo方法调用的时候，里面要传入一个对象的，如果返回结构是调用对象减去参数的那个对象，升序，反之，参数的对象减去调用的对象，降序。compare方法中要传入两个对象，第一个参数对象减去第二个参数对象，升序，反之，第二个参数对象减去第一个参数对象，降序。

为什么要设计两套接口来实现排序功能

Comparable接口用于对象在设计的时候就考虑好会进行排序操作的了，这样的对象在创建好之后基本上就可以直接对它进行排序操作了，而Comparetor这个接口的话，我觉得老杜的资料里面的一句话说得很好，就是分离了排序算法和对象，可以实现灵活的排序方式，对同类的数据可以进行多种方式的排序。

参考资料：

[Java零基础教程视频（适合Java 0基础，Java初学入门）_哔哩哔哩_bilibili
Java集合详解（非常详细！！！）_阿里官方架构师的博客-CSDN博客
[HashMap 链表和红黑树的转换 - abcdefghijklmnop - 博客园 (cnblogs.com)](https://www.cnblogs.com/aaabbbcccddd/p/14849064.html#:~:text=当链表元素个数大于8的时候，就会转换为红黑树；当红黑树元素个数小于6的时候，就会转换回链表。,hashMap中确实定义了这两个常量，但并非简单通过元素个数的判断来进行转换。链表转换为红黑树的最终目的，是为了解决在map中元素过多，hash冲突较大，而导致的读写效率降低的问题。)

MyBatis引入logback框架

MySQL基本语句