数据结构与集合

写在前边：本文是个人学习笔记。（我是根据自己知识体系来做的，未必适合别人阅读）

本文整理自《码出高效：java开发手册》

目录

本文整理自《码出高效：java开发手册》

List集合

集合初始化

数组集合

集合与泛型

元素的比较：

JDK中使用的排序方法TimSort

hashCode 和 equals

fail-fast机制

Map类集合：

 

  关于树：

平衡二叉树：

二叉查找树：

红黑树：

TreeMap

HashMap

ConcurrentHashMap 

程序 = 数据结构 + 算法

 

集合框架图：

  在集合框架图中分两类，第一类是按照单个元素存储的collection，set 和 list 都是继承的collection接口，第二类是 按照key-value存储的Map。

List集合

list集合是线性数据结构的主要表现，集合元素通常明确的上一个和下一个元素，也存在明确的第一个元素和最后一个元素。

  在List体系中，最常用的也即是ArrayList 和 LinkedList 根据名字就可以看出来，两个的底层数据结构分别是数组和链表（双向链表） ，根据数据结构我们可以知道，数组是支持随机访问的，测试表明，十万数据，数组随机访问是链表的100倍。但是我们知道数组的需要的是连续的内存地址，链表可以是非连续的内存地址，但是因为链表要记录前驱后继，多以同样存一个数据，要浪费更多的空间。同样因为底层数据结构的问题，数组的插入比较麻烦，因为插在最后边还好，但是插在中间，就要将后边的数据后移，才能插入，而链表的好处是只需要修改前驱和后继就好了。所以插入删除操作比较容易快一点。但是请注意，他们都是非线程安全的。

  LinkedList  

• implements List, Deque, Cloneable, Serializable

  请注意LinkedList 具有的方法：addFirst（）添加到头结点上，add（）添加到末尾节点上，sort（null）从小到大排序。很奇怪，我拿到的api文档，没看到sort（）。但是真的能用。

  Map集合

  非线程安全，以kay-value 键值对存储，key都是唯一的，但是value可以相同。 当put相同的key的时候，会覆盖掉原来的key的value。HashTable是线程安全的，但是由于无法突破性能瓶颈，而被逐渐遗弃。想要使用线程安全的就可以使用ConcurrentHashMap。

keySet() 可以得到所有的主键； values（） 可以得到所有的值；entrySet() 可以的到所有的键值视图。 

 set集合

  set是不允许重复元素的集合类型，set体系最常用的是HashSet ，TreeSet， LinkedHashSet。相同的元素是放不进去set的。

HasHSet是使用HashMap实现的，只是将value固定为一个静态对象，使用key保证集合的唯一性，但是不保证顺序性。

LinkedHashMap是继承自HashSet，具有HashSet的优点，内部使用链表维护了插入顺序。

集合初始化

  集合初始化通常进行分配容量，设置特定参数等相关工作。分析集合的初始化及相关源码，洞悉容量分配，参数设定等相关逻辑，可以帮助我们更好的了解集合特性，提升代码质量 。

  就拿ArrayList来说，如果能在自己的预测范围之内进行初始化的话，就避免不断扩容带来的不必要的性能损失，动态数组的扩容是需要重新创建一个更大容量的数组的，并且需要将原来的内容复制到新的数组中来。如果知道JVM垃圾回收的话，频繁的new，以及回收不用的，都要造成性能的浪费。还需要知道一点，如果不指定初始话大小的话，默认是10，在第一次add的时候分配容量。后续每次扩容都会调用 Array.copyOf()

  再看一下HashMap，对于HashMap的扩容是非常影响性能的，因为要重建hash表。默认初始化是16，负载因子是0.75，这两个参数的乘积，决定可以存放的元素的个数。同样，HashMap的容量不会在new的时候分配，而是在第一次put的时候分配。我们需要知道的是，通过查看底层源码，我们会知道，即使你初始化容量了，底层会帮你找到离你最近的2的幂次方。这样做的好处是：这样的方式计算落槽位置更快。比方说，若果没有初始化，按照默认值16来，想要存1000个元素，必须扩容7次，这与指定1000相比，浪费了很多性能。

数组集合

  数组是一种顺序表，我们可以通过索引下标快速定位获取指定位置的元素。提一下为什么下标从0开始，而不是从1开始。因为需要拿下标直接进行偏移量进行运算，如果从1开始，每次都要减1，减法对于cpu来说是一种双数运算，在数组下标频繁使用的情境下，是很耗能的。

  数组分为静态初始化，和动态初始化，不管哪一种，大小一旦初始化完成都不能再改变。非线程安全。Vector线程安全，同样因为性能基本被废弃。

  args3是静态初始化，args4是动态初始化。 

  对于数组的遍历，优先推荐的是 foreach方式，其次用for循环。

  Array.asList()  可以帮我们将数组转化为集合，但是仍然是固定大小的。但是请注意：数组转化为集合时，并不能使用修改集合的相关方法，add（） remove（） clear（），都会报 不允许操作异常 。  Array.asList() 体现的是适配器模式，后台的数据仍然是原有数组。 set（）间接的对数组修改值。

  请注意 Array.asList() 装换来的 ArrayList并不是我们认识的ArrayList，想要达到我们认识的那个ArrayList还要这样做：

 

 接下来是集合转数组，

 所以不要用toArray()无参方法把集合转为数组，这样会导致泛型丢失， 如果长度不够也不行。

集合与泛型

总结一下