学习分享数据结构对比

常用数据结构特点对比 | 数据结构 | 底层实现 | 核心特点 | 典型场景 | |--------------------|--------------------|------------------------------------------------------------------------------|----------------------------------| | 数组 (Array)| 连续内存空间 | 固定大小随机访问快O(1)插入/删除需移动元素O(n) | 存储固定长度数据、快速查询场景 | | List | 接口无具体实现 | 有序、可重复、支持索引访问提供增删改查方法 | 需动态调整大小且有序存储的场景 | | ArrayList| 动态数组 | 基于数组实现查询快O(1)扩容成本高默认1.5倍非线程安全 | 频繁读取、少量插入删除的场景 | | HashMap | 数组链表/红黑树 | 键值对存储无序键唯一允许null键查询/插入/删除平均O(1)非线程安全 | 快速键值映射如缓存、统计频次 | | HashSet | 基于HashMap实现 | 元素唯一无序基于哈希值存储查询O(1)非线程安全 | 去重、快速判断元素是否存在 | | Queue | 接口无具体实现 | 先进先出FIFO仅允许在队首删除、队尾添加元素 | 任务排队、消息队列等场景 | | Deque | 接口双端队列 | 允许在两端插入/删除元素支持FIFO和LIFO栈操作 | 双端操作场景如滑动窗口 | | PriorityQueue | 堆默认小顶堆 | 元素按优先级排序默认自然顺序队首为最小/最大值插入O(log n)、查询O(1) | 任务调度、Top K问题 | 关键差异总结 - 有序性ArrayList、Queue、Deque、PriorityQueue 是有序的ArrayList按插入顺序PriorityQueue按优先级HashMap、HashSet 是无序的。 - 唯一性HashSet、HashMap 的键要求唯一List、Queue、Deque 允许重复元素。 - 线程安全以上均非线程安全需手动同步如 Collections.synchronizedList或使用并发容器如 ConcurrentHashMap。 哈希表的遍历方式取决于具体编程语言但核心逻辑是遍历键值对常见方式如下 1. 遍历所有键Keys 通过获取哈希表的所有键再逐个访问对应的值。 - Pythonfor key in hashmap.keys() - Javafor (K key : hashmap.keySet()) - JavaScriptfor (let key of Object.keys(hashmap)) 2. 遍历所有值Values 直接遍历哈希表中存储的所有值无需关注键。 - Pythonfor value in hashmap.values() - Javafor (V value : hashmap.values()) - JavaScriptfor (let value of Object.values(hashmap)) 3. 遍历键值对Key-Value Pairs 同时获取键和值适用于需要同时处理两者的场景。 - Pythonfor key, value in hashmap.items() - Javafor (Map.EntryK, V entry : hashmap.entrySet()) - JavaScriptfor (let [key, value] of Object.entries(hashmap)) 4. 迭代器遍历部分语言支持 通过迭代器顺序访问哈希表元素适合复杂逻辑控制。 - JavaIteratorMap.EntryK, V iterator hashmap.entrySet().iterator(); while (iterator.hasNext()) { ... } 注意事项 - 无序性多数哈希表如Python的dict、Java的HashMap不保证遍历顺序与插入顺序一致。若需有序可使用LinkedHashMapJava或Python 3.7的dict默认保留插入顺序。 - 并发安全遍历过程中修改哈希表可能导致异常如Java的ConcurrentModificationException需加锁或使用并发容器。