Java学习篇之容器篇（进阶&源码分析）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java学习篇之容器篇（进阶&源码分析），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12754字，纯文字阅读大概需要19分钟。
内容图文
一、概括：
在java中，由于数组长度固定，在实际开发中用到的并不多；为了解决数组长度固定的缺陷，在JDK1,2开始，java中提供了集合框架（容器）来解决这一问题。简单来说，java集合框架实际上就是一种数据结构，用来存放数量不固定的元素。java类集框架中提供了两个最为核心的接口，Collection 和 Map
- Collection ：和单链表类似，每一次操作的都是单个元素
- Map ：每次操作的都是一对键值对（key = value）
二、Collection集合
2.1 常见类的结构图：
List：
List：存放单个元素，元素可以重复
先来看一下他们的基本使用：
public class ListTest {
public static void main(String[] args) {
//List 是一个接口，通过子类进行对象实例化,通过泛型指明集合中存的是int型的变量
List<Integer> list = new ArrayList();
// 向集合中添加元素
list.add(1);
list.add(2);
list.add(3);
list.add(5);
//删除集合中的某个元素
list.remove(3); //删除下标为3元素的
int a = list.get(2); // 获取下标为2的元素
list.clear(); // 清空集合
System.out.println(list.size()); // 输出集合中元素个数
System.out.println(list.contains(3));
}
}
这里列出来了一些简单的用法，其余两个用法也都差不多。这里重点看看List集合的三个常见子类之间的区别：
- ArrayList：
- JDK1.2产生
- 底层是基于动态数组实现的，易于随机访问，但是插入，删除元素的时候需要移动大量元素；
- 是一个异步操作，线程不安全，但是性能高
- 采用懒加载策略（在第一次插入元素的时候才会初始化数组的大小）
- 扩容方式：当数组存满了的时候，会扩容到原来的1.5倍
- 遍历集合的方式：Iterator, ListIterator , foreach
对应的一些源码简单分析：
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- Vector ：
- 底层通过动态数组实现，和ArrayList差不多
- Vector是线程安全的（使用了synchronized关键字），性能低
- Vector在对象产生的时候就会初始化数组的大小，默认容量为10
- 扩容：当数组大小不够用时，扩容为原来的2倍
- 遍历集合的方式：Iterator， ListIterator， foreach， Enumeration
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
使用synchronized实现同步操作（下图只是列举部分方法）：
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
- LinkedList ：
- 底层通过链表实现，易于插入和删除元素，但是不支持随机访问，需要挨个遍历
- 还可以用作栈，队列和双向队列
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注意：这里关于ArrayList还要注意两点：
- ArrayList的序列化问题：Array List基于数组实现，并且具有扩容性的特征，因此并不是它的所有空间都一定会被使用（只有一部分空间存放了数据），ArrayList中保存元素的elementData数组由transient关键字修饰，被这个关键字修饰的对象在默认情况下不会被序列化，ArrayList通过实现了writeObject和readObject来控制只序列化有元素的那部分数组。
- 对于ArrayList是一个线程不安全的集合，有两种解决方案：
- 通过使用 Collections.synchronizedList( ) 来获得一个线程安全的ArrayList
- 也可以使用Concurrent并发包下的CopyOnWriteArrayList类（读写分离）
关于读写分离所CopyOnWriteArrayList ：
1、读写分离：
- 所谓的读写分离指的是写操作和读操作没有在一个数组中进行，写操作是在一个复制的数组上进行的，读操作是在原来的数组中进行的，读和写完全分离，互不影响。
- 在进行写操作的时候需要加锁，防止并发写入时导致写入的数据丢失
- 写操作完了之后需要把原数组指向新的数组
2、使用场景：
- 在写操作的同时允许读数据，大大提升了读操作的性能，因此适用于读多写少的场景
3、缺点：
- 占用内存：在进行写操作的时候需要复制一个新的数组，使得内存占用为原来的两倍
- 数据不一致：读操作不能读取实时性的数据，因为部分写操作还没有同步到数组中去
- 不适合内存敏感以及对数据实时性要求较高的场景
Set集合：
Set ：存放单个元素，元素不能重复
常用子类中有HashSet 和 TreeSet：
TreeSet：
- 基于红黑树实现，支持有序操作，但是查找效率不如HashSet（HashSet的查找时间复杂度为O(1), TreeSet的查找时间复杂度为O(logn)），TreeSet中不允许存放空值。
- 所谓的有序操作，就是指通过底层的树可以对插入的数据进行排序，输出的时候是一个有序序列
- TreeSet的有序，必须满足一下条件之一：
- 作为TreeSet集合类，实现Compareable接口（内部排序）
- 通过构造方法，传入Comparator接口对象（外部排序）
如果以上两个条件都满足，优先使用外部接口（更加灵活，策略模式）
- TreeSet怎么比较两个元素是否相等：
- 如果指定了Compareator（也就是第一种构造方法），那么就用其中的compare方法进行比较；
- 否则就用Compareable接口中的compareTo方法进行比较；
HashSet：
- 基于哈希表实现，支持快速查找，但是不支持有序操作，使用iterator遍历结果的时候结果的顺序是不确定的，允许向其中插入空值，但是只能插入一个。
- HashSet怎么判重（hashCode方法和equals方法一起使用来判重）：
-
当程序向HashSet中添加一个对象的时候，先用hashCode方法计算出一个Hash码 ；
-
如果算出来的Hash码和集合中已经存在的hash码不一致，这说明该对象没有与其他对象重复，可以添加到集合
-
如果计算出来的hash码和已有元素的hash码重复，就说明该元素有可能和其他元素重复，就再次调用equals方法比较两个对象是否相同，如果比较之后发现两对象相同，就说明集合中已经有该对象了（重复了），就不能插入该元素；如果调用equals方法发现两对象不相同，就说明两对象不相同，就可以插入元素
- 为什么有了hash码进行比较，还要使用equals方法呢？？？
- 首先，如果是Object类中的hashCode方法的话，是不会返回两个完全相同的hash码的（Object中的hashCode方法可以唯一标示对象）；
- 但是这样程序的运行逻辑不符合现实生活（这个逻辑就是：属性相同的对象被看做同一对象）；
- 为了让程序逻辑符合生活，Object的子类会覆写hashCode方法（基本数据类型已经覆写过这个方法，自定义类需要自己覆写）；
- 但是在我们覆写的时候，即使哈希函数设计的再精妙，总是不可避免的出现一个bug：有些属性不同的对象也会返回相同的hash码；
- 最后，为了解决这个问题，在hash码相同的时候，在使用equals方法比较这两个对象是否相同，以保证万无一失；
LinkedHashSet：
- 具有HashSet的查找效率，同时底层是双向链表实现，可以维护元素的插入顺序，又因为是集合，可以过滤掉重复元素；
- 如果在既需要排除重复元素，又想维护数据的插入顺序，可以考虑使用这一个Set子类，不过这是一个非线程安全的，如果在多线程使用，必须要在外部实现同步操作
二、Map集合（存储的是Key = Value的键值对）
Map中常见类的结构图：
HashMap的源码分析：
- 容量：默认容量为16
- 负载因子为：0.75
- 最大容量 ： 2的30次方
- 树化 ：当桶的数量超过64，链表长度超过8就会树化（将桶中的链表结构转为红黑树结构），树化的时候并不是将整个哈希表中的链表树化，而是只会树化那些长度超过8的链表；
- 解除树化：当一个红黑树的节点个数小于6，将红黑树结构转为链表结构
- 为什么要树化：链表长度太长的话，会影响查找效率（链表的查找效率为O(n）,红黑树的查找效率为O(logn) ）
- 初始化策略：
- 采用懒加载策略（一开始不会初始化桶的容量，等到第一次插入数据的时候才会初始化桶）
- 在初始化容量的时候，要求容量必须为2的n次方（当通过构造方法传入一个初始容量时，如果传入的这个参数不是2的n次方，那么HashMap会自动调用一个方法tableSizeFor，去返回一个最接近传入参数的2的n次方的一个数值作为初始化容量）
- 为什么一定要是2的n次方？？？ 因为在put方法中，有一行代码为：if ((p = tab[i = (n-1) & hash]) == null) 如果其中的n恰好为一个2的n次方的数的话，(n-1) & hash 刚好就是hash%(n-1）的值，这里使用位运算代替取余操作，可以提高效率。
- put方法执行过程分析：
- 若HashMap还没有初始化，先调用resize方法进行初始化操作
- 对key值hash，取得存储下标
- 如果这个桶为空，直接将节点作为头结点保存
- 如果不为空，判断是否树化，如果树化，就按照树的方式将节点插入；如果没有树化，就用链表的方式插入，插入后，如果链表的binCount >= 树化阈值-1， 就尝试进行树化操作
- 如果桶中存在相同的key，就将value的值替换
- 添加元素后，计算hash表的大小，如果超过threshold（容量*负载因子），进行resize（扩容）操作
- get方法流程：
- 若表已经被初始化，并且首节点不为空
- 查找节点的值恰好等于首节点，返回首节点，否则
- 进行桶节点的遍历，如果树化，就按树的方式遍历，没有就按两点方式进行遍历；
- 如果hash表为空或者首节点为空，就直接返回null
- hash算法：
- 如果key为空（null），就返回0（因为如果为空，不能使用null的hashCode方法计算下标）
- 如果不为空，返回key的hashCode方法返回的值的高十六位与第十六位的异或运算的值
- 为什么不直接使用Object的hashCode方法：因为Object方法的hashCode几乎不会产生哈希冲突，因此就需要大量的桶；
- 扩容机制：
- resize方法：
- 判断哈希表是否已经初始化，若还没有初始化，就根据InitialCapacity的值进行初始化
- 如果表已经初始化，将hash表按照二倍的方式进行扩容
- 扩容后将原表的数据进行移动：如果桶中元素已经树化，调用树的移动方式，若在移动过程中发现红黑树节点的个数小于等于6，就解除树化，还原为链表；如果还没有树化，就按链表的方式移动元素。
- 扩容存在的问题及解决方法：
- 问题：多线程下，如果出现竞争，容易出现死锁；解决方法：使用ConcurrentHashMap代替HashMap
- 问题：rehash操作耗时；解决方法：在能预估元素个数的情况下尽量自定义初始化容量
Hashtable：
- 基于哈希表实现，和HashMap类似，但它是线程安全的，目前使用的不多，已经被ConcurrentHashMap代替。
- Hashtable 如何实现线程安全：在put、 get、 remove等方法上使用synchronized关键字，对整个hash表上锁，性能低下。
- 优化Hashtable的性能：将锁细粒度化（把一个大锁拆成一些小锁）
- 初始化策略：当产生Hashtable对象时就将整个表的大小初始化好，默认容量为11，如果通过构造方法传入初始容量，传的是多少就是多少（不会转为2的多少次方）
- Hashtable的一个子类：Properties :属性文件
- 在Java中存在一种属性文件（* . properties），这种文件的内容为key = value的形式，可以通过ResourceBundle类读取该文件中的类容，通过Properties类编辑文件内容。这个类的作用：可以用作属性值的初始化
- 常用方法：
- 设置属性值：setProperty(key, value);
- 取得属性：
- getProperty (key) ，如果没有指定key 返回null
- getProperty (key ， defaultValue) 如果没有指定key 返回默认value
ConcurrentHashMap : (JDK1.5新增的)
- JDK7之前的实现：
- 结构：将一个hash表拆分为16个Segment， 每一个Segment又是一个小的hash表 ；
- 关于锁：将原先整个表的大锁细粒度化为每一个Segment一把锁，并且不同Segment之间互不干扰，每一个Segment实际上都是一个ReentrantLock的子类 ；
- 扩容机制：Segment初始化以后就不能再扩容，默认初始容量为16；我们 “肉眼看见的” 扩容 实际上是每一个Segment的扩容。每一个Segment是一个小的hash表，这些小的哈希表可以扩容，并且每一个Segment之间的扩容完全隔离。
- 总结：ConcurrentHashMap是基于分段锁Segment来实现的，每一个Segment都是ReentrantLock的子类 。
- JDK8 的实现：
- 结构和JDK8的HashMap如出一辙，也是hash表加红黑树的底层结构，原来的Segment依然保留，但没有实际意义，仅用作序列化 ；
- 关于锁：将原来的小锁再次细粒度化，变为只锁桶的头结点。使用的是CAS+同步代码块（synchronized）；
- 为甚么在JDK8中会用内建锁机制：在现代版本中，内建锁和Lock体系性能相差并不大，甚至在某些方面内建锁性能可能更由于Lock体系 ， 并且内建锁可以节省大量空间 ；
内容总结
以上是互联网集市为您收集整理的Java学习篇之容器篇（进阶&源码分析）全部内容，希望文章能够帮你解决Java学习篇之容器篇（进阶&源码分析）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。