java集合类学习

一、集合依赖图

一、Collection接口

1.特点

1. collection实现子类可以存放多个元素，每个元素可以是Object
2. 有些实现类可以放重复元素，有些不可以
3. 有些实现类存储元素是有序的，有些是无序的
4. Collection接口没有直接的实现子类，是通过他的子接口Set和List来实现的

2.常用方法

以实现子类ArrayList来演示

add(),

remove()

contains()

size()

isEmpty()

addAll() 将另外Collection的实现类内元素添加入集合

removeAll()

3.遍历方式

3.1 Iterator（迭代器）

1.特点

1. Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。
2. 所有Collection的实现类都有 iterator() 方法

2.执行原理

获取一个迭代器

使用时首先判断： hasNext() 来查看是否有下一元素

然后使用iterator.next()来进行下移，并且此方法还能将下移后的对应元素返回

3.使用

Iterator iterator = list2.iterator();
while (iterator.hasNext()) {
    Object next = iterator.next();
    System.out.printf(next+"");

}

//增强for循环，原理也是使用迭代器
for (Object o : list2) {
    System.out.println(o);
}

4.ArrayList

4.1注意事项

1. 可以存放多个不同类型的值，包括null
2. 是由数组来实现数据存储的
3. 基本等同于Vector，除了ArrayList是线程不安全的（执行效率高），多线程下，不建议使用

4.2底层源码

1.ArrayList中维护了一个Object类型的数组elementData[]

transient Object[] elementData; transient: 表示该属性不会被序列化

2.当创建ArrayList对象时，如果使用无参构造器，则数组初始值为0，第一次添加时，扩容到10

以后满后需要扩容时，大小 = 原大小 + 原大小右移一位（相当于1.5倍）

3.如果使用指定大小的构造器，那么扩容时也直接扩容为1.5倍

5.Vector

4.1注意

1. 内部维护了一个Object[] elementData
2. 是线程安全的，但是效率低

4.2底层源码

1. 当使用无参构造方法时，会调用有参构造，将初始大小设为10
2. 当需要扩容时，判断是否为自定义扩容。如果不是自定义扩容，则将容量扩大到二倍。
3. 最后使用拷贝函数

6.LinkedList

内部维护了firest和last两个Node节点对象

底层结构是双向链表

改查的效率较低

二、Set接口

2.1 介绍

1. 无序（添加和取出的顺序不一样），没有索引
2. 不允许重复添加元素，可以有null
3. 初始添加时，扩容到16，阈值为16*加载因子（0.75） = 12
4. 扩容时扩容到2倍

2.2HashSet

1. 实现了Set接口
2. 实际上是HashMap
3. 可以存null,但只能有一个
4. 不保证元素是有序的，取决于hash后，在确定索引结果

1.add源码

//核心操作putVal
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建 
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理  
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value 
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // 步骤④：判断该链为红黑树 
        // hash值不相等，即key不相等；为红黑树结点
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：该链为链表 
        // 为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    // 结点数量达到阈值，转化为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值与插入元素相等的结点
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 步骤⑥：超过最大容量 就扩容 
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}

解释：add流程

1. 使用构造器时，执行新建一个HashMap对象

2. 执行add方法

3. 执行map的put方法

   1. 计算出hash值为：key.hash = (h = k.hashCode()) ^ (h >>> 16)；（hashCode与自身无符号右移16位做异或）

      因为通常声明map集合时不会指定大小，或者初始化的时候就创建一个容量很大的map对象，所以这个通过容量大小与key值进行hash的算法在开始的时候只会对低位进行计算，虽然容量的2进制高位一开始都是0，但是key的2进制高位通常是有值的，因此先在hash方法中将key的hashCode右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。

