Java基础知识学习08

野性酷女 2024-03-23 15:18 14阅读 0赞

***Map接口***

***1、HashMap 和 Hashtable 的区别？***

*  线程是否安全： `HashMap` 是**非线程安全**的，`Hashtable` 是**线程安全**的,因为 `Hashtable` 内部的方法基本都经过`synchronized` 修饰。（如果你要保证线程安全的话就使用 `ConcurrentHashMap` 吧！）；
 *  效率： 因为线程安全的问题，`HashMap` 要比 `Hashtable` 效率高一点。另外，`Hashtable` **基本被淘汰**，不要在代码中使用它；
 *  对 **Null key** 和 **Null value** 的支持： `HashMap` 可以存储 `null` 的 `key` 和 `value`，但 `null` **作为键只能有一个**，`null` **作为值可以有多个**；`Hashtable` 不允许有 `null` 键和 `null` 值，否则会抛出 `NullPointerException`。
 *  初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，`Hashtable` **默认的初始大小为 11**，之后每次扩充，容量变为原来的 **2n+1**。`HashMap` 默认的**初始化大小为 16**。之后每次扩充，容量变为原来的 **2 倍**。② 创建时如果给定了容量初始值，那么 `Hashtable` 会**直接使用你给定的大小**，而 `HashMap` 会将其**扩充为 2 的幂次方大小**（`HashMap` 中的`tableSizeFor()`方法保证）。也就是说 `HashMap` 总是使用 **2 的幂作为哈希表的大小**。
 *  底层数据结构： JDK1.8 以后的 `HashMap` 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 **8**）时，将链表转化为**红黑树**（将链表转换成红黑树前会判断，**如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树**），以减少搜索时间。`Hashtable` 没有这样的机制。

HashMap 中带有初始容量的构造函数：

public HashMap(int initialCapacity, float loadFactor) {
        
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
     public HashMap(int initialCapacity) {
        
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

下面这个方法保证了 HashMap 总是使用 2 的幂作为哈希表的大小。

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

***2、HashMap 和 HashSet 区别？***

`HashSet` 底层就是基于 `HashMap` 实现的。（`HashSet` 的源码非常非常少，因为除了 `clone()、writeObject()、readObject()`是 `HashSet` 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。  
![在这里插入图片描述][b192bacb269e472a89b4a2150d1cac5d.png_pic_center]  
***3、HashMap 和 TreeMap 区别？***

`TreeMap` 和`HashMap` 都继承自`AbstractMap` ，但是需要注意的是`TreeMap`它还实现了`NavigableMap`接口和`SortedMap` 接口。  
![在这里插入图片描述][d16d47b6a2ce454ca2902701917c7785.png]

实现 `NavigableMap` 接口让 `TreeMap` 有了对集合内元素的搜索的能力。

实现`SortedMap`接口让 `TreeMap` 有了对集合中的元素根据键排序的能力。默认是按 key 的**升序排序**，不过我们也可以**指定排序的比较器**。示例代码如下：

/**
     * @author shuang.kou
     * @createTime 2020年06月15日 17:02:00
     */
    public class Person {
        
        private Integer age;
    
        public Person(Integer age) {
        
            this.age = age;
        }
    
        public Integer getAge() {
        
            return age;
        }
    
    
        public static void main(String[] args) {
        
            TreeMap<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
        
                @Override
                public int compare(Person person1, Person person2) {
        
                    int num = person1.getAge() - person2.getAge();
                    return Integer.compare(num, 0);
                }
            });
            treeMap.put(new Person(3), "person1");
            treeMap.put(new Person(18), "person2");
            treeMap.put(new Person(35), "person3");
            treeMap.put(new Person(16), "person4");
            treeMap.entrySet().stream().forEach(personStringEntry -> {
        
                System.out.println(personStringEntry.getValue());
            });
        }
    }

输出:

person1
    person4
    person2
    person3

可以看出，`TreeMap` 中的元素已经是按照 `Person` 的 age 字段的升序来排列了。

上面，我们是通过**传入匿名内部类的方式**实现的，你可以将代码替换成 Lambda 表达式实现的方式：

