数据结构与集合

1. 数据结构

1. 数据结构是什么？
   数据结构是指逻辑意义上的数据组织方式及其相应的处理方式
2. 数据结构分类
   数据结构是算法实现的基石
   （1）线性结构：当线性结构非空时，有唯一的首元素和尾元素，线性结构包括顺序表，链表，栈，队列等，其中栈和队列是访问受限的结构，栈是后进先出，即Last-In，First-Out，简称LIFO，队列是先进先出，即First-In，First-Out，简称FIFO
   （2）树结构：树是一种非常重要的有层次的非线性数据结构，像自然界的树一样，由于树结构比较稳定和均衡，在计算机领域中得到广泛应用
   （3）图结构：图结构包括简单图，多重图，有向图和无向图等
   （4）哈希结构：哈希结构通过某种特定的哈希函数将索引与存储的值关联起来，它是一种查找效率非常高的数据结构

2. 集合框架图

Java中的集合是用于存储对象的工具类容器，它实现了常用的数据结构，提供了一系列公开的方法用于增加，删除，修改，查找和遍历数据，降低了日常开发成本，集合的种类非常多，形成了一个比较经典的继承关系树，称为Java集合框架图

如上图所示，框架图中主要分为两种：第一类是按照单个元素存储的Collection，在继承树中Set和List都实现了Collection接口，第二类是按照Key-Value存储的Map，以上两类集合体系，无论数据存取还是遍历，都存在非常大的差异

• List集合
  List集合是线性数据结构的主要实现，集合元素通常存在明确的上一个和下一个元素，也存在明确的第一个元素和最后一个元素，List集合的遍历结果是稳定的，该体系最常用的是ArrayList和LinkedList两个集合类
  ArrayList是容量可以改变的非线程安全集合，内部实现使用数组进行存储，集合扩容时会创建更大的数据空间，把原有数据复制到新数组中，ArrayList支持对元素的快速随机访问，但是插入与删除时速度通常很慢，因为这个过程很有可能需要移动其他元素
  LinkedList的本质是双向链表，与ArrayList相比，LinkedList的插入和删除速度更快，但是随机访问速度则很慢，测试表明，对于10万条的数据，与ArrayList相比，随机提取元素时存在数百倍的差距，除继承AbstractList抽象类外，LinkedList还实现了另一个接口Deque，即double-ended queue，这个接口同时具有队列和栈的性质，LinkedList包含3个重要的成员：size，first，last，size是双向链表中节点的个数，first和last分别指向第一个和最后一个节点的引用，LinkedList的优点在于可以将零散的内存单元通过附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高
• Queue集合
  Queue（队列）是一种先进先出的数据结构，队列是一种特殊的线性表，它只允许在表的一端进行获取操作，在表的另一端进行插入操作，当队列中没有元素时，称为空队列，自从BlockingQueue（阻塞队列）问世以来，队列的地位得到极大的提升，在各种高并发编程场景中，由于其本身FIFO的特性和阻塞操作的特点，经常被作为Buffer（数据缓冲区）使用
• Map集合
  Map集合是以Key-Value键值对作为存储元素实现的哈希结构，Key按某种哈希函数计算后是唯一的，Value则是可以重复的，Map类提供三种Collection视图，在集合框架图中，Map指向Collection的箭头仅表示两个类之间的依赖关系，可以使用KeySet（）查看所有的Key，使用values（）查看所有的Value，使用entrySet（）查看所有的键值对，最早用于存储键值对的Hashtable因为性能瓶颈已经被淘汰，而如今广泛使用的HashMap，线程不是安全的，ConcurrentHashMap是线程安全的，在JDK8中进行了锁的大幅度优化，体现出不错的性能，在多线程并发场景中，优先推荐使用ConcurrentHashMap，而不是HashMap，TreeMap是Key有序的Map类集合
• Set集合
  Set是不允许出现重复元素的集合类型，Set体系最常用的是HashSet，TreeSet和LinkedHashSet三个集合类，HashSet从源码分析是使用HashMap来实现的，只是Value固定为一个静态对象，使用Key保证集合元素的唯一性，但它不保证集合元素的顺序，TreeSet也是如此，从源码分析是使用TreeMap来实现的，底层为树结构，在添加新元素到集合中时，按照某种比较规则将其插入合适的位置，保证插入后的集合仍然是有序的，LinkedHashSet继承自HashSet，具有HashSet的优点，内部使用链表维护了元素插入顺序

3. 集合区别的简述

• ArrayList和Vector的区别
  这两个类都实现了List接口，都是有序集合，相当于一种动态的数组，可以按位置索引号取出某个元素，并且其中的数据可以重复
  （1）同步性：
  Vector是线程安全的，也就是说它的方法之间是线程同步的，而ArrayList是线程不安全的，而ArrayList是线程不安全的，它的方法之间是线程不同步的，如果只有一个线程会访问到集合，最好使用ArrayList，因为它不考虑线程安全，效率会比Vector高，如果有多个线程访问集合，最好使用Vector，因为它是线程安全的
  （2）数据增长：
  ArrayList与Vector都有一个初始的容量大小，当存储进它们里面的元素的个数超过了容量时，就需要增加ArrayList与Vector的存储空间，每次要增加存储空间时，不是指增加了一个存储单元，而是增加多个存储单元，每次增加的存储单元的个数在内存空间利用与程序效率之间要取得一定的平衡，Vector默认增长为原来两倍，而ArrayList的增长策略没有明确规定，从源码看到的是增长为原来的1.5倍，ArrayList和Vector都可以设置初始的空间大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法
• HashMap和HashTable的区别
  HashMap允许将null作为一个entry的key或者value，而Hashtable不允许
  Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现
  Hashtable和HashMap采用的hash/rehash算法都大概一样，所以性能不会有很大的差异
  （1）历史原因：
  Hashtable是基于陈旧的Dictionary类的，HashMap是Java1.2引进的Map接口的一个实现
  （2）同步性：
  Hashtable是线程安全的，HashMap是线程不安全的

待更新。。。