ArrayList、LinkedList 和 HashMap 底层原理

ArrayList、LinkedList 和 HashMap 底层原理

1.LinkedList 和 ArrayList底层源码分析

ArrayList：作为List的主要实现类；线程不安全，效率高；底层使用数组实现。
LinkedList:对于频繁的插入、删除操作，建议使用此类，因为效率高；底层使用双向链表实现
Vector:List的古老实现类；线程安全的，效率低；底层使用数组实现

LinkedList jdk1.8 源码

由源码可看出LinkedList底层是使用双向链表实现的。

ArrayList 源码

jdk 1.7:





jdk1.8:






总结：

• ArrayList 底层使用数组实现。
• 一旦要添加的元素超出了底层数组的长度，就需要扩容，默认扩容为原来的1.5倍，同时，需要将原有数组中的元素复制到新的数组中。
• 实际情况：需要存储80个数据到ArrayList中，建议 ： List list = new ArrayList(85);如果能确定长度，就尽量在方法里写上长度，这样底层直接给到这个长度的数组，避免了不断判断，不断扩容

jdk1.7 和 jdk1.8源码主要区别：
前者是先创建一个长度为10的数组
Object[] elementData = new Object[10];
后者是先不创建一个长度为10的数组
Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
等到list对象调用add()方法时，再创建长度为10 的数组

2.HashMap 的底层源码分析

HashMap:Map的主要实现类，线程不安全的，效率高；可以存储null的key和value（存储结构：jdk 7.0: 数组 + 链表；jdk 8.0 :数组+链表+红黑树）
LinkedHashMap:HashMap的子类，可以按照添加的顺序遍历，对于频繁的遍历效率较高。（在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序）
TreeMap:可以按照key的制定的熟悉进行排序，底层实现：红黑树
Hashtable:Map的古老实现类；线程安全的，效率低；不可以存储null的key和value
Properties:Hashtabke的子类，常常用了处理属性文件。其key和value都是String型。

HashMap jdk 1.7

① HashMap 的数据结构

② HashMap 源码（jdk 1.7）





由上面的代码创建了长度为16的Entry数组

总结：
向HashMap 中添加entry1(key,value)，需要首先计算entry1中key的哈希值（根据key所在类的hashCode()计算得到），此时哈希值经过处理以后，得到在底层Entry[] 数组中要存储的位置i，如果位置i上没有元素，则entry1直接添加成功。如果位置i上以经存在元素entry2(或还有链表存在的entry3,entry4)吗，则需要通过循环的方法，依次比较entry1中key和其他的entry是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回的都为false，则entry1仍可添加成功。entry1指向原有的entry元素。

默认情况下，如果添加元素的长度 >= DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR(默认值为12)，且新要添加的数组位置不为null的情况下，就进行扩容。默认扩容为原有长度的2倍，将原有的数据复制到新的数组中。

HashMap jdk 1.8 :

putVal()方法里部分代码：


形成红黑树方法：

HashMap jdk1.8 与 jdk1.7 区别：
1.HashMap map = new HashMap();//默认情况下，先不创建长度为16的数组
2.当首次调用map.put()时，再创建长度为16的数组
3.当数组指定索引位置的链表长度为 > 8 时，且map中的数组的长度 > 64 时，此索引位置上的所有entry使用红黑树进行存储