1 Arraylist

  • 初始化容量10，底层是Object数组。当超过容量时，会进行数组扩容，为原来的1.5倍。




  • 优化：预估初始化容量，给定一个初始化容量，减少数组扩容。（同StringBuffer）
  • 用的最多的集合ArrayList,原因：向数组末位添加元素效率不受影响，我们在检索查找某个元素的操作比较多。


2 LinkedList

底层是双向链表

3 Vector

底层是Object数组,初始容量是10，扩容时是原来的两倍

4 HashMap

  • 底层实际上是一个数组+链表，数组中每一个元素是一个单向列表。（数组和链表的结合体）key值可以为null.
  • 找到数组的下标是通过对key的地址进行hashcode()转为哈希，在对哈希值进行哈希算法得到数组下标。

  • 为什么哈希表的增删和查询效率都很高？

    增删是在链表上完成，查询也不需要都扫描，只需要部分扫描。Hashmap会先调用hashcode（确定数组下标），equals（确定元素是否相同）方法。
  • Hashmap的key无序的原因：因为不一定挂到哪个单向列表上了



  • 不可重复的原因：equals方法来保证不可重复，重复的话会把value给覆盖。

  • Hashmap集合的默认初始化容量是16，默认加载因子是0.75，两倍扩容。

    默认加载因子：当hashmap底层数组容量达到75%的时候，数组开始扩容。Hashmap初始化容量必须是2的倍数，这是因为达到散列均匀，为了提高hashmap的存取效率。

 

  • 在jdk8之后，如果哈希表的单向列表节点超过8的时候，数据结构会变成红黑树结构。当红黑树节点小于6时会自动变成单向列表。二叉树检索也会减少

5 HashTable

  • HashTable和HashMap的实现原理几乎一样，差别无非是
  • HashTable不允许key和value为null
  • HashTable是线程安全的。但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。
  • 底层也是哈希表数据结构，底层初始化容量11，加载因子0.75.扩容是二倍再加一。