JAVA 常用集合内部机制原理

luqiuwen 发布于2019-08-16 10:28 / 1525人阅读

摘要：访问顺序调用过访问的元素会放到链尾，迭代会从链首开始插入顺序按插入顺序迭代出来内部是基于红黑树实现的，并且默认会通过按照类型进行自然排序。

对于常用的集合大家都不陌生，但是深入到内部原理可能都是一知半解，通过阅读源码理解如下。

ArrayList

ArrayList内部就是一个默认大小为10的动态对象数组容器，每当add一个新数据的时候，如果大于原来的容器大小，则会通过Arrays.copyOf把容器大小增加到原来的1.5倍，以此类推。当可以预知数据大小，可以通过initialCapacity来默认设置动态数据的大小，减少扩容带来的资源消耗。

时间复杂度：
get() - 直接读取下标 - O(1)
add(E) - 直接在后面添加 - O(1)
add(idnex, E) - 插入数据后需要移动后面的数据 - O(n)
remove(index) - 删除后需要移动 - O(n)

LinkedList

LinkedList内部是一个双向链表，add新数据的时候，其实就是调用linklast在链表尾部插入数据。删除的时候直接找到对应数据，替换掉链表的前后节点即可。

时间复杂度：
get() - 需要遍历 - O(n)
add(E) - 调用linklast直接添加在最后 - O(1)
add(index, E) - 需要先查找到原来index位置的数据，再重新指定链表前后的数据 - O(n)
remove() - 直接调用removeLast删除最后数据 - O(1)
remove(index) - 需要先查找到原来index位置的数据 - O(n)

HashMap

HashMap内部其实是一个数组，每个数组下是一个单向链表。HashMap中的数组是一个取名为Entry的类，类包含(key, value, next)这几个属性。存放规则为，数组下标按hash(key)%len获得，取得数组后则查找对应数组的值。HashMap还有个负载因子（默认0.75），当里面数组填满了75%的时候，会进行扩展到原来大小的2倍。

那么问题来了，如果在put的时候，取到hash(key)%len的值相等时不就冲突了？
HashMap的处理方法是：原来有一个Entry[0] = A，此时来一个index也是0的B，则会把Entry[0] = B，B.next = A，又来一个C的时候，则会把Entry[0] = C，C.next = B，以此类推。这样Entry就会形成一个链表，取的时候则是遍历链表取值。

这里需要提到的是，使用hashMap的时候，引入的key对象必须重写hashCode()和equal()两个函数，原因可以参考源码判断条件(if (e.hash == hash && ((k = e.key) == key || key.equals(k))))，如果hashCode()没重写，则压根找不到对应数组，如果equal()没重写，则无法判断key值的内容是否相等。

public V put(K key, V value) {  
        if (key == null)  
            return putForNullKey(value); //null总是放在数组的第一个链表中  
        int hash = hash(key.hashCode());  
        int i = indexFor(hash, table.length);  
        //遍历链表  
        for (Entry e = table[i]; e != null; e = e.next) {  
            Object k;  
            //如果key在链表中已存在，则替换为新value  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))){  
                V oldValue = e.value;  
                e.value = value;  
                e.recordAccess(this);  
                return oldValue;  
            }  
        }  
        modCount++;  
        addEntry(hash, key, value, i);  
        return null;  
}

补充：
在Java 8之后hashmap进行了优化：由于单向链表的查询时间复杂度为O(n)，在极端情况下(每次都查找)可能存在性能问题，于是Java 8针对链表长度大于8的情况会使用时间复杂度为O(log n)的红黑树进行存储来提升存储查询的效率，时间复杂度就从原来的O(1)+O(n)变成了O(1)+O(log n)，优化了极端情况导致的性能问题。

LinkedHashMap

LinkedHashMap内部双向链表和HashMap的结合，支持多种迭代顺序，默认按插入顺序，也可以按访问顺序。
访问顺序（accessOrder=true）：调用过get访问的元素会放到链尾，迭代会从链首开始
插入顺序（accessOrder=false）：按插入顺序迭代出来

TreeMap

TreeMap内部是基于红黑树实现的，并且默认会通过compareTo按照key类型进行自然排序。TreeSet的底层是TreeMap。

GPU云服务器云服务器 java集合的原理内部原理 php执行的机制原理 java 集合

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69866.html

金三银四，2019大厂Android高级工程师面试题整理

摘要：原文地址游客前言金三银四，很多同学心里大概都准备着年后找工作或者跳槽。最近有很多同学都在交流群里求大厂面试题。最近整理了一波面试题，包括安卓JAVA方面的，目前大厂还是以安卓源码，算法，以及数据结构为主，有一些中小型公司也会问到混合开发的知识，至于我为什么倾向于混合开发，我的一句话就是走上编程之路，将来你要学不仅仅是这些，丰富自己方能与世接轨，做好全栈的装备。原文地址：游客kutd...

tracymac7 2019-08-16 16:18 评论0 收藏0
小马哥Java项目实战训练营极客大学

摘要：百度网盘提取码一面试题熟练掌握是很关键的，大公司不仅仅要求你会使用几个，更多的是要你熟悉源码实现原理，甚至要你知道有哪些不足，怎么改进，还有一些有关的一些算法，设计模式等等。百度网盘提取码：u6C4 一、java面试题熟练掌握java是很关键的，大公司不仅仅要求你会使用几个api，更多的是要你熟悉源码实现原理，甚...

不知名网友 2021-11-26 11:11 评论0 收藏0
后台开发常问面试题集锦（问题搬运工，附链接）

摘要：基础问题的的性能及原理之区别详解备忘笔记深入理解流水线抽象关键字修饰符知识点总结必看篇中的关键字解析回调机制解读抽象类与三大特征时间和时间戳的相互转换为什么要使用内部类对象锁和类锁的区别，，优缺点及比较提高篇八详解内部类单例模式和 Java基础问题 String的+的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记深入理解Java Stream流水...

spacewander 2019-08-21 17:42 评论0 收藏0
后台开发常问面试题集锦（问题搬运工，附链接）

摘要：基础问题的的性能及原理之区别详解备忘笔记深入理解流水线抽象关键字修饰符知识点总结必看篇中的关键字解析回调机制解读抽象类与三大特征时间和时间戳的相互转换为什么要使用内部类对象锁和类锁的区别，，优缺点及比较提高篇八详解内部类单例模式和 Java基础问题 String的+的性能及原理 java之yield(),sleep(),wait()区别详解-备忘笔记深入理解Java Stream流水...

xfee 2019-08-15 12:33 评论0 收藏0