数据结构是计算机存储, 组织数据的方式. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合. 通常情况下, 精心选择的数据结构可以带来更高的运行或存储效率. 数据结构往往同高效的检索算法和索引技术有关
java 中常见的几种数据结构 (也是初级工程师常见面试题) 主要是一些常见的容器, 它们主要来自于 Collection 和 Map 这 2 个集合; 以下是 2 个集合的总体框架
(1)Collection 接口图
(2)map 接口图
上述 2 个图片分别来自于
- http://www.cnblogs.com/nayitian/p/3266090.html
- https://www.cnblogs.com/nayitian/p/3267110.html
下面我将每一个接口或类进行详细介绍, 其中他们所拥有的方法就不介绍了, 可以自行查 API, 另外, 很多方法也不会用到, 常见的方法就那么几个.
1.Collction:
Collection 接口继承自超级接口 Iterator, 是 Collection 层次结构中的根接口. Collection 表示一组对象, 这些对象也被称为 Collection 的元素. 一些 Collection 允许有重复的元素(例如 List), 但是另一些则不允许有重复的元素, 即可为无序的(如 Set).JDK 不提供此接口的任何直接实现 --- 它会提供更为具体的子接口(如 Set 和 List), 这从上面的 UML 也可以看出来. 此接口用来传递 Collection, 并在需要最大普遍性的地方操作这些 Collection. 其实现类的底层是由数组或者链表组成, 数组是通过首地址 +(元素长度*下标), 即通过下标查询的, 因此查询速度快, 而增删慢(在增删的时候, 数组需要整体的移动, 所以慢); 链表不维护序号, 即链表不存在下标的概念,** 所以查询很慢(通过地址查询的), 而增删快(直接通过地址删掉某一个元素, 其它元素不需要移动) 数组: 查询快, 增删慢; 链表: 查询慢, 增删快
1.1.List: 有序, 可重复
ArrayList : 底层是数组结构, 线程不安全. 查询快, 增删慢
LinkedList : 底层是链表结构, 线程不安全. 查询慢, 增删快
Vector: 底层是数组结构, 是线程安全的, 所以效率很低, 已经被 ArrayList 取代
1.2.Set : 无序, 不可重复
HashSet 类 及其实现类 LinkedHashSet: 底层是使用了哈希表来支持的, 特点: 存取速度快, 线程不安全, 集合元素允许为 NULL
SortedSet 接口及其实现类 TreeSet: 如果元素具备自然顺序 的特性, 那么就按照元素自然顺序的特性进行排序存储.
1.3.EnumSet
EnumSet 类是专为枚举类设计的集合类, EnumSet 中的所有元素都必须是指定枚举类型的枚举值
2.Map
Map 用于保存具有映射关系的数据, 因此 Map 集合里保存着两组值, 一组值用于保存 Map 里的 key, 另外一组用于保存 Map 里的 value,key 和 value 都是可以任意引用类型的数据. Map 的 key 不允许重复, 即同一个 Map 对象的任何两个 key 通过 equals 方法比较总是返回 false. 给 key-value 起个名字: Entry, 表示一个键值对, 对应 Map 的一个实体; 把 Entry 放到集合 set 中就是一个 Map 如果把 Map 所有 value 放在一起来看, 元素与元素之间可以重复, 每个元素可以根据索引来查找, 相当于 list 集合, 只是 Map 中的索引不再使用整数值, 而是以另外一个对象作为索引. 如果需要从 List 集合中取出元素, 需要提供该元素的数字索引. 如果需要从 Map 中取出元素, 需要提供该元素的 key 索引, 因此, Map 也被称为字典.
常见的实现类:
2.1.HashMap:
采用哈希表算法, 此时 Map 中的 key 不会保证添加的先后顺序, key 也不允许重复. key 判断重复的标准是: key1 和 key2 是否 equals 为 true, 并且与 hashCode 相等. 其中实现类 LinkedHashMap 采用了链表和哈希表算法
2.2.TreeMap:
sortedMap 接口的实现类, 采用红黑树算法, 此时 Map 中的 key 会按照自然顺序或定制排序进行排序,,key 也不允许重复. key 判断重复的标准是: compareTo/compare 的返回值是否为 0.
2.3.Hashtable:
采用哈希表算法, 是 HashMap 的前身(类似于 Vector 是 ArrayList 的前身). 打死不用. 在 Java 的集合框架之前, 表示映射关系就使用 Hashtable. 所有的方法都使用 synchronized 修饰符, 线程安全的, 但是性能相对 HashMap 较低. 其子类 Properties 要求 key 和 value 都是 String 类型.
本文摘自:
- https://www.jianshu.com/p/b878a4e1c762
- http://www.cnblogs.com/nayitian/p/3266090.html
- https://www.cnblogs.com/nayitian/p/3267110.html
- https://www.cnblogs.com/dz-boss/p/10259743.html
来源: https://juejin.im/post/5c75eef6518825347a561ba2