美文网首页
Java集合框架

Java集合框架

作者: laowangv2 | 来源:发表于2021-01-12 23:24 被阅读0次

    常见的数据结构

    1. 线性表
      • 数组
      • 链表
    2. 栈与队列
    3. 散列表

    顶层接口

    Collection和Map


    集合框架图 from https://www.jianshu.com/p/63e76826e852

    Collection

    三个子接口:List、Set、Queue

    List,对应线性表

    • ArrayList,对应数组
    • LinkedList,对应链表

    Set

    • HashSet
    • LinkedHashSet
      插入序
    • TreeSet

    Stack和Queue

    • Stack
      继承自Vector,如java doc所言,如果需要栈这种结构,可以使用Deque的实现类

    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
    Deque<Integer> stack = new ArrayDeque<Integer>();

    • Queue
      队列接口,offer-poll,add-remove,后者失败throws,前者返回null或false。element和peek,前者失败throws,后者null
    • Deque
      继承Queue(头插头出),扩展了从另一端操作队列(头插尾插,头出尾出)的功能,也就拥有了作为stack使用的能力,实现类包括ArrayDeque和LinkedList,对应队列的数组实现和链表实现。

    Map

    • HashMap,对应散列表

      1. 数组+链表实现,1.8之后链表长度大于8会转为红黑树,优化查询效率
      2. 长度length为2的幂次方,可以使得
        hash % length = hash & (length - 1)
        成立,于是可以使用二进制运算&来提升计算效率
      3. 多线程死循环
        并发rehash导致链表成环,1.8修复了这个问题。不过本来HashMap也不是并发安全的,0202年了,不会还有人问怎么成环吧,那也太low了
        疫苗:JAVA HASHMAP的死循环
    • TreeMap,对应红黑树
      遍历有序,实现接口如下图。主要的是SortedMap和NavigableMap,一个提供了排序能力,一个提供了搜索能力(如lowEntry,小于指定key的最大的entry),navigable的意思是可导航的。


      TreeMap类图
    • LinkedHashMap
      HashMap+LinkedList
      继承自HashMap,同时维护头尾链表节点(双向,1.8),每个插入的节点都会拼到尾部。自带lru特性,访问后会调整到尾部,插入后会删除eldest(实现removeEldestEntry即可)

    补充

    1. ConcurrentHashMap
      将哈希桶分配在若干Segment(继承自ReetrantLock)下,依靠分段锁实现线程安全
      1.8之后取消了Segment的设计,直接锁HashMap的桶

    相关文章

      网友评论

          本文标题:Java集合框架

          本文链接:https://www.haomeiwen.com/subject/oswjaktx.html