Java 集合复习

复习范围：

集合复习

ArrayList与LinkedList区别

• 线程安全：两个都是不同步的，即不保证线程安全
• 数据结构：ArrayList用的是数组实现，LinkedList用的是双向链表。
• 插入删除，随机访问：ArrayList因为是数组，所以插入删除末尾元素的话时间复杂度只需O（1），如果是指定位置i的元素，因为要对i之后的元素进行往后一位或者往前一位的操作，时间复杂度为O（n-i）。LinkedList是链表，所以插入删除指定位置i的元素就要一直移动到指定位置再删除，时间复杂度为O（i），但是如果在末尾删除插入元素，时间复杂度为O（1）。ArrayList支持随机访问，直接通过数组下标就可以访问元素了。LinkedList则不支持，这也是数据结构的区别造成的。
• 空间占用：ArrayList的结尾需要预留一定的容量空间，而LinkedList每个元素都要有直接前继，直接后继，元素大小。所以每个元素消耗的空间大于ArrayList。

ArrayList扩容机制

minCapacity:所需的最小容量
当ArrayList增加元素时，minCapacity就会+1，这个时候拿他和默认值10进行比较，取最大值赋给minCapacity。当minCapacity大于当前ArrayList的长度后，就会调用grow方法来进行扩容。

扩容过程：先把旧容量（当前数组的长度，不是数组元素的个数）变为之前的1.5倍，再和minCapacity相比，如果还是小于minCapacity就会把minCapacity的值赋给新容量（newCapacity）。如果新容量大于ArrayList所定义的最大容量MAX_ARRAY_SIZE，newCapacity就为Interger.MAX_VALUE，否则是MAX_ARRAY_SIZE。最后把原数组内容放到新的数组里面。

HashMap

JDK1.8以前是用的数组＋链表的形式，，先对key的hashcode进行hash方法，得到一个hash值，然后用hash & （ n - 1 ）来得到该存放在数组的哪一个位置，如果这时候数组该位置已经有一个了，那么判断两者的hash和key是不是相同，相同就直接覆盖了，不同的话就在数组的该位置生成一个链表，把后者加进链表里面。
这样子的话如果所有key都存放在数组的一个链表上面，那么查找效率就是从链表的第一个节点往下面找，是个线性结构，就会导致效率过低，所以JDK1.8引入了红黑树来辅助查找。当链表长度大于指定值（一般是8），这个时候就会判断数组长度是否大于64，大于的话链表就会转化为红黑树，小于的话会对数组进行扩容。

HashMap多线程的问题

多线程中，HashMap扩容后要重新计算hash值，也就是rehash后，元素之间会存在一个死循环链表，然后就会一直在运行，浪费资源。jdk1.8之后解决了这个问题。

HashMap和HashTable区别

• 数据结构：HashMap用的是数组＋链表的形式，如果链表长度大于8，数组长度大于64，链表就会转成红黑树。HashTable不会转红黑树。
• 存放null ：HashMap允许存放key和value都为null的值。key只允许存放一个，value可以存放多个。HashTable不允许存放null。
• 线程安全：HashMap在多线程的时候是不安全的，HashTable是安全的，里面的方法经过synchronized修饰过。（注意：HashTable现在不推荐使用，如果要保证线程安全就要使用ConcurrentHashMap！）
• 效率：HashMap效率会高一点，因为线程安全的问题。
• 初始容量：HashMap默认值是16，如果要扩容就会乘2，因为他要保证长度永远是2的幂次方。如果你给了一个初始值，就会把它扩充成2的幂次方。HashTable默认值是11，每次扩容就是原来的2n+1。给定初始值的话，HashTable会直接使用你给的值。

HashMap和HashSet区别

HashSet基于HashMap实现，所以都是线程不安全

• HashMap实现了Map接口，HashSet实现了set接口
• HashMap存储了键值对，HashSet存储对象
• HashMap使用key计算hashcode。HashSet使用成员对象来计算hashcode，对于两个对象可能hashcode相等，这个时候就要用equals来判断两个对象相不相等。
• HashMap添加时遇到重复值是覆盖，HashSet遇到重复值是把后来的放弃掉，维持原来的。

HashSet检查重复

当你添加对象到HashSet中，HashSet计算对象的hashcode值，与其他对象的hashcode进行比较，如果有相同hashcode的对象，就调用equals方法来检查两个对象是不是相等，相等就不把对象添加进HashSet中。

LinkedHashMap

LinkedHashMap可以把添加的数据，按添加的顺序输出 。用的是双向链表。

ConcurrentHashMap线程安全

JDK1.7:把数据分成一段一段，分开上锁，如果一个线程对第一段数据进行操作，那么其他线程依旧可以访问其他段数据。由Segment数组结构和HashEntry数组结构组成。Segment负责锁的角色，HashEntry负责存储键值对。
一个ConcurrentHashMap有一个Segment数组，每个Segment有一个HashEntry数组。每个Segment都会守护一个HashEntry的数据，如果要进行操作，必须获得相对应的Segment。

JDK1.8：放弃了Segment，才用CAS和synchronized来保证安全。数据结构和HashMap一样，采用Node数组+链表/红黑树的结构。synchronized锁定当前链表和红黑树的首节点，只要hash不冲突，就不会产生并发。

ConcurrentHashMap与HashTable

HashTable使用Synchronized来保证线程安全，效率比较低。当一个线程进行put操作时，其他线程无法进行put和get操作。ConcurrentHashMap采用的是数据分成一段段进行上锁，这样子就不会产生过多的阻塞，也能保证线程安全。

根据资料：
本文主要根据JavaGuide的资料
ArrayList简介