跳至主要內容

Map系列概述

God约 3218 字大约 11 分钟

1、HashMap 和 Hashtable 的区别

  1. 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的，因为 Hashtable 内部的方法基本都经过synchronized 修饰；

  2. 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它；

  3. 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。

  4. 初始容量大小和每次扩充容量大小的不同 ： ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小，后面会介绍到为什么是 2 的幂次方。

  5. 底层数据结构： 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 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己的之外，其他方法都是直接调用 HashMap 中的方法。

补充HashSet的实现：HashSet的底层其实就是HashMap，只不过我们HashSet是实现了Set接口并且把数据作为K值，而V值一直使用一个相同的虚值来保存。如源码所示：

public boolean add(E e) {
    return map.put(e, PRESENT)==null;// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
}

由于HashMap的K值本身就不允许重复，并且在HashMap中如果K/V相同时，会用新的V覆盖掉旧的V，然后返回旧的V，那么在HashSet中执行这一句话始终会返回一个false，导致插入失败，这样就保证了数据的不可重复性。

3、HashMap 和 TreeMap 区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 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 就不会让加入操作成功！

注意，在openjdk8中：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) {
...
}

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

hashCode()与 equals() 的相关规定：

  1. 如果两个对象相等，则 hashcode 一定也是相同的

  2. 两个对象相等,对两个 equals() 方法返回 true

  3. 两个对象有相同的 hashcode 值，它们也不一定是相等的

  4. 综上，equals() 方法被覆盖过，则 hashCode() 方法也必须被覆盖

  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

==与 equals 的区别

对于基本类型来说，== 比较的是值是否相等；

对于引用类型来说，== 比较的是两个引用是否指向同一个对象地址（两者在内存中存放的地址（堆内存地址）是否指向同一个地方）；

对于引用类型（包括包装类型）来说，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

5、HashMap 的底层实现原理

JDK1.8 之前

JDK1.8 之前 HashMap 底层数据结构采用的是 数组+链表 **。HashMap 拿到 key 的 hashCode，再经过 扰动函数处理过后得到一个 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖；不相同就通过拉链法（链表头插法）**解决冲突！

所谓扰动函数指的是 HashMap 的 hash 方法。HashMap 的使用自己的hash函数是为了防止一些比较差的 hashCode()计算方法，换句话说使用HashMap扰动函数计算得到的hash值可以有效减少碰撞！

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 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) {
    int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

    h ^= k.hashCode(); // 取hashCode值
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但实现原理一样
     return h & (length-1);  // 取模运算
}

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

Hash 算法本质上就三步：取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算得到存储的位置。

所谓 “拉链法” ：将数组和链表相结合。创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值采用头插法加到链表中！

jdk1.8之前的内部结构-HashMap
jdk1.8之前的内部结构-HashMap

JDK1.8 之后

JDK1.8 中，由 ”数组+链表/红黑树” 组成。当链表过长，则会严重影响 HashMap 的性能，红黑树搜索时间复杂度是 O(logn)，而链表是糟糕的 O(n)。因此，JDK1.8 对数据结构做了进一步的优化，引入了红黑树，链表和红黑树在达到一定条件会进行转换：

  • 当链表长度超过 8，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树 （以减少搜索时间）
  • 当链表长度超过 8， 且 数组的长度超过 64 才会转红黑树 （以减少搜索时间）
jdk1.8之后的内部结构-HashMap
jdk1.8之后的内部结构-HashMap

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

6、ConcurrentHashMap的底层实现原理

JDK1.7 的 ConcurrentHashMap：

  • 底层数据结构：
    • JDK1.7 的底层采用 Segment 数组 + HashEntry 数组 + 链表，即把哈希桶切分成小数组（Segment ），每个小数组由 n 个 HashEntry 数组组成，每个HashEntry代表着一个链表的头结点，链表中每个HashEntry 节点用于存储键值对数据。
  • 实现线程安全的方式（重要）：
    • 在 JDK1.7 的时候，ConcurrentHashMap 对整个桶数组进行了分段(Segment)，每个分段都有各自的锁（分段锁），每把锁只锁对应分段的数据，多线程访问容器里不同分段的数据，就不会存在锁竞争，提高并发访问率
    • 简单理解就是，ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 Segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。
JDK1.7_ConcurrentHashMap
JDK1.7_ConcurrentHashMap

观察ConcurrentHashMap有参构造函数：

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

concurrencyLevel：并行级别、并发数、Segment 数，怎么翻译不重要，理解它才是关键。默认是 16，也就是说 ConcurrentHashMap 默认有 16 个 Segments，所以理论上，这个时候最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。

这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的！

再具体到每个 Segment 内部，其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些。

JDK1.8 的 ConcurrentHashMap：

  • 底层数据结构：
    • JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。
  • 实现线程安全的方式（重要）：
    • JDK1.8 已经抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加低粒度的锁，将锁的级别控制在了更细粒度的哈希桶元素级别，也就是说只需要锁住这个链表头结点（红黑树的根节点），就不会影响其他的哈希桶元素的读写，大大提高了并发度。
Java8_concurrenthashmap
Java8_concurrenthashmap

JDK1.7中，ConcurrentHashMap是通过分段锁机制来实现的，所以其最大并发度受Segment的个数限制。

因此，在JDK1.8中，ConcurrentHashMap的摒弃了这种设计，而是选择了与HashMap类似的数组+链表/红黑树的方式实现，而加锁则采用CAS和synchronized实现。

注意，Node 只能用于链表的情况，红黑树的情况需要使用 TreeBin。

当链表长度超过一定阈值8时将链表（时间复杂度为 O(N)）转换为红黑树（时间复杂度为 O(log(N)）。

MIT Licensed | Copyright © 2024-present God