数据结构与算法|集合总结--ArrayList、LinkedList、HashMap 数据结构与算法|java

一、概述 ArrayList：数组集合。查询、修改、新增（尾部新增）快，删除、新增（队列中间）慢，适用于查询、修改较多的场景。 LinkedList：双向链表集合。查询、修改慢（需要遍历集合），新增，删除快（只需要修改前后节点的链接即可），适用于新增、删除较多的场景。 HashMap：结合数组和链表的优势，期望做到增删改查都快速，时间复杂度接近于O(1)。当hash算法较好时，hash冲突较低。适用于增删改查所有场景。二、分叙 ArrayList

ArrayList底层实现是基于数组的，因此对指定下标的查找和修改比较快，但是删除和插入操作比较慢。
【数据结构与算法|集合总结--ArrayList、LinkedList、HashMap】构造ArrayList时尽量指定容量，减少扩容时带来的数组复制操作，如果不知道大小可以赋值为默认容量10。
每次添加元素之前会检查是否需要扩容，每次扩容都是增加原有容量的一半。（扩容是创建一个新的数组，并将原来的数组元素迁移到新数组中）
每次对下标的操作都会进行安全性检查，如果出现数组越界就立即抛出异常。
ArrayList的所有方法都没有进行同步，因此它不是线程安全的。
以上分析基于JDK1.7，其他版本会有些出入，因此不能一概而论

LinkedList 数据结构

private static class Node { E item; //元素 Node next; //下一个节点 Node prev; //上一个节点Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }

LinkedList是基于双向链表实现的，不论是增删改查方法还是队列和栈的实现，都可通过操作结点实现
LinkedList无需提前指定容量，因为基于链表操作，集合的容量随着元素的加入自动增加（无需执行默认长度，也没有扩容需求）
LinkedList删除元素后集合占用的内存自动缩小，无需像ArrayList一样调用trimToSize()方法
LinkedList的所有方法没有进行同步，因此它也不是线程安全的，应该避免在多线程环境下使用
LinkedList根据index查询时采取的是二分法，即index小于总长度一半时从链表头开始往后查找，大于总长度一半时从链表尾往前查找。如果是根据元素查找，则需要从头开始遍历
以上分析基于JDK1.7，其他版本会有些出入，因此不能一概而论。

HashMap 数据结构

static class Entry implements Map.Entry { final K key; //键 V value; //值 Entry next; //下一个Entry的引用 int hash; //哈希码 ...//省略下面代码 }

哈希图

数据结构与算法|集合总结--ArrayList、LinkedList、HashMap

文章图片

- 哈希表是由数组和单项链表共同构成的一种结构，上图中一个数组元素链表存在多个元素，说明存在hash冲突，理想情况下每个数组元素只应包含一个元素
- 扩容原因：HashMap默认的初始容量为16，默认的加载因子是0.75。而threshold是集合能够存储的键值对的阀值，默认是初始容量*加载因子，也就是16*0.75=12，当键值对要超过阀值时，意味着这时候的哈希表已处于饱和状态，再继续添加元素就会增加哈希冲突，从而使HashMap的性能下降。
- 每次扩容都是增加原有容量的一倍。（扩容是创建一个新的数组，并将原来的数组元素迁移到新数组中，根据hash值重新分配）
- hash值的计算方式（字符串是单独的计算方式，扰动函数就是把所有东西杂糅到一起，提高随机性）

//生成hash码的函数 final int hash(Object k) { int h = hashSeed; //key是String类型的就使用另外的哈希算法 if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); //扰动函数 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

三、总结
概述中已经描述各个集合的适用场景，这里重点说一下HashMap。HashMap可以通过hash值快速定位到数组下标，执行新增、修改、删除操作。当hash算法较好（hash冲突较少）时，增删改查的时间复杂度都是O(1)。但是如果链表较长，则会增加增删改查的时间复杂度O（链表长度）。原则就是尽量减少hash冲突，并预先估算hashmap长度，减少扩容操作。