TreeMap<Person, String> treeMap = new TreeMap<>((person1, person2) -> {
        
      int num = person1.getAge() - person2.getAge();
      return Integer.compare(num, 0);
    });

综上，相比于`HashMap`来说 `TreeMap` 主要**多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力**。

***4、HashSet 如何检查重复?***

当把对象加入`HashSet`时，`HashSet` 会先计算对象的`hashcode`值来判断对象加入的位置，同时也会与其他加入的对象的 `hashcode` 值作比较，如果没有相符的 `hashcode`，`HashSet` 会假设对象没有重复出现。

但是如果发现有相同 `hashcode` 值的对象，这时会调用`equals()`方法来检查 `hashcode` 相等的对象**是否真的相同**。**如果两者相同，`HashSet` 就不会让加入操作成功**。

在 JDK1.8 中，`HashSet`的`add()`方法只是简单的调用了`HashMap`的`put()`方法，并且判断了一下返回值以确保是否有重复元素。直接看一下`HashSet`中的源码：

// Returns: true if this set did not already contain the specified element
    // 返回值：当 set 中没有包含 add 的元素时返回真
    public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
    }

而在`HashMap`的`putVal()`方法中也能看到如下说明：

// Returns : previous value, or null if none
    // 返回值：如果插入位置没有元素返回null，否则返回上一个元素
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
    ...
    }

也就是说，在 JDK1.8 中，实际上无论`HashSet`中是否已经存在了某元素，`HashSet`都会**直接插入**，只是会在**add()方法的返回值处告诉我们插入前是否存在相同元素**。

***5、HashMap 的底层实现？***

JDK1.8 之前

JDK1.8 之前 `HashMap` 底层是 **数组和链表** 结合在一起使用也就是 **链表散列**。`HashMap` 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 `HashMap` 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法， 换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加简化，但是原理不变。

