A_05 数据结构

By xuhang

A_05 数据结构

常用数据结构介绍

Array数组

  1. 数组存储在连续的内存上
  2. 数组的元素都是相同类型或者类型的衍生类型
  3. 数组可以直接通过下标访问

ArrayList数组

  1. 动态数组
  2. 可以存储不同类型的元素,因为ArrayList会把它的元素都当做Object来处理
  3. ArrayList是类型不安全的,有可能会在使用时发生类型不匹配的情况
  4. 会有装箱拆箱的操作

List数组

泛型数组

  1. 类型安全的
  2. 取消了装箱和拆箱操作
  3. 有Array可以快速访问的优点,也有ArrayList长度灵活变化的优点

链表LinkedList

内存不连续

优势在于插入或删除节点,无需调整结构的容量

适合元素数量不固定且需要经常增删节点的情况

栈(Stack)和队列(Queue)

队列是一种操作受限制的线性表,先进先出

栈仅允许在栈顶进行插入和删除,后进先出

哈希表、散列表(Hash Tabel)和字典(Dictionary<K,T>)

哈希表是根据 key/value 来直接进行访问的数据结构

哈希冲突

冲突避免机制:尽可能选择合适的哈希函数

冲突解决机制:

开放寻址法:

  • 最简单的一种实现就是线性探查:
  1. 当插入新的元素时,使用哈希函数在哈希表中定位元素位置

  2. 检查哈希表中该位置是否存在元素,如果为空,则插入并返回,否则进行步骤3的操作

3.如果该位置为 i ,则检查i+1是否为空,如果已被占用,则检查i+2,以此类推,直到找到一个内容为空的位置

线性探查并不是解决冲突的最好策略,因为它会导致同类哈希的聚集

  • 针对线性探查所存在的问题,一种改进的方式为二次探查,即每次检查位置空间的步长为平方倍数

Hashtable类实例的空间扩充的步骤如下:

  1. Hashtable类实例的位置空间值从当前的素数值增加到下一个最大的素数值
  2. 因为二度哈希时,Hashtable类实例中的所有元素值将依赖于Hashtable类实例的位置空间值,所以Hashtable类实例中保存的所有值也需要重新二度哈希

字典除了支持强类型外,还采用了不同的冲突解决策略,链接技术

链接技术采用额外的数据结构来处理冲突,Dictionary<K,T>中的每个位置都映射到了一个链表,当冲突发生时,冲突的元素将被添加到桶列表中

二叉树

Share: X (Twitter) Facebook LinkedIn