集合(常用集合的底层原理)

た入场券 2021-09-22 10:00 384阅读 0赞

本文主要从Collection、Map、链表等方向进行分析  
集合主要由可以分为两大类  
1、Collection  
2、Map  
一般我们使用的都是这个集合下面的子类，在这里我们谈谈它们实现的数据结构。  
**数组**  
百度百科是这样解释的：是按序排列的同类数据元素的集合称为数组。  
我的理解是，它是计算机内存中分配的连续的内存空间。  
它的优点是查找块，增删慢。  
我们最常用的ArrayList集合底层就是数组，它底层是一个动态分配的数组集合，当ArrayList达到一个点时，它会自动扩充，一般扩充是达到75%时，按照50%的比例扩充。刚开始ArrayList分配的长度是10。  
**链表**  
百度百科定义语句有点长，下面是我的截取的一些重点：是一种线性表，是一种物理存储单元上非连续、非顺序的存储结构。  
我的理解：它是内存不连续、但可以从第一个找到最后一个。  
一般情况下，使用的都是双链表，这样不仅可以找到前面元素，也可以找到后面元素，对定位添加删除查找都有很多帮助。  
LinkedList底层使用的就是双链表，常常我们用它当作队、栈，就是因为它是双链表的特性，它的特点是增删快，查询慢。  
在集合中，有Linked这个字段的，底层都使用的是双链表。如：LinkedHashSet，它底层使用的是散列表，散列表中有使用链表。  
**散列表**  
可以快速查找所需要的对象。散列表为每个对象计算一个整数，称为散列码，散列码是由对象的实例域产生的一个整数，具有不同的数据域的对象将产生不同的散列码。散列码就是Object类中hashCode方法产生的。  
使用链表数组实现，每个列表被称为桶。要想查找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就保存这个元素的桶的索引。有时会遇到桶被占满(散列冲突)。散列码是合理且随机分布的，桶的数目越大，需要比较的次数就会越少。  
想更多的控制散列表的运行性能，就需要制定一个初始的桶数，桶数是指用于收集具有相同散列值的桶的数目。如果要插入到散列表中的元素太多，就会增加冲突的可能性，降低运行性能。  
知道多少个元素要插入散列表，就将桶数设置为预计个数的75%~150%。有研究人员认为：最好将桶数设置为一个素数，以防键的集聚。HashSet这里使用的桶数是2的幂，默认值是16。  
如果散列表太满，就需要再散列。如果要对散列表再散列，就需要创建一个桶数更多的表，并将所有元素插入到这个新标中，然后丢弃原来的表(一般是扩充一倍)。装满因子决定何时对散列表进行再散列。HashSet一般的装填因子为0.75，而表中超过75%的位置已经填入元素，这个表就会用双倍的桶数自动地进行再散列。HashSet一般用的不是很多，主要原因是它不能进行排序。但HashMap用的还是蛮多的，Map表中一般不需要对键排序。  
**红黑树**  
红黑树，我们能知道它有这几个特点  
1、根元素必须为黑色  
2、红色不能连续  
3、叶子节点是黑色的  
4、叶子节点到根元素所进过的黑节点相同  
主要是这四个要点，实现起来不是特别难，主要它相比于二叉平衡树对平衡的要求不是特别好，平衡时相对于二叉平衡树旋转的次数能少一些。  
用在这里了，主要是对那些排序的元素插入快(不如B树快)，查询快(不如B树快)。TreeSet中底层使用的就是红黑树，它满足一般树的特点。  
一般情况下TreeSet使用比较多，TreeMap使用的比较少。  
**红黑树和散列表的区别**  
红黑树速度比散列表速度慢，但红黑树可以排序。  
现在你可以结合这个特点来判断TreeMap,TreeSet,HashSet,HashMap这四个什么时候用起来能好一点。  
**视图**  
它主要用于查询快，禁止修改，删除操作。它的底层使用的也是上面那几种。  
它主要用在遍历中，Map集合遍历和Collections中，返回的可能是ArrayList，但它其实是一个内部类，使用添加和删除的时候会抛出异常。如：Arrays类的静态方法asList，Collections.nCopies(n,anObject)，map中映射类的keySet。

总结：上面这些是了解集合中常用的数据结构原理，多看看这些底层代码，对你设计类，使用类会有很多的帮助。

主要参考课本：Java核心技术 卷1

# 如何觉得能帮助你，麻烦给作者一份信任，让作者有一个写下去的理由，不需要你给的太多，只需1块钱即可。 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70]  
支付宝  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 1]  
微信

# 如果你是一个新手或者是你已经工作多年，想修改简历或者想内推互联网公司(如：百度、滴滴、小米等公司)，均可以帮你内推；如果想修改简历，了解更多知识；下面是作者微信(备注csdn)。 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70]: /images/20210920/e8239c727f434dbd911ed0f148c6ff5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 1]: /images/20210920/fe710b464a4f43f7a5f347200e401b90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 2]: /images/20210920/ca428dbcb88040e19ca8254892372543.png