Java教程

Java、Android数据结构小节,终局之战

本文主要是介绍Java、Android数据结构小节,终局之战,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
     - HashMap 默认容量(16) 和扩容容量都是 2的N次方; Hashtable 的默认容量(11) 和扩容容量(2N + 1). 素数的容量设计可以减小 key 的 hash碰撞问题, 但是 2的N次方 容量设计可以更高效的获取到 key 在哈希桶的位置(Entry数组位置)
    
    - HashMap 内部对 key 的 hashCode 做了一套新的 hash 运算规则, 让高位也参与位置计算, 从而减小碰撞概率. 
    
    -  HashMap 在发生碰撞后把节点实现改为链表, 在节点链表长度超过 7 后, 把链表改为树以增加查询效率

    - https://www.cnblogs.com/xinzhao/p/5644175.html

- ConcurrentHashMap

    - 线程安全, 多线程优化的 Map 结构实现

    - 不允许 null key 和 null value

    - 其他特性同 HashMap类似

- LinkedHashMap

    - HashMap 的子类, 将结构与操作更改为链表形式, 可以保证有序性

    - accessOrder 默认fasle, 代表基于插入顺序; 修改为 true 后重写 removeEldestEntry 方法用来快速实现 lru 算法

- TreeMap
  
    - 不允许 null key 但可以 null value

    - 可以对元素进行排序, 无序集合(插入顺序和便利顺序不一致)

Collections.synchronizedMap(map); 可以使线 Map 程安全.

Map 的 key 需要具有不可变性并且重写 equals() 和 hashCode() 方法

HashMap 和 Hashtable 的底层数据结构是一个数组, 结合了顺序表和单向链表的形式,内部的每一个节点都是 Node 对象
  • Set (这部分没有用心写)

    线程不安全, 无序且元素不能重复

    底层使用了 map 进行实现(HashMap & LinkedHashMap),借用 map 的 key 不能重复的特性, 来实现不重复性

    HashSet、LinkedHashSet、TreeSet 的区别

    • 都无法保证线程安全, 底层都使用 map 实现不重复性(所以特性也在 map 中),Set 都不能使用 get(index) 的方法获取元素, 只能使用 iterator 进行获取. 其中:

      • HashSet 使用 HashMap, 无法保证有序性。

      • LinkedHashSet 使用 LinkedHashMap, 可以保证有序性

      • TreeSet 使用 NavigableMap, 可以使用 Comparator 来控制顺序

    Collections.synchronizedSet(set);可以使Set线程安全

Android 数据结构

  • SparseArray、SparseBooleanArray、SparseIntArray、SparseLongArray

    • 内部 key、value 使用数据实现, 使用 int 作为 key, 对于 Boolean、 Int 以及 Long 的额外处理也免除了 value 的装箱行为, 提升性能

    • 内部的数组采用了压缩方式表示稀疏数组, 节省内存

    • 数据的存取添加了二分查找处理,加快了处理速度

    • 添加数据时使用 append 操作性能优异, 不建议直接使用 put

    适用场景为 key 可以使用 int 类型并且数据量在千级以内(二分查找的原因)

  • LongSparseArray

    使用 long 作为 key 其他与 SparseArray 无异; 该类在 androidx.collection 包

  • ArrayMap

    • 内部使用数组实现; 数据存取添加了二分查找处理

    • 推荐在千级以下数据量情况下使用 ArrayMap 代替 HashMap

  • ArraySet

    同 ArrayMap 是 Android 对 set 的一个实现

关于我

更多Android高级面试合集放在github上面了

需要的小伙伴可以点击关于我 联系我获取

非常希望和大家一起交流 , 共同进步

这篇关于Java、Android数据结构小节,终局之战的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!