LinkedHashMap 底层实现原理分析

LinkedHashMap继承自HashMap实现了Map接口。基本实现同HashMap一样,不同之处在于LinkedHashMap保证了迭代的有序性。其内部维护了一个双向链表,解决了 HashMap不能随时保持遍历顺序和插入顺序一致的问题。除此之外,LinkedHashMap对访问顺序也提供了相关支持。在一些场景下,该特性很有用,比如缓存。

在实现上,LinkedHashMap很多方法直接继承自HashMap,仅为维护双向链表覆写了部分方法。所以,要看懂 LinkedHashMap 的源码,需要先看懂 HashMap 的源码。

默认情况下,LinkedHashMap的迭代顺序是按照插入节点的顺序。也可以通过改变accessOrder参数的值,使得其遍历顺序按照访问顺序输出。

这里我们只讨论LinkedHashMap和HashMap的不同之处,LinkedHashMap的其他操作和特性具体请参考HashMap

我们先来看下两者的区别:

Java

LinkedList 底层实现原理分析

  • 在Java.util包下
  • 继承自AbstractSequentialList
  • 实现 List 接口,能对它进行队列操作。
  • 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  • 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  • 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  • 允许包含null值
  • 迭代器可以快速报错
  • 非线程安全的,如果在多线程中使用(修改),需要在外部作同步处理。

LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的。内部有三个变量,size表示链表中元素的个数, first指向链表头部,last指向链表尾部。 结构图如下图所示

Java

Vector 底层实现原理分析

Vector,一个可变长的数组,底层实现与 ArrayList 大同小异,但Vector是同步的(线程安全),Vector的很多方法之前都加了关键字synchronized,所以是线程安全的。

由于Vector的实现和ArrayList的实现大同小异,这里就不再逐一分析Vector中的方法,主要分析一下和ArrayList不同的方法。

首先我们还是来看以下Vector中定义的变量

Java

ArrayList动态扩容机制

我们通过一个具体的例子看一下ArrayList的扩容效果
先看一下ArrayList的初始容量

ArrayList<Integer> array = new ArrayList<>();
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量:"+capacity);
System.out.println("大小:"+size);
容量:0
大小:0

getCapacity()方法是用来获取集合容量的,ArrayList通过一个elementData对象数组储存数据,也就是说ArrayList的容量就是该数组的长度。所以我们只要得到了elementData数组就可以知道ArrayList的实际容量。

Java

ArrayList 底层实现原理分析

ArrayList是List接口的 可变数组的实现。实现了所有可选列表操作,并允许包括 null 在内的所有元素。除了实现 List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。ArrayList继承自 AbstractList,这是一个抽象类对一些基础的list操作做了一些封装.实现了RandomAccess 标记接口,表明可以实现快速随机访问.实现了Cloneable接口的实现表示该容器具有Clone函数操作,Serializable是序列化。

每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的大小,就可在构造ArrayList实例时指定其容量。

在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。

注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

ArrayList这个数据结构比较简单,总体来说,ArrayList底层结构是数组,他的很多方法都是从数组上面演变而来的。

下面我们先来看一下ArrayList中的一些初始值

Java

动态代理原理剖析

动态代理的常用实现方式是反射。反射机制是 Java 语言提供的一种基础功能,赋予程序在运行时自省(introspect,官方用语)的能力。通过反射我们可以直接操作类或者对象,比如获取某个对象的类定义,获取类声明的属性和方法,调用方法或者构造对象,甚至可以运行时修改类定义。

动态代理是一种方便运行时动态构建代理、动态处理代理方法调用的机制,很多场景都是利用类似机制做到的,比如用来包装 RPC 调用、面向切面的编程(AOP)。

JDK 自身提供的动态代理,就是主要利用了上面提到的反射机制。但动态代理不止有反射一种实现方式,还有其他的实现方式,比如利用传说中更高性能的字节码操作机制,类似 ASM、cglib(基于 ASM,一个 Java 字节码操作框架)、Javassist 等。简单来说,动态代理是一种行为方式,而反射或 ASM 只是它的一种实现手段而已。

Java