A_05 数据结构
常用数据结构介绍
Array数组
- 数组存储在连续的内存上
- 数组的元素都是相同类型或者类型的衍生类型
- 数组可以直接通过下标访问
ArrayList数组
- 动态数组
- 可以存储不同类型的元素,因为ArrayList会把它的元素都当做Object来处理
- ArrayList是类型不安全的,有可能会在使用时发生类型不匹配的情况
- 会有装箱拆箱的操作
List数组
泛型数组
- 类型安全的
- 取消了装箱和拆箱操作
- 有Array可以快速访问的优点,也有ArrayList长度灵活变化的优点
链表LinkedList
内存不连续
优势在于插入或删除节点,无需调整结构的容量
适合元素数量不固定且需要经常增删节点的情况
栈(Stack)和队列(Queue)
队列是一种操作受限制的线性表,先进先出
栈仅允许在栈顶进行插入和删除,后进先出
哈希表、散列表(Hash Tabel)和字典(Dictionary<K,T>)
哈希表是根据 key/value 来直接进行访问的数据结构
哈希冲突
冲突避免机制:尽可能选择合适的哈希函数
冲突解决机制:
开放寻址法:
- 最简单的一种实现就是线性探查:
-
当插入新的元素时,使用哈希函数在哈希表中定位元素位置
-
检查哈希表中该位置是否存在元素,如果为空,则插入并返回,否则进行步骤3的操作
3.如果该位置为 i ,则检查i+1是否为空,如果已被占用,则检查i+2,以此类推,直到找到一个内容为空的位置
线性探查并不是解决冲突的最好策略,因为它会导致同类哈希的聚集
- 针对线性探查所存在的问题,一种改进的方式为二次探查,即每次检查位置空间的步长为平方倍数
Hashtable类实例的空间扩充的步骤如下:
- Hashtable类实例的位置空间值从当前的素数值增加到下一个最大的素数值
- 因为二度哈希时,Hashtable类实例中的所有元素值将依赖于Hashtable类实例的位置空间值,所以Hashtable类实例中保存的所有值也需要重新二度哈希
字典除了支持强类型外,还采用了不同的冲突解决策略,链接技术
链接技术采用额外的数据结构来处理冲突,Dictionary<K,T>中的每个位置都映射到了一个链表,当冲突发生时,冲突的元素将被添加到桶列表中