Java数据结构实现及效率

• List
• • ArrayList
  • LinkedList
• Set
• • HashSet
  • TreeSet
  • LinkedHashSet
• Map
• • TreeMap
  • LinkedHashMap

List

ArrayList

都是线性表

• 元素在内存连续存放，每个元素占用内存相同
• 可以通过下标快速访问数组中的任何元素
• 数组增删需要移动大量元素
• 必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
• 数组（静态）从栈中分配空间

效率：
寻找元素：O( 1 )
增删元素：O( n )
Arraylist 可增长的数组长度 查询快 get（） set（） 常数级
插入和现有所有项的删除代价昂贵 除非在表的末端

ArrayList 是线性表（数组）
get() 直接读取第几个下标，复杂度 O(1)
add(E) 添加元素，直接在后面添加，复杂度O（1）
add(index, E) 添加元素，在第几个元素后面插入，后面的元素需要向后移动，复杂度O（n）
remove（）删除元素，后面的元素需要逐个移动，复杂度O（n）

总结：查 O（1） 增 末尾0（1）中间0（n） 删0（n）
移动是消耗时间复杂度的

LinkedList

• 元素非顺序存储，通过元素的指针联系到一起
• 访问元素需要从链表的第一个元素开始一直找到需要的元素
• 增删简单，只需要修改元素的指针即可
• 链表动态地进行存储分配，可以适应数据动态地增减的情况
• 链表（动态）从堆中分配空间

效率：
寻找元素：O( n )
增删元素：O( 1 )

get() 获取第几个元素，依次遍历，复杂度O(n)
add(E) 添加到末尾，复杂度O(1)
add(index, E) 添加第几个元素后，需要先查找到第几个元素，直接指针指向操作，复杂度O(n)
remove（）删除元素，直接指针指向操作，复杂度O(1)

总结：查 O（n） 增 末尾O（1）中间O（n） 删O（1）

Set

HashSet底层数据结构采用的是哈希表，元素无序（即不保证元素的排列顺序不会发生改变）且不可重复。
效率：
增删元素：O( n )
获取set元素，需要调用iterator方法，返回的元素无序，因此需要遍历集合，时间复杂度O(N)，效率低下
添加set元素，调用add方法，底层实际上是调用HashMap的put()方法添加key-value对，时间复杂度O(1)，因此效率高
移除set元素，调用remove方法，底层实际上是调用HashMap的remove方法删除指定Entry，时间复杂度是O(1)，因此效率高

Set集合有三个常见的实现类：HashSet，TreeSet，LinkedHashSet。
简单的说，如果你关注性能，应该使用HashSet；
如果你需要一个有序的Set集合，应该使用TreeSet；
如果你需要一个Set集合保存了原始的元素插入顺序，应该使用LinkedHashSet。

HashSet

基于散列表实现的，元素没有顺序；add、remove、contains方法的时间复杂度为O(1)。(contains为false时，就直接往集合里存)
总结：查 O（1） 增 O（1） 删O（1）

TreeSet

基于树实现的（红黑树），元素是有序的；add、remove、contains方法的时间复杂度为O(log (n))(contains为false时，插入前需要重新排序)。

总结：查 O（log n） 增 O（log n） 删O（log n）
因为元素是有序的，它提供了若干个相关方法如first(), last(), headSet(), tailSet()等；

LinkedHashSet

介于HashSet和TreeSet之间，是基于哈希表和链表实现的，支持元素的插入顺序；基本方法的时间复杂度为O(1)；

总结：查 O（1） 增 O（1） 删O（1）

Map

TreeMap

基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。正常是O(1)到O（n） jdk1.8添加了 红黑树 是 O（log n）

TreeMapget操作的时间复杂度是O(log(n))的，相比于HashMap的O(1)还是差不少的。

LinkedHashMap

出现就是为了平衡这些因素，能以O(1)时间复杂度查找元素，又能够保证key的有序性