4. 执行putVal方法、

   1. 判断table是否为null（为null则扩容到16，阈值为0.75*容量 = 12）
      1. 使用hash进行高效取余计算出应该存在table表中的那个索引位置
         1. 索引位为null,直接存入时，新建一个Node对象，传入三个参数，hash值（为了下次添加时比较hash值），key值（添加的值），value值（一个哨兵变量，占位用，为了set使用hashMap，每个key的value都一样(PRESENT)）,next（null）
         2. 不为null,产生冲突
            1. 判断是否属于同一个对象，或者equals判断相等（将e赋值为当前下标对应的Node）
            2. 判读是否属于红黑树，（属于则 将p强转为TreeNode,调用putTreeVal,将e赋值）
            3. 将当前下表的链表进行for循环
               1. 如果链表中有节点是和将要添加的对象属于同一对象，或者equals判断相等，则break;
               2. 如果循环到了链表尾，则进行添加
                  1. 判断结点数量是否达到阈值（8），到8则转化为红黑树
                     1. 转换之前，判断table数组大小是否小于64或等于null，小于则扩容
                     2. 转化红黑树
      2. 判断e是否为null,不为空返回旧值（添加失败）
   2. 判断++size是否大于阈值，大于则进行扩容
   3. 返回null（添加成功）

高效率取余运算

Java的HashMap源码中用到的(n-1)&hash这样的运算，这是一种高效的求余数的方法

结论：假设被除数是x，对于除数是2ⁿ的取余操作x%2ⁿ，都可以写成x&(2ⁿ-1)，位运算效率高！

举例：259%8=259&7=3

原理：因为对8的取余结果肯定小于8

​ 在二级制中，8=(1000)₂,因此取余结果肯定小于等于7=(0111)₂

​ 因此对于被除数的二进制来说，只需要保证后三位保留下来即可（后三位保留下来肯定小于8）

​ 此时保存下来的结果就是取余结果

​ 259 ： 1 0 0 0 0 0 0 1 1
​ 7 ： 0 0 0 0 0 0 1 1 1

​ 要保存后面的三个数，就需要使用到位运算：（&运算中1&1=1,1&0=0,0&0=0）

​ 此时位运算结果：0 0 0 0 0 0 0 1 1

​ 转换为10进制就等于3！

注意：只有对于除数是2ⁿ，才可以使用此方法进行取余运算

公式： x%2ⁿ == x&(2ⁿ-1)

2.3 LinkedHashSet

1.简介

1. 底层维护的是LinkedHashMap
   1. LinkedHashMap：数组+双向链表
   2. 数组类型：HashMap$Node[]
   3. 添加时，存入的类型为LinkedHashMap$Entry
2. 加入的顺序和取出顺序一致

2.底层

和HashSet一样

2.4TreeSet

1. 底层是TreeMap

2. 当使用无参构造器时，默认是首字母ASCII表

3. 构造时，使用比较器来进行排序、去重

三、Map接口

3.1简介

1. 用于保存具有映射关系的数据
2. k,v可以是任意数据类型
3. key不允许重复，和HashSet一样，当重复时，会覆盖上次的value
4. 常用String作为key
5. 没有实现同步，是线程不安全的

3.2常用方法

HashMap为实现类

1. put(添加<k,v>)
2. get（获取key对应的value）
3. isEmpty()
4. clear(清空)
5. entrySet(返回所有node)
6. ketSet(返回所有key)
7. values（返回所有value）

3.3底层源码

1.entrySet（）方法

public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }

在entrySet中，存放的是Entry<k,v>; transient Set<Map.Entry<K,V>> entrySet = hashMap.entrySet();

EntrySet为HashMap的内部类，在HashMap中，为了方便管理遍历，将Node转换为Entry（因为Node实现了Entry接口，上转型），再将这些Entry存入entrySet中

因此遍历时，需要将entrySet转型为Map.Entry接口

3.4Hashtable

1.简介

1. 存放的元素都是键值对
2. 内部维护了一个Hashtavle$Entry[] table
3. 键和值都不能为null，否则会抛出空指针异常
4. 是线程安全的，hashMap是线程不安全的，扩容时原容量左移一位再加一
5. 初始大小大小为11，临界值为11*0.75 = 8

3.5Properties

1.介绍

1. 继承了Hashtable
2. 存放的是键值对，并且都不可以为null
3. 一般用来存储读取properties文件中的对象

3.6TreeMap

1. 通过传入comparator接口的实现类可以实现排序
2. 添加元素时调用put方法，将第一个元素直接加入。后续加入时按照传入的比较器规则进行添加

