HashMap的知识点整理

API截图:在线版https://blog.fondme.cn/apidoc/jdk-1.8-google/

构造方法摘要

Constructor and Description

HashMap()构造一个空的 HashMap ,默认初始容量(16)和默认负载系数(0.75)。

HashMap(int initialCapacity)构造一个空的 HashMap具有指定的初始容量和默认负载因子(0.75)。

HashMap(int initialCapacity, float loadFactor)构造一个空的 HashMap具有指定的初始容量和负载因子。

HashMap(Map<? extends K,? extends V> m)构造一个新的 HashMap与指定的相同的映射 Map 。

我们看源码:

/**
 * Hash table based implementation of the <tt>Map</tt> interface.  This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 */

哈希表是基于 Map 接口的实现的,它允许 null 值和

null 键,它不是线程同步的,同时也不保证有序

HashMap 的大致结构如下图所示,其中哈希表是一个数组,我们经常把数组中的每一个节点称为一个桶,哈希表中的每个节点都用来存储一个键值对。在插入元素时,

如果发生冲突(即多个键值对映射到同一个桶上)的话,就会通过链表的形式来解

决冲突。因为一个桶上可能存在多个键值对,所以在查找的时候,会先通过 key 的

哈希值先定位到桶,再遍历桶上的所有键值对,找出 key 相等的键值对,从而来获

取 value。

//默认的初始容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大的容量上限为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的负载因子为 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//变成树型结构的临界值为 8
static final int TREEIFY_THRESHOLD = 8;
//恢复链式结构的临界值为 6
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表
transient Node<K,V>[] table;
//哈希表中键值对的个数
transient int size;
//哈希表被修改的次数
transient int modCount;
//它是通过 capacity*load factor 计算出来的,当 size 到达这个值时,
就会进行扩容操作
int threshold;
//负载因子
final float loadFactor;
//当哈希表的大小超过这个阈值,才会把链式结构转化成树型结构,否则仅采
取扩容来尝试减少冲突
static final int MIN_TREEIFY_CAPACITY = 64;

构造方法

关于put方法如果超过最大容量是1<<30,按常理并不会放入超过此数值,但如果极限值超过这个值,就将threshold修改为Integer.MAX_VALUE(此时的桶大小已经是2的31次方了,表名已经不进行扩容了)

关于负载因子为 0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

他能不能超过0.75,或者到1再扩容呢?

明显如果到1,现插入节点的链表会极限大,但其他位置可能为空,造成空间复杂度为o(n)

那么如果小于0.75,就会频繁扩容,造成空间浪费,所以计算后到达元素个数的0.75进行扩容

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            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;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

put 方法比较复杂,实现步骤大致如下:

1、先通过 hash 值计算出 key 映射到哪个桶。

2、如果桶上没有碰撞冲突,则直接插入。

3、如果出现碰撞冲突了,则需要处理冲突:

(1)如果该桶使用红黑树处理冲突,则调用红黑树的方法插入。

(2)否则采用传统的链式方法插入。如果链的长度到达临界值,则把链转变为红

黑树。

4、如果桶中存在重复的键,则为该键替换新值。

5、如果 size 大于阈值(8),则进行扩容

根据hash算法得到hash码值,也就是数组的索引值,在判断是否有对象,如果没有则放入

如果有则先通过equals比较两个对象的内容,如果内容一样,则覆盖value,

如果内容不一样,形成链表,1.7后加的放前面,这种情况叫做hash碰撞,这种情况我们是尽可能避免的,如果这里的元素过多的话,插入效率过低,为了避免的话,重写hashcode和equals方法保持一致,这种情况避免不了

加载因子,当到达元素个数的0.75,进行扩容,扩容则每个元素重新运算位置,,如果到达100%其他位置可能会不存入,如果太小,则频繁扩容,可浪费空间。这样碰撞的概率会降低,但是极端情况下还是需要查询每个元素比较,效率极低。

1.8以后,数组+链表+红黑树

当碰撞的个数大于8时,并且总容量大于64时,将链表转为红黑树,除了添加以外其他的效率都高,jdk1.8加到链表末尾,扩容以后不需要运行hash算法计算hashcode值。原来hash表的总长度,加上hash表的现在的位置,就放到第8个位置即可。

ConcurrentHashMap ConcurrentLevel16

A hash table supporting full concurrency of retrievals and
 * high expected concurrency for updates. This class obeys the
 * same functional specification as {@link java.util.Hashtable}, and
 * includes versions of methods corresponding to each method of
 * {@code Hashtable}. However, even though all operations are
 * thread-safe, retrieval operations do <em>not</em> entail locking,
 * and there is <em>not</em> any support for locking the entire table
 * in a way that prevents all access.  This class is fully
 * interoperable with {@code Hashtable} in programs that rely on its
 * thread safety but not on its synchronization details.

支持完全并发检索和更新的高预期并发性。这个类遵循java. util.HasTabe相同的功能规范,以及包括与每个方法对应的方法版本哈希表。然而,即使所有的操作线程安全,检索操作do<em>not<em>induct locking而且还支持锁定整个表,线程安全,但不在其同步详细信息上

构造方法摘要

Constructor and Description

ConcurrentHashMap()创建一个新的,空的地图与默认的初始表大小(16)。

ConcurrentHashMap(int initialCapacity)创建一个新的空的地图,其初始表格大小适应指定数量的元素,而不需要动态调整大小。

ConcurrentHashMap(int initialCapacity, float loadFactor)根据给定的元素数量( initialCapacity )和初始表密度( loadFactor ),创建一个新的,空的地图,初始的表格大小。

ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)创建具有基于给定数量的元件(初始表大小的新的空映射 initialCapacity ),表密度( loadFactor ),和同时更新线程(数 concurrencyLevel )。

ConcurrentHashMap(Map<? extends K,? extends V> m)创建与给定地图相同的映射的新地图。

像Hashtable但不像HashMap ,这个类不允许 null用作键或值。

1.7是锁分段 segment 16,隔离级别太大,有很多空间就浪费了,太小就段内的元素过多

1.8以后是cas算法C语言写得,无锁算法,put添加的时候,链表+红黑树

put方法(无锁添加)

unsafe是CAS算法的核心类,底层是native方法修饰的C语言编写

CAS算法的缺点:

1.0:循环时间长开销大

2.0:只能保证一个共享变量的原子操作

3.0:引发ABA问题

原文发布于微信公众号 - 赵KK日常技术记录(gh_cc4c9f1a9521)

原文发表时间:2019-06-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券