static final int hash(Object key) {
        
          int h;
          // key.hashCode()：返回散列值也就是hashcode
          // ^ ：按位异或
          // >>>:无符号右移，忽略符号位，空位都以0补齐
          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {
        
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
    
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

相比于 JDK1.8 的 hash 方法 ，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “`拉链法`” 就是：**将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可**。

***JDK1.8 之后：***

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

`TreeMap`、`TreeSet` 以及 JDK1.8 之后的 `HashMap` 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷，因为**二叉查找树在某些情况下会退化成一个线性结构**。

结合源码分析一下 `HashMap` 链表到红黑树的转换。

*  1、putVal 方法中执行链表转红黑树的判断逻辑。

链表的长度大于 8 的时候，就执行 `treeifyBin` （转换红黑树）的逻辑。

// 遍历链表
    for (int binCount = 0; ; ++binCount) {
        
        // 遍历到链表最后一个节点
        if ((e = p.next) == null) {
        
            p.next = newNode(hash, key, value, null);
            // 如果链表元素个数大于等于TREEIFY_THRESHOLD（8）
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                // 红黑树转换（并不会直接转换成红黑树）
                treeifyBin(tab, hash);
            break;
        }
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        p = e;
    }

*  2、treeifyBin 方法中判断是否真的转换为红黑树。

final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        // 判断当前数组的长度是否小于 64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            // 如果当前数组的长度小于 64，那么会选择先进行数组扩容
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
        
            // 否则才将列表转换为红黑树
    
            TreeNode<K,V> hd = null, tl = null;
            do {
        
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
        
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

将链表转换成红黑树前会判断，如果**当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树**。

***6、HashMap 的长度为什么是 2 的幂次方？***

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做**对数组的长度取模运算**，得到的**余数才能用来要存放的位置也就是对应的数组下标**。这个数组下标的计算方法是`“ (n - 1) & hash”`。（n 代表数组长度）。这也就解释了 HashMap 的长度为什么是 2 的幂次方。

这个算法应该如何设计呢？首先可能会想到采用%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。

***7、HashMap 多线程操作导致死循环问题？***

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。

***HashMap 有哪几种常见的遍历方式?***

[点击这里看细节！！！！][Link 1]

![在这里插入图片描述][12c649392c9e4eea8b005b3ce4748a90.png_pic_center]  
HashMap 遍历从大的方向来说，可分为以下 4 类：

*  迭代器（Iterator）方式遍历；
 *  For Each 方式遍历；
 *  Lambda 表达式遍历（JDK 1.8+）;
 *  Streams API 遍历（JDK 1.8+）。

但每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为以下 7 种：

*  使用迭代器（Iterator）EntrySet 的方式进行遍历；
 *  使用迭代器（Iterator）KeySet 的方式进行遍历；
 *  使用 For Each EntrySet 的方式进行遍历；
 *  使用 For Each KeySet 的方式进行遍历；
 *  使用 Lambda 表达式的方式进行遍历；
 *  使用 Streams API 单线程的方式进行遍历；
 *  使用 Streams API 多线程的方式进行遍历。

![在这里插入图片描述][89419cc582044e9c85bdaa0b69305dd6.png_pic_center]

其中 Units 为 ns/op 意思是执行完成时间（单位为纳秒），而 Score 列为平均执行时间， ± 符号表示误差。从以上结果可以看出，两个 `entrySet` 的性能相近，并且**执行速度最快**，接下来是 `stream` ，然后是两个 `keySet`，**性能最差**的是 `KeySet` 。

从以上结果可以看出 `entrySet` 的性能比 `keySet` 的**性能高出了一倍之多**，因此我们应该尽量使用 `entrySet` 来实现 `Map` 集合的遍历。

**性能分析：**

`EntrySet` 之所以比 `KeySet` 的性能高是因为，`KeySet` 在循环时使用了 `map.get(key)`，而 `map.get(key)` 相当于又遍历了一遍 `Map` 集合去查询 `key` 所对应的值。为什么要用“又”这个词？那是因为在使用`迭代器`或者 `for` 循环时，其实已经遍历了一遍 Map 集合了，因此再使用 `map.get(key)` 查询时，**相当于遍历了两遍**。

而 `EntrySet` 只遍历了一遍 `Map` 集合，之后通过代码“`Entry<Integer, String> entry = iterator.next()`”**把对象的 key 和 value 值都放入到了 Entry 对象中**，因此再获取 key 和 value 值时就**无需再遍历 Map 集合**，只需要**从 Entry 对象中取值**就可以了。

所以，`EntrySet` 的性能比 `KeySet` 的性能高出了一倍，因为 `KeySet` 相当于**循环了两遍** `Map` 集合，而 `EntrySet` 只循环了一遍。

***安全性测试：***

不能在遍历中使用集合 `map.remove()` 来删除数据，这是**非安全**的操作方式，但我们可以使用**迭代器**的 `iterator.remove()` 的方法来删除数据，这是**安全**的删除集合的方式。同样的我们也可以使用 `Lambda` 中的 `removeIf` 来提前删除数据，或者是使用 `Stream` 中的 `filter` 过滤掉要删除的数据进行循环，这样都是**安全**的，当然我们也可以在 `for` **循环前删除数据再遍历**也是线程安全的。

总结：`HashMap` 4 种遍历方式：**迭代器、for、lambda、stream**，以及具体的 7 种遍历方法，综合性能和安全性来看，我们应该尽量使用**迭代器（Iterator）来遍历 `EntrySet` 的遍历方式来操作 `Map` 集合，这样就会既安全又高效**了。

[b192bacb269e472a89b4a2150d1cac5d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/e1ab3c2feefd48ea8fa7e67f0186c7b7.png
[d16d47b6a2ce454ca2902701917c7785.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/6c9a11a4ae314b6d92ba2d65b77ca0c4.png
[Link 1]: https://mp.weixin.qq.com/s/zQBN3UvJDhRTKP6SzcZFKw
[12c649392c9e4eea8b005b3ce4748a90.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/fa4a215f943b48bba1552be9aade26db.png
[89419cc582044e9c85bdaa0b69305dd6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/40a6e439aa694585a7e6f2f929310a39.png