[数据结构与算法]学习记录：集合

集合

概念：对象的容器，定义了对多个对象进行操作的常用方法，可实现数组的功能

和数组的区别

1. 数组的长度固定，集合长度不固定
2. 数组可以存储基本类型和引用类型，集合只能存储引用类型
3. 都位于java.util.*里

Collection体系集合

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lohcvAWv-1629465662810)(C:\Users\ONCE-Jam\Desktop\超车\笔记\QQ截图20210820144314.png)]

Collection父接口

特点：代表一组任意类型的对象，无序、无下标、不能重复

方法:

boolean add(Object obj);//添加一个对象
boolean addAll(Collection c);//将一个集合中的所有对象添加到此集合中
void clear();//清空此集合中的所有对象
boolean contains(Object o);//检查此集合中是否包含o对象
boolean equals(Object o);//比较此集合是否与指定对象相等
boolean isEmpty();//判断此集合是否为空
boolean remove(Object o);//在此集合中移除o对象
int size();//返回此集合中的元素个数
Object[] toArray();//将此集合转换为数组
//可以使用增强for来遍历collection
//可以使用迭代器遍历 iterator方法 Iterator是接口

注意！iterator方法的hasNext()方法是判断当前指向的下一个有没有元素，最开始指向第一个元素的上方

迭代过程中不能使用collection的删除方法，会报异常，可以试用iterator的删除方法

List子接口

有序、有下标、元素可以重复

void add(int index, Object o);//在index位置插入对象o
boolean addAll(int index, Collection c);//将一个集合中的元素添加到此集合中的index位置
Object get(int index);//返回集合中指定位置的元素
List subList(int fromIndex, int toIndex);//返回fromIndex和toIndex之间的集合的元素

有列表迭代器，和Iterator的区别在于，列表迭代器可以向前向后遍历hasPrevious和previous和previousIndex三个方法

remove是根据下标来删除，可以通过强转成Object或new Integer来实现根据数字删除

List实现类

ArrayList

1. 数组结构实现，查询快、增删慢

2. JDK1.2版本，运行效率快、线程不安全

3. remove()可以通过下标或对象来删除

4. indexOf查找下标

5. 通过重写equals改变比较规则，可以方便查找与删除

   源码分析

   1. 默认容量 DEFAULT_CAPACITY = 10;如果没有向集合中添加任何元素时，容量为0

   2. 存放元素的数组 elementData

   3. 实际元素个数 size

   4.  public boolean add(E e) {
              ensureCapacityInternal(size + 1);  // Increments modCount!!
              elementData[size++] = e;
              return true;
          }
      
      
        private void ensureCapacityInternal(int minCapacity) {
              if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
              }
      
              ensureExplicitCapacity(minCapacity);
          }
      
          private void ensureExplicitCapacity(int minCapacity) {
              modCount++;
      
              // overflow-conscious code
              if (minCapacity - elementData.length > 0)
                  grow(minCapacity);
          }
      
          private void grow(int minCapacity) {
              // overflow-conscious code
              int oldCapacity = elementData.length;
              int newCapacity = oldCapacity + (oldCapacity >> 1);
              if (newCapacity - minCapacity < 0)
                  newCapacity = minCapacity;
              if (newCapacity - MAX_ARRAY_SIZE > 0)
                  newCapacity = hugeCapacity(minCapacity);
              // minCapacity is usually close to size, so this is a win:
              elementData = Arrays.copyOf(elementData, newCapacity);
          }
      

   5. 每次扩容，新容量是原来的1.5倍

Vector

1. 数组结构实现，查询快、增删慢

2. JDK1.0版本，运行效率慢、线程安全

3. 枚举器遍历

4. Enumeration en = vector.elements();
   while(en.hasMoreElements()){
       String o = (String)en.nextElement();
       System.out.println(o);
   }
   

LinkedList

1. 链表结构实现，增删快、查询慢
2. 可以使用迭代器和列表迭代器

泛型

1. 本质是参数化类型，把类型作为参数船体
2. 常见形式有泛型类、泛型接口、泛型方法
3. 语法<T,…> T成为类型占位符，表示一种引用形式
4. 1. 提高代码的重用性
   2. 防止类型转换异常，提高代码的安全性

泛型类

1. 可以使用泛型创建变量
2. 使用泛型作为方法的参数
3. 使用泛型作为方法的返回值

泛型接口

1. 不能有静态常量
2. 可以作为参数和返回值
3. 接口被实现时需要写明泛型的类
4. 可以用泛型类实现泛型接口（不用写明类）

泛型方法

1. 语法： 返回值类型
2. 可以作为参数和返回值
3. 调用泛型方法，类型由传入的类型决定

泛型集合

1. 参数化类型、类型安全的集合，强制集合元素的类型必须一致
2. 编译时即可检查，而非运行时抛出异常
3. 访问时，不必类型转换
4. 不同泛型之间引用不能相互赋值，泛型不存在多态

Set子接口

无序、无下标、元素不可重复

方法全部继承自Collection集合

Set实现类

HashSet

1. 基于HashCode实现元素不重复
2. 当存入元素的哈希码相同时，会调用equals进行确认，如果为true则拒绝后者存入
3. 可以使用增强for，迭代器来遍历
4. 存储结构：哈希表（数组+列表+红黑树）
5. 使用HashSet实际就是在使用hashMap，hashset的add实际就是用的hashMap的key

TreeSet

1. 基于排列顺序实现元素不重复
2. 实现了SortedSet接口，对集合元素自动排序
3. 元素对象的类型必须实现Comparable接口，制定排序规则
4. 通过CompareTo方法确定是否为重复元素
5. 可以创建集合时就指定比较规则，通过匿名内部类comparator
6. 实际用的是TreeMap

Map集合

Map接口

1. 用于存储任意键值对（Key-Value）
2. 键：无序、无下标、不允许重复
3. 值：无序、无下标、允许重复

方法

V put(K key,V value);//将对象存入集合中，关联键值，key重复则覆盖原值
Object get(Object key);//根据键获取对应的值
Set<K>;//返回所有值的Collection集合
Set<Map.Entry<K,V>>;//键值匹配的Set集合
//keySet方法可以获得Set键值集合，可以通过get(key)获得value值
//entrySet获得的是Set键值对集合

HashMap

1. 存储结构哈希表（数组+链表+红黑树）
2. 使用key和hashcode和equals作为重复

源码分析

1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//初始容量
   static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量
   static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子，当存入的容量要超过75%则要扩容了,达到阈值，进行扩容，扩容后是原来的2倍
   static final int TREEIFY_THRESHOLD = 8;
   static final int UNTREEIFY_THRESHOLD = 6;
   static final int MIN_TREEIFY_CAPACITY = 64;
   //链表长度大于8,且数组长度>=64,链表转换为红黑树,链表小于6时转回链表
   

   TreeMap

   1. 实现了SortedMap接口，可以对key自动排序
   2. 使用时要实现Comparable接口
   3. 可以创建集合时就指定比较规则，通过匿名内部类comparator