目录结构

• 1.常用数据有哪些
• 2.数据的说明
• 3.集合数据结构介绍
• 4.集合{List，Set，Map}的特点
• 5.Queue队列

1.常用数据有哪些？

• 1.1 如下图所示： 

• 1.2 常见的集合数据 

2.数据的说明

• 2.1 数组

  • 无序数组
    • 优点：查询快,如果知道索引可以快速地存取
    • 缺点：删除慢,大小固定
  • 有序数组
    • 优点：比无序数组查找快
    • 缺点：删除和插入慢，大小固定

• 2.2 栈

  • 优点：提供后进先出的存取方式
  • 缺点：存取其他项很慢
  • 比如，Android中管理activity进出就是使用栈

• 2.3 队列

  • 优点：提供先进先出的存取方式
  • 缺点：存取其他项都很慢

• 2.4 链表

  • 优点：插入快，删除快
  • 缺点：查找慢(一个个节点查)

• 2.5 二叉树

  • 优点：查找，插入，删除都快（平衡二叉树）
  • 缺点：删除算法复杂

• 2.6 红-黑树

  • 优点：查找，插入，删除都快，树总是平衡的(局部调整)
  • 缺点：算法复杂

• 2.7 哈希表

  • 优点：如果关键字已知则存取速度极快，插入快
  • 缺点：删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分

• 2.8 堆

  • 优点：插入，删除快，对最大数据的项存取很快
  • 缺点：对其他数据项存取很慢

• 2.9 图

  • 优点：对现实世界建模
  • 缺点：有些算法慢且复杂

3.集合数据结构介绍

• 3.1 Set集合【一般使用的有TreeSet和HashSet】

• 3.1.1 TreeSet

  • TreeSet是根据二叉树实现的，也就是TreeMap, 放入数据不能重复且不能为null,可以重写compareTo()方法来确定元素大小，从而进行升序排序。

• 3.1.2 HashSet

  • HashSet是根据hashCode来决定存储位置的，是通过HashMap实现的，所以对象必须实现hashCode()方法，存储的数据无序不能重复，可以存储null,但是只能存一个。

• 3.2 List集合【List比较常用的有ArrayList和LinkedList，还有一个比较类似的Vector】

• 3.2.1 ArrayList

  • 是使用动态数组来实现的，对于数据的随机get和set或是少量数据的插入或删除，效率会比较高。ArrayList是线程不安全的，在不考虑线程安全的情况下速度也比较快的。ArrayList插入数据可以重复，也是有序的，按照插入的顺序来排序。
  • 根据序号读取数据只需直接获取数组对应脚表的数据

• 3.2.2 LinkedList

  • 内部是使用链表的形式来实现的,在插入大量数据的时候效率比较快。
  • LinkedList根据序号获取数据，是二分进行遍历，如果序号小于总长度的一半，就从链表头部开始往后遍历，直到找到对应的序号。如果序号大于总长度的一半，就从链表尾部往前进行遍历，直到找到对应的序号。拿到数据。

• 3.2.3 Vector

  • Vector的使用方法和内部实现基本和ArrayList相同，只不过它在add(), remove(), get()等方法中都加了同步。所以它是线程安全的。但是使用效率上就不如ArrayList了。

4.Map集合【HashMap，TreeMap，HashTable】

• 4.1 HashMap

  • HashMap是基于散列链表来实现的，简单的来说，根据key算出一个hash值，确定一个存放index,但是hash值有可能会冲突重复，所以如果冲突的hash值就需要以链表的形式在同一个index存放了。

• 4.2 TreeMap

  • TreeMap的使用大致跟HashMap类似，但是内部实现是根据红黑树来实现的。红黑树是一种平衡有序的二叉树，TreeMap的插入删除查询都是依据红黑树的规则来进行的。

• 4.3 HashTable

  • HashMap和TreeMap都是线程不安全的，多线程操作的时候可能会造成数据错误。Hashtable是线程安全的。其他内部实现，与HashMap都是一样的。

5.Queue队列

5.1 什么是队列

• 队列是数据结构中比较重要的一种类型，它支持 FIFO，尾部添加、头部删除（先进队列的元素先出队列），跟我们生活中的排队类似。

5.2 队列的种类

• 单队列（单队列就是常见的队列, 每次添加元素时，都是添加到队尾，存在“假溢出”的问题也就是明明有位置却不能添加的情况）
• 循环队列（避免了“假溢出”的问题）

5.3 Java 集合框架中的队列 Queue

• Java 集合中的 Queue 继承自 Collection 接口 ，Deque, LinkedList, PriorityQueue, BlockingQueue 等类都实现了它。Queue 用来存放 等待处理元素 的集合，这种场景一般用于缓冲、并发访问。除了继承 Collection 接口的一些方法，Queue 还添加了额外的 添加、删除、查询操作。

赞赏支持