从上面看到，HashMap 主要是数组 + 链表结构组成。HashMap 扩容是成倍的扩容。为什么是成倍，而不是1.5或其他的倍数呢？既然 HashMap 在进行 put 的时候针对 key 做了一些列的 hash 以及与运算就是为了减少碰撞的一个概率，如果扩容后的大小不是2的n次幂的话，之前做的不是白费了吗？

ConcurrentHashMap 采用了分段锁技术来将数据分成一段段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

ArrayList：

LinkedList：

ArrayList 底层是一个变长的数组，基本上等同于Vector，但是ArrayList对writeObjec() 和 readObject()方法实现了同步。

从注释，我们知道 ArrayList 是线程不安全的，多线程环境下要通过外部的同步策略后使用，比如List list = Collections.synchronizedList(new ArrayList(…))。

当调用add函数时，会调用ensureCapacityInternal函数进行扩容，每次扩容为原来大小的1.5倍，但是当第一次添加元素或者列表中元素个数小于10的话，列表容量默认为10。

扩容原理：根据当前数组的大小，判断是否小于默认值10，如果大于，则需要扩容至当前数组大小的1.5倍，重新将新扩容的数组数据copy只当前elementData，最后将传入的元素赋值给size++位置。

根据源码可知，当调用add函数时，首先要调用ensureCapacityInternal(size + 1)，该函数是进行自动扩容的，效率低的原因也就是在这个扩容上了，每次新增都要对现有的数组进行一次1.5倍的扩大，数组间值的copy等，最后等扩容完毕，有空间位置了，将数组size+1的位置放入元素e，实现新增。

在删除index位置的元素时，要先调用 rangeCheck(index) 进行 index 的check，index 要超过当前个数，则判定越界，抛出异常，throw new IndexOutOfBoundsException(outOfBoundsMsg(index))，其他函数也有用到如：get(int index)，set(int index, E element) 等后面删除重点在于计算删除的index是末尾还是中间位置，末尾直接--，然后置空完事，如果是中间位置，那就要进行一个数组间的copy，重新组合数组数据了，这一就比较耗性能了。

而查询：

addFirst(E e):将指定元素添加到刘表开头
addLast(E e):将指定元素添加到列表末尾
descendingIterator():以逆向顺序返回列表的迭代器
element():获取但不移除列表的第一个元素
getFirst():返回列表的第一个元素
getLast():返回列表的最后一个元素
offerFirst(E e):在列表开头插入指定元素
offerLast(E e):在列表尾部插入指定元素
peekFirst():获取但不移除列表的第一个元素
peekLast():获取但不移除列表的最后一个元素
pollFirst():获取并移除列表的最后一个元素
pollLast():获取并移除列表的最后一个元素
pop():从列表所表示的堆栈弹出一个元素
push(E e);将元素推入列表表示的堆栈
removeFirst():移除并返回列表的第一个元素
removeLast():移除并返回列表的最后一个元素
removeFirstOccurrence(E e):从列表中移除第一次出现的指定元素
removeLastOccurrence(E e):从列表中移除最后一次出现的指定元素

LinkedList 的实现原理：LinkedList 的实现是一个双向链表。在 Jdk 1.6中是一个带空头的循环双向链表，而在 Jdk1.7+ 中则变为不带空头的双向链表，这从源码中可以看出：

为什么说 LinkedList 增删很快呢？

从注释看，add函数实则是将元素append至list的末尾，具体过程是：新建一个Node节点，其中将后面的那个节点last作为新节点的前置节点，后节点为null；将这个新Node节点作为整个list的后节点，如果之前的后节点l为null，将新建的Node作为list的前节点，否则，list的后节点指针指向新建Node，最后size+1，当前llist操作数modCount+1。

在add一个新元素时，LinkedList 所关心的重要数据，一共两个变量，一个first，一个last，这大大提升了插入时的效率，且默认是追加至末尾，保证了顺序。

删除指定index的元素，删除之前要调用checkElementIndex(index)去check一下index是否存在元素，如果不存在抛出throw new IndexOutOfBoundsException(outOfBoundsMsg(index));越界错误，同样这个check方法也是很多方法用到的，如：get(int index)，set(int index, E element)等。

注释讲，删除的是非空的节点，这里的node节点也是通过node(index)获取的，分别根据当前Node得到链表上的关节要素：element、next、prev，分别对 prev 和 next 进行判断，以便对当前 list 的前后节点进行重新赋值，frist和last，最后将节点的element置为null，个数-1，操作数+1。根据以上分析，remove节点关键的变量，是Node实例本身的局部变量 next、prev、item 重新构建内部变量指针指向，以及list的局部变量first和last保证节点相连。这些变量的操作使得其删除动作也很高效。

获取指定index位置的node，获取之前还是调用checkElementIndex(index)进行检查元素，之后通过node(index)获取元素，上文有提到，node的获取是遍历得到的元素，所以相对性能效率会低一些。

Set 集合在我们日常中，用到的也比较多。用于存储不重复的元素集合，它主要提供下面几种方法：

• 将元素添加进Set<E>：add(E e)

• 将元素从Set<E>删除：remove(Object e)

• 判断是否包含元素：contains(Object e)

这几种方法返回结果都是 boolean值，即返回是否正确或成功。Set 相当于只存储key、不存储value的Map。我们经常用 Set 用于去除重复元素，因为 重复add同一个 key 时，会返回 false。

Set 子孙中主要有：HashSet、SortedSet。HashSet是无序的，因为它实现了Set接口，并没有实现SortedSet接口，而TreeSet 实现了SortedSet接口，从而保证元素是有序的。

HashSet 添加后输出也是无序的：

看到输出的顺序既不是添加的顺序，也不是String排序的顺序，在不同版本的JDK中，这个顺序也可能是不同的。

换成TreeSet：

在遍历TreeSet时，输出就是有序的，不是添加时的顺序，而是元素的排序顺序。

注意：添加的元素必须实现Comparable接口，如果没有实现Comparable接口，那么创建TreeSet时必须传入一个Comparator对象。

本文转自网络，如有侵权请及时联系我们删除。