HashMap、HashTable、ConcurrentHashMap、HashSet底层原理

2024-02-22 14:04:22

文章目录

1、哈希表

哈希表（hash table）也叫散列表，是一种非常重要的数据结构，我们先来看一下其他数据结构的特点。

数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

我们可以发现，数组和链表几乎是两个极端，一个查找效率高，一个插入删除效率高，那么将两者的优点进行融合，得到的是一个存放链表的数组，这种数组和链表的结合体，叫散列表或哈希表。

在哈希表中进行添加，删除，查找等操作，性能都非常高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，那么是如何做到的呢？首先，哈希表的主干为数组，例如我们要增加或查找某个元素，我们可以将当前元素通过某个函数映射到数组中的某个位置，通过数组下标直接定位即可。这个函数被称为哈希函数。
哈希函数的设计至关重要，好的哈希函数会尽可能地保证散列的地址分布均匀，但是再好的哈希函数也会出现冲突的情况，比如我们的两个元素通过哈希函数得到同一个存储地址，那么该如何解决呢？哈希冲突的解决方案有很多种，而HashMap采用了链地址法，就是数组+链表的方式，所有通过哈希函数得到同一地址的元素，将其加在对应的链表上，就构成了HashMap。

2、HashMap

2.1 HashMap的特点

HashMap是一个散列桶（数组和链表），它存储的内容是键值对(key-value)，可以接受null键和值，而Hashtable的key与value均不能为null
HashMap是非synchronized，所以HashMap很快
初始size为16，当Map中元素总数超过Entry数组的75%，触发扩容操作，扩容方式为newsize = oldsize*2（size一定为2的n次幂），扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
插入元素后才判断该不该扩容，有可能无效扩容（插入后如果扩容，如果没有再次插入，就会产生无效扩容）
计算索引的方法：index = hash & (tab.length – 1)
将新元素加到链表头部（JDK1.8引入了红黑树）
在HashMap中，null可以作为键，这样的键只有一个，但可以有一个或多个键所对应的值为null。当get(key)方法返回null值时，即可以表示HashMap中没有该key，也可以表示该key所对应的value为null，因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个key，应该用containsKey()方法来判断

2.2 HashpMap实现原理

HashMap的主干是一个Node数组。Node是HashMap的基本组成单元，每一个Node包含一个key-value键值对：

//HashMap的主干数组，可以看到就是一个Node数组，初始值为空数组，主干数组的长度一定是2的次幂
transient Node<K,V>[] table;

Node的内部结构：

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
        final K key;
        V value;
        Node<K,V> next;//存储指向下一个Entry的引用，单链表结构

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

2.3 HashMap ，HashTable 区别

默认容量不同
计算索引的方法不同
扩容方法不同
线程安全性不同
效率不同，HashTable慢，因为加锁

3、HashTable

3.1 HashTable的特点

底层数组+链表实现，无论key还是value都不能为null
在修改内部共享数据时，使用synchronized锁住整个HashTable，保证线程安全，但是效率低，ConcurrentHashMap做了相关优化
初始size为11，当Map中元素总数超过Entry数组的75%，扩容方式为newsize = olesize*2+1，扩容针对整个Map，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
计算索引的方法：index = (hash & 0x7FFFFFFF) % tab.length
将新元素加到链表头部

4、ConcurrentHashMap

4.1 ConcurrentHashMap的特点

底层采用分段的数组+链表实现
ConcurrentHashMap使用了锁分段技术来保证线程安全，通过把整个Map分为N个Segment，默认将整个表分为16个segment，诸如get、put、remove等常用操作只锁住当前需要用到的segment，这样，原来只能一个线程进入，现在却能同时有16个写线程执行，并发性能的提升是显而易见的。(读操作不加锁，由于HashEntry的value变量是 volatile的，也能保证读取到最新的值)

锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

Hashtable的synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
扩容：段内扩容（段内元素超过该段对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入前检测需不需要扩容，有效避免无效扩容

5、HashSet

5.1 HashSet的特点

HashSet内部基于HashMap来实现的，底层采用HashMap来保存元素，HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个private static final Object PRESENT = new Object();
HashSet跟HashMap一样，都是一个存放链表的数组，这种数组和链表的结合体，也叫散列表、哈希表。
HashSet集合里的元素无序且不可重复

5.2 HashMap与HashSet的区别

一、HahMap存储对象的过程如下
1、对HahMap的Key调用hashCode()方法，返回int值，即对应的hashCode；
2、把此hashCode作为哈希表的索引，查找哈希表的相应位置，若当前位置内容为NULL，则把hashMap的Key、Value包装成Entry数组，放入当前位置；
3、若当前位置内容不为空，则继续查找当前索引处存放的链表，利用equals方法，找到Key相同的Entry数组，则用当前Value去替换旧的Value；
4、若未找到与当前Key值相同的对象，则把当前位置的链表后移（Entry数组持有一个指向下一个元素的引用），把新的Entry数组放到链表表头；

二、HashSet存储对象的过程
往HashSet添加元素的时候，HashSet会先调用元素的hashCode方法得到元素的哈希值，然后通过元素的哈希值经过移位等运算，就可以算出该元素在哈希表中的存储位置。

情况1：如果算出元素存储的位置目前没有任何元素存储，那么该元素可以直接存储到该位置上。

情况2：如果算出该元素的存储位置目前已经存在有其他的元素了，那么会调用该元素的equals方法与该位置的元素再比较一次，如果equals返回的是true，那么该元素与这个位置上的元素就视为重复元素，不允许添加，如果equals方法返回的是false，那么该元素运行添加。

参考：https://blog.csdn.net/c99463904/article/details/77619826
参考：https://mp.weixin.qq.com/s/DTr0vHtSk9n_QF7vfXZ7qQ
参考：https://blog.csdn.net/chen213wb/article/details/84647179

码农公寓