Java 集合基础知识

谁借莪１个温暖的怀抱￠ 2023-03-02 13:07 110阅读 0赞

### Java 集合基础知识 ###

*  Java 集合基础知识
 *   *  ArrayList
     *  LinkedList
     *  HashMap
     *   *  如何计算bucket下标
         *   *  map的几种遍历方法
             *  方式1：Iterator迭代器
             *  方式2：最常见的使用方式，可同时得到key、value值
             *  方式3：使用foreach方式（JDK1.8才有）
             *  方式4：通过key的set集合遍历
     *  JDK8中的HashMap底层实现
 *  1. 快速失败和安全失败是什么

# Java 集合基础知识 #

https://juejin.im/post/5de85e05f265da33b50727f6 参考链接。

## ArrayList ##

*  *ArrayList*实现了*List*接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入`null`元素，底层通过**数组实现**。
 *  每个*ArrayList*都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。
 *  当向容器中添加元素时，如果容量不足，**容器会自动增大底层数组的大小**。数组进行扩容时，会将老数组中的元素重新**拷贝**一份到新的数组中，每次数组容量的增长大约是其原容量的**1.5倍**。这种操作的代价是很高的，因此在实际使用时，我们应该**尽量避免数组容量的扩张**。
 *  size(), isEmpty(), get(), set()方法均能在**常数时间**内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
 *  为追求效率，ArrayList没有实现同步（**synchronized**），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

## LinkedList ##

**LinkedList**同时实现了**list**接口和**Deque**接口，也就是说它既可以看作一个**顺序容器**，又可以看作**一个队列（Queue）**，同时又可以看作**一个栈（Stack）**。这样看来，LinkedList简直就是个全能冠军。当你需要使用栈或者队列时，可以考虑使用LinkedList，一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（它是个接口名字）。**关于栈或队列，现在的首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）有着更好的性能**。

LinkedList底层**通过双向链表实现**，双向链表的每个节点用内部类Node表示。LinkedList通过`first`和`last`引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候`first`和`last`都指向`null`

## HashMap ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center]

**part1：特殊key值处理，key为null；**

**part2：计算table中目标bucket的下标；**

**part3：指定目标bucket，遍历Entry结点链表，若找到key相同的Entry结点，则做替换；**

**part4：若未找到目标Entry结点，则新增一个Entry结点。**

\*\*`put()`\*\*方法是有返回值的，场景区分如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 1]

*  场景1：若执行put操作前，key已经存在，那么在执行put操作时，会使用本次的新value值来覆盖前一次的旧value值，返回的就是旧value值；
 *  场景2：若key不存在，则返回null值。

特殊key值，指的就是key为null。 先说结论：  
**a)** HashMap中，是允许key、value都为null的，且key为null只存一份，多次存储会将旧value值覆盖；  
**b)** key为null的存储位置，都统一放在下标为**0**的bucket，即：table\[0\]的位置；

扩容

**a)** 扩容后大小是扩容前的2倍；

**b)** 数据搬迁，从旧table迁到扩容后的新table。 为避免碰撞过多，先决策是否需要对每个Entry链表结点重新hash，然后根据hash值计算得到bucket下标，然后使用头插法做结点迁移。

### 如何计算bucket下标 ###

1.  hash值的计算

