java集合之HashMap理解和分析

硅谷探秘者 1109 0 0

1.HashMap的构造函数

1.public HashMap()
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

        构造一个空的HashMap,初始容量为16,负载因子为0.75,负载因子和它的作用将会在下方解释。

2.public HashMap(int initialCapacity)                        
public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

        构造一个初始容量为initialCapacity,负载因子为0.75的HashMap。

3. public HashMap(int initialCapacity, float loadFactor)
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);
}

        构造一个初始容量为initialCapacity,负载因子为loadFactor的HashMap。

4.public HashMap(Map<? extends K, ? extends V> m)
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
}

        构造一个和参数Map有相同mappings的HashMap,并将m中的键值元素移到HashMap中。

2.HashMap的底层数据结构

        在JDK1.8以后采用了hash表+链表+红黑树的数据结构,如下图。
        JDK1.8之前则采用的是hash表+链表的数据结构。

        从源码中可以知道HashMap内部维护者一个table的数组,它的默认大小是16。

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    transient Node<K,V>[] table;

        并且使用的是拉链法处理hash冲突。
        从HashMap的put方法的源码中可以看到,当链表的长度大于等于7时,链表将会转换成为红黑树。

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;
}

3.HashMap的扩容机制

        HashMap的扩容和之前提到的负载因子有关,当HashMap中的元素个数超过数组大小*loadFactor(负载因子默认0.75)时,就会进行数组扩容,HashMap的容量将扩大一倍。然而扩容是非常消耗性能的,因为元素要重新hash分配。
        值得注意到的是在jdk中,当我们new HashMap并且指定初始化容量capacity时,jdk会帮我们取第一个大于capacity的2次幂。也即HashMap的容量必须是2的幂。
        比如new HashMap(3); jdk则会生成一个容量为4的HashMap,new HashMap(5); jdk则会生成一个容量为8的HashMap。如果没有指定,则默认就是16。
        因此可以得到一个结论,HashMap初始化时,初始化大小应该是initialCapacity=(需要储存元素的个数 / 负载因子)+1

4.HashMap线程不安全

        HashMap的put方法并没有用到synchronized同步锁,所以在进行hash分配时,或处理hash冲突时(操作链表),或处理红黑树的结构时都会牵扯到对象引用的改变,那么在多线程环境下势必会造成数据结构组织错误,或其他异常。
        此后还会重点研究一下ConcurrentHashMap,这是一个线程安全的,效率较(HashTable)高的HashMap。


评论区
请写下您的评论...
暂无评论...
猜你喜欢
java基础 1738 javaTreeMap实现原TreeMap的实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完全依靠红黑树这个数据结构,相比与HashMap来说TreeMap不用考虑
java基础 1288 javaHashtable一、构造方法1.publicHashtable()publicHashtable(){this(11,0.75f);}无参构造,初始化一个容量为11,负载因子为
java基础 1224 一、HashSet底层实现从HashSet的源码中可以发现,它的底层维护了一个HashMap,在newHashSet的时候,构造方法中其实是new了一个HashMap
java基础 2633 ArrayList的实现是一个动态数组,从源码中也可以看出。这就决定了他的查找效率高,可以直接通过下标访问。但是对于删除增加元素,需要大量的移动元素,所以插入删除的效率就很低。ArrayList
java基础 2066 1.linkedList的实现linkedlist的实现是基于数据结构:双向链表。模型图如对于linkedList没有像arrayList一样有扩容的概念。也不需要移动数据。所以对于新增删除操作
数据结构,算法基础 404 代表来表示属于这个.当set[i]==i是表明i是一个根节点。set[i]==k可以为i,k间有一条连通的路线,被称为链接。 初始化让所有元素指向自己,表示属于不同的,此时中每个元素
java虚拟机(jvm) 1389 硬件的效率与一致性在正式讲Java虚拟机并发相关的知识前,我们先花费一点时间去了一下物计算机中的并发问题,物机遇到的并发问题与虚拟机中的情况有不少相似处,物机对并发的处方案对于虚拟机
java基础 2179 Java框架数据结构是以某种形式将数据组织在一起的,它不仅存储数据,还支持访问数据的操作。Java提供了几个能有效地组织操作数据的数据结构,这些数据结构通常称为Java框架。在平
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。