四、如何选择集合实现类

一、先判断存储的类型

二、如果是单列的：Collection接口

​ 2.1 允许重复：List

​ 增删多：LinkedList(底层维护了一个双向链表)

​ 改查多：ArrayList(底层维护了Object类型的可变数组)

​ 2.2不允许重复：Set

​ 无序： HashSet（底层HashMap,维护了一个哈希表，即（数组+链表+红黑树））

​ 排序：TreeSet

​ 插入和取出顺序一致：LinkedHashSet,维护了数组+双向链表

三、如果是双列的（键值对）：Map

​ 健无序：HashMap（底层哈希表, jdk7:数组+链表，jdk8:数组+链表+红黑树）

​ 健排序:TreeMap

​ 插入和取出顺序一致:LinkedHashMap

​ 读取文件：Properties

五、Collectios工具类

Collections 类是 Java 提供的一个操作 Set、List 和 Map 等集合的工具类。Collections 类提供了许多操作集合的静态方法，借助这些静态方法可以实现集合元素的排序、查找替换和复制等操作。

5.1排序（正向和逆向）

Collections 提供了如下方法用于对 List 集合元素进行排序。

• void reverse(List list)：对指定 List 集合元素进行逆向排序。
• void shuffle(List list)：对 List 集合元素进行随机排序（shuffle 方法模拟了“洗牌”动作）。
• void sort(List list)：根据元素的自然顺序对指定 List 集合的元素按升序进行排序。
• void sort(List list, Comparator c)：根据指定 Comparator 产生的顺序对 List 集合元素进行排序。
• void swap(List list, int i, int j)：将指定 List 集合中的 i 处元素和 j 处元素进行交换。
• void rotate(List list, int distance)：当 distance 为正数时，将 list 集合的后 distance 个元素“整体”移到前面；当 distance 为负数时，将 list 集合的前 distance 个元素“整体”移到后面。

该方法不会改变集合的长度。

5.2查找、替换操作

Collections 还提供了如下常用的用于查找、替换集合元素的方法。

• int binarySearch(List list, Object key)：使用二分搜索法搜索指定的 List 集合，以获得指定对象在 List 集合中的索引。如果要使该方法可以正常工作，则必须保证 List 中的元素已经处于有序状态。
• Object max(Collection coll)：根据元素的自然顺序，返回给定集合中的最大元素。
• Object max(Collection coll, Comparator comp)：根据 Comparator 指定的顺序，返回给定集合中的最大元素。
• Object min(Collection coll)：根据元素的自然顺序，返回给定集合中的最小元素。
• Object min(Collection coll, Comparator comp)：根据 Comparator 指定的顺序，返回给定集合中的最小元素。
• void fill(List list, Object obj)：使用指定元素 obj 替换指定 List 集合中的所有元素。
• int frequency(Collection c, Object o)：返回指定集合中指定元素的出现次数。
• int indexOfSubList(List source, List target)：返回子 List 对象在父 List 对象中第一次出现的位置索引；如果父 List 中没有出现这样的子 List，则返回 -1。
• int lastIndexOfSubList(List source, List target)：返回子 List 对象在父 List 对象中最后一次出现的位置索引；如果父 List 中没有岀现这样的子 List，则返回 -1。
• boolean replaceAll(List list, Object oldVal, Object newVal)：使用一个新值 newVal 替换 List 对象的所有旧值 oldVal。

5.3复制

Collections 类的 copy() 静态方法用于将指定集合中的所有元素复制到另一个集合中。执行 copy() 方法后，目标集合中每个已复制元素的索引将等同于源集合中该元素的索引。

copy() 方法的语法格式如下：

void copy(List <? super T> dest,List<? extends T> src)

其中，dest 表示目标集合对象，src 表示源集合对象。

注意：目标集合的长度至少和源集合的长度相同，如果目标集合的长度更长，则不影响目标集合中的其余元素，假如dest集合元素有5个，src集合中元素有3个，复制后dest中前三个被覆盖。

后两个不改变，如果目标集合长度不够而无法包含整个源集合元素，

程序将抛出 IndexOutOfBoundsException 异常