/**
         * 分析1：hash(key)
         * 作用：计算传入数据的哈希码（哈希值、Hash值）
         * 该函数在JDK 1.7 和 1.8 中的实现不同，但原理一样 = 扰动函数 = 使得根据key生成的哈希码（hash值）分布更加均匀、更具备随机性，避免出现hash值冲突（即指不同key但生成同1个hash值）
         * JDK 1.7 做了9次扰动处理 = 4次位运算 + 5次异或运算
         * JDK 1.8 简化了扰动函数 = 只做了2次扰动 = 1次位运算 + 1次异或运算
         */
    
          // JDK 1.7实现：将 键key 转换成 哈希码（hash值）操作  = 使用hashCode() + 4次位运算 + 5次异或运算（9次扰动）
          static final int hash(int h) {
            h ^= k.hashCode(); 
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
         }
    
          // JDK 1.8实现：将 键key 转换成 哈希码（hash值）操作 = 使用hashCode() + 1次位运算 + 1次异或运算（2次扰动）
          // 1. 取hashCode值： h = key.hashCode() 
          // 2. 高位参与低位的运算：h ^ (h >>> 16)  
          static final int hash(Object key) {
               int h;
                return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
                // a. 当key = null时，hash值 = 0，所以HashMap的key 可为null      
                // 注：对比HashTable，HashTable对key直接hashCode（），若key为null时，会抛出异常，所以HashTable的key不可为null
                // b. 当key ≠ null时，则通过先计算出 key的 hashCode()（记为h），然后 对哈希码进行 扰动处理： 按位 异或（^） 哈希码自身右移16位后的二进制
         }
    
       /**
         * 计算存储位置的函数分析：indexFor(hash, table.length)
         * 注：该函数仅存在于JDK 1.7 ，JDK 1.8中实际上无该函数（直接用1条语句判断写出），但原理相同
         * 为了方便讲解，故提前到此讲解
         */
         static int indexFor(int h, int length) {  
              return h & (length-1); 
              // 将对哈希码扰动处理后的结果 与运算(&) （数组长度-1），最终得到存储在数组table的位置（即数组下标、索引）
              }

首先得有key的hash值，就是一个整数，int类型，其计算方式使用了一种可尽量减少碰撞的算式（高位运算），具体计算流程如上代码

问题1：为什么不直接采用经过hashCode（）处理的哈希码作为存储数组table的下标位置？  
结论：容易出现 哈希码 与 数组大小范围不匹配的情况，即 计算出来的哈希码可能 不在数组大小范围内，从而导致无法匹配存储位置，所以为了解决 “哈希码与数组大小范围不匹配” 的问题，HashMap给出了解决方案：**哈希码 与运算（&） （数组长度-1）**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 2]  
问题二、为什么采用 哈希码 与运算(&) （数组长度-1） 计算数组下标？  
根据HashMap的容量大小（数组长度），按需取 哈希码一定数量的低位 作为存储的数组下标位置，从而 解决 “哈希码与数组大小范围不匹配” 的问题。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 3]  
问题3：为什么在计算数组下标前，需对哈希码进行二次处理：扰动处理？  
结论：加大哈希码低位的随机性，使得分布更均匀，从而提高对应数组存储下标位置的随机性 & 均匀性，最终减少Hash冲突  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 4]

1.  取模运算

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

计算相当简洁：将table的容量与hash值做“**与**”运算，得到哈希table的bucket下标。

在文档开头，给出了HashMap类中的各个域变量。其中，哈希table的初始大小默认设置为16，为2的次幂数。后面在扩容时，都是以2的倍数来扩容。为什么非要将哈希table的大小控制为2的次幂数？

**原因1**：降低发生碰撞的概率，使散列更均匀。根据key的hash值计算bucket的下标位置时，使用“与”运算公式：h & (length-1)，当哈希表长度为2的次幂时，等同于使用表长度对hash值取模（不信大家可以自己演算一下），散列更均匀；  
**原因2**：表的长度为2的次幂，那么(length-1)的二进制最后一位一定是1，在对hash值做“与”运算时，最后一位就可能为1，也可能为0，换句话说，取模的结果既有偶数，又有奇数。设想若(length-1)为偶数，那么“与”运算后的值只能是0，奇数下标的bucket就永远散列不到，会浪费一半的空间。  
**原因3**： 提高运算效率

#### map的几种遍历方法 ####

#### 方式1：Iterator迭代器 ####

Iterator<Entry<String, Integer>> iterator = testMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Entry<String, Integer> next = iterator.next();
        System.out.println(next.getKey() + ":" + next.getValue());
    }

逐个获取哈希table中的每个bucket中的每个Entry结点，后面会详细介绍。

#### 方式2：最常见的使用方式，可同时得到key、value值 ####

// 方式一
    for (Map.Entry<String, Integer> entry : testMap.entrySet()) {
        System.out.println(entry.getKey() + ":" + entry.getValue());

这种方式是一个语法糖，我们可通过反编译命令javap，或通过IDE来查下编译之后的语句：

Iterator var2 = testMap.entrySet().iterator();
    while(var2.hasNext()) {
        Entry<String, Integer> entry = (Entry)var2.next();
        System.out.println((String)entry.getKey() + ":" + entry.getValue());
    }
    复制代码

其底层还是使用的是Iterator功能。

#### 方式3：使用foreach方式（JDK1.8才有） ####

testMap.forEach((key, value) -> {
        System.out.println(key + ":" + value);
    });

这是一种Lambda表达式。foreach也是一个语法糖，其内部是使用了**方式二**的处理方式，Map的foreach方法实现如下：

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dMLBCTiF-1595994935387)(https://raw.githubusercontent.com/zhaozhen197/my\_markdown\_img/master/1)\]

#### 方式4：通过key的set集合遍历 ####

Iterator<String> keyIterator = testMap.keySet().iterator();
    while (keyIterator.hasNext()) {
        String key = keyIterator.next();
        System.out.println(key + ":" + testMap.get(key));
    }

这种也是Iterator的方式，不过是通过Set类的iterator方式。

综合以上，在遍历Map时，从性能方面考虑，若需同时使用key和value，推荐使用**方式1**或**方式2**，若单纯只是使用key，推荐使用**方式4**。任何情况下都不推荐使用**方式3**，因为会新增二次查询（通过key再一次在Map中查找value）。

## JDK8中的HashMap底层实现 ##

ashMap在JDK8中做链表结构做了优化（但仍然线程不安全），在一定条件下将链表转为红黑树，提升查询效率。

# 1. 快速失败和安全失败是什么 #

HashMap、ArrayList 这些集合类，这些在 java.util 包的集合类就都是快速失败的；而 java.util.concurrent 包下的类都是安全失败，比如：ConcurrentHashMap。

在使用迭代器对集合对象进行遍历的时候，如果 A 线程正在对集合进行遍历，此时 B 线程对集合进行修改（增加、删除、修改），或者 A 线程在遍历过程中对集合进行修改，都会导致 A 线程抛出 ConcurrentModificationException 异常。

原因是迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变 modCount 的值。每当迭代器使用 hashNext()/next() 遍历下一个元素之前，都会检测 modCount 变量是否为 expectedModCount 值，是的话就返回遍历；否则抛出异常，终止遍历。

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，故不会抛 ConcurrentModificationException 异常

变量\*\*`modCount`**，记录了map新增/删除k-v对，或者内部结构做了调整的次数，其主要作用，是对Map的**`iterator()`**操作做一致性校验，如果在iterator操作的过程中，map的数值有修改，直接抛出**`ConcurrentModificationException`\*\*异常。

HashEntry对象几乎是不可变的(只能改变Value的值)，因为HashEntry中的key、hash和next指针都是final的。这意味着，我们不能把节点添加到链表的中间和尾部，也不能在链表的中间和尾部删除节点。这个特性可以保证：在访问某个节点时，这个节点之后的链接不会被改变，这个特性可以大大降低处理链表时的复杂性。与此同时，由于HashEntry类的value字段被声明是Volatile的，因此Java的内存模型就可以保证：某个写线程对value字段的写入马上就可以被后续的某个读线程看到。此外，由于在ConcurrentHashMap中不允许用null作为键和值，所以当读线程读到某个HashEntry的value为null时，便知道产生了冲突 —— 发生了重排序现象，此时便会加锁重新读入这个value值。这些特性互相配合，使得读线程即使在不加锁状态下，也能正确访问 ConcurrentHashMap。总的来说，ConcurrentHashMap读操作不需要加锁的奥秘在于以下三点：

用HashEntery对象的不变性来降低读操作对加锁的需求；

用Volatile变量协调读写线程间的内存可见性；

若读时发生指令重排序现象，则加锁重读；

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center]: /images/20230208/54843377c12e484e8067a91c7333a757.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230208/092aa7d3017143b5972201c5b267c037.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230208/6699c132884a4cc6ab73fb73f18bd466.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230208/a8d5b292e4474dc98077a67be8a1ce3d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9fX3poZW4_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20230208/9af639fe38ef4e14aae3c9ca59fd975c.png