测试派 Give testers a home.

常用数据结构

哈希表

• 特点：
  • 一般没有容量限制，是通过对Key的哈希计算快速存储和访问指定的内容
  • 因为一般的哈希算法是把任意长度的值，生成指定长度的Key，可能会存在哈希碰撞问题
  • 碰到哈希碰撞时，会通过一个链表来存储具有相同哈希值Key的数据
  • 为了提高哈希表的访问效率，当某个哈希值的相同Key过多，比如超过8个，会使用红黑树进行存储，性能更好
  • 具体如下图
    
• 逻辑结构：根据关键码(Key)和值(Value)进行访问的数据结构
• 物理结构：通过对Key进行一个哈希算法映射到一个指定位置，这样就能很快在哈希表中找到对应元素；物理结构上结合了数组和链表进行存储
• 优点：插入、删除、查询都一个字，快
• 缺点：结构略复杂，对初学者不友好
• Java语言中的定义如下
  Map<Integer,String> data = new HashMap<>();
• 详细示例见附件中的HashMapDemo.java

树

• 特点：
  • 由1~n个有限节点组成的一种层次化的数据结构，有唯一一个根节点
  • 称之为树，是因为其结构像一颗倒挂的树，也就是根朝上，叶子朝下
  • 每个节点有0~n个子节点
  • 没有父结点的叫根节点
  • 没有子节点的叫叶子节点
  • 具体如下图，分别为树、二叉树、满二叉树
    
• 逻辑结构：由1~n个有限节点组成的一种层次化的数据结构
• 物理结构：常用的存储方式有双亲表示法(顺序存储)、孩子表示法(链表存储)、孩子兄弟表示法(链表存储)
• 优点：是一种相对有用的折中数据结构，其插入、删除元素很快，在查找方面也有很多的算法优化；其中二叉树既有链表的优点，也有数组的特性，是两者的优化方案，在处理大批量的动态数据方面非常有用
• 缺点：学习稍复杂
• 扩展：基于二叉树，还有很多扩展的应用，如平衡二叉树、红黑树、B+树等
• Java语言中一般没有直接操作树，但有一些集合类是基于树实现的；像TreeMap和TreeSet都是基于红黑树实现的，本身也是一个二叉树

堆

• 特点：
  • 是用数组实现的二叉树，没有像树一样的指针域
  • 根据"堆属性"来进行排序
  • 主要的应用有：构建优先队列、支持堆排序、快速找出一个集合中的最大值或最小值
• Java语言中没有对堆的直接操作，在应用中使用也比较少

图

• 特点：

  • 是离散数学的概念，是一些顶点的集合，并且顶点使用边连接起来，边还可以有权重
  • 广泛应用于如工作任务分解、列车运行图等方面
  • 在一个图确定后，可以使用广度优先搜索和深度优先搜索来查找两个顶点间的路径
  • 常见的场景如下图的城市关系图

  

• Java语言中没有对图的直接操作，在应用中使用需要自己构建相应数据结构

【备注：部分图片来自网络】