首页 > 代码库 > 集合总结

集合总结

数组:数据在内存是连续存放的,随机访问效率很高(根据索引值就可以直接定位到具体的元素)。插入和删除效率低(重新分配、移动元素)
链表:数据在内存按需分配,随机访问效率低(必须从头或尾,顺着链接查找),插入和删除效率高。

ArrayLis,底层是动态数组(ArrayList随机访问效率很高,但插入和删除性能比较低)
    添加元素的效率还可以,重新分配和拷贝数组的开销被平摊了。
    插入和删除元素的效率比较低,因为需要移动元素。
    扩容条件:需求大小 > 数组大小 
    扩容后:原容量1.5倍


LinkedList(底层是双向链表,但是支持双端队列 (Deque)),它的特点与ArrayList几乎正好相反:(LinkedList随机访问效率很低,但插入和删除性能比较高)
    实现了Deque接口,可以作为队列、栈和双端队列使用。实现原理上,内部是一个双向链表,并维护了长度、头节点和尾节点。链表对LinkedList没有限制长度,但有可能对其他的容器限制长度


    数据结构:
        E item;
        Node<E> next;
        Node<E> prev;

    栈和队列底层实现都是链表。(此处可以看《算法》这本书94页)
    栈和队列只是双端队列的特殊情况。数据结构如下:
        栈:
            E item
            Node next
        队列:
            E item
            Node first
            E item
            Node last

    链表:增删易,查询慢(必须从头到尾,顺着链接查找,效率比较低)
         内存只需按需分配内存,插入和删除时 需要修改前驱和后继节点的链接
         
    数组:增删难(移动元素和扩容分配),查询快(元素连续存放,可以直接随机访问)
         内存需要分配额外空间,插入和删除时 需要移动所有后续元素
         

栈只操作头部,队列两端都操作(尾部只添加、头部只查看和删除)
    Queue:队列
    Deque:双向队列(里面包含了栈的操作方法)。extends Queue

链表和双向链表不是一回事,结构不一样:
    链表:item和下一个结点引用(后继)
    双向链表:item、上一个结点引用(前驱)、下一个结点引用(后继)

理解了LinkedList和ArrayList的特点,我们就能比较容易的进行选择了,如果列表长度未知,添加、删除操作比较多,尤其经常从两端进行操作,而按照索引位置访问相对比较少,则LinkedList就是比较理想的选择。

==============================================================================================================================
HashMap:底层是  数组+单向链表,数据结构如下:
    final K key;
    V value;
    HashMapEntry<K,V> next;
    int hash;

    扩容条件:size(实际键值对个数) >= 阀值( 阀值 = initialCapacity * loadFactor )
    扩容后:原容量2倍

    如何存储值:根据key计算hash值,根据hash值计算索引index,根据索引找到链表。在对应链表操作时也是先比较hash值,相同的话才用equals方法比较。

HashMap特点分析:
    HashMap实现了Map接口,内部使用数组链表和哈希的方式进行实现,这决定了它有如下特点:
        1  根据键保存和获取值的效率都很高,为O(1),每个单向链表往往只有一个或少数几个节点,根据hash值就可以直接快速定位。
        2  HashMap中的键值对没有顺序,因为hash值是随机的。



LinkedHashMap:extends HashMap ---> 所以底层是哈希表。另外还有一个就是双向链表,每个键值对既位于哈希表中,也位于这个双向链表中。
    重点是理解这里的链表,哈希表(数组+单向链表)是一个结构,双向列表是另一个结构
    双向链表数据结构如下: LinkedHashMapEntry<K,V> before, after;

    可以保持元素按 插入 或 访问 有序,这与TreeMap按 键 排序不同。
    所以LinkedHashMap支持两种顺序,一种是插入顺序,另外一种是访问顺序。
        插入顺序:先添加的在前面,后添加的在后面,修改操作不影响顺序。
        访问顺序:是指get/put操作。对一个键执行get/put操作后,其对应的键值对会移到链表 末尾,所以,最末尾的是最近访问的,最开始的是最久没被访问的,这种顺序就是访问顺序。

    LRU缓存:是一个通用的提升数据访问性能的思路,用来保存常用数据。
        特点:容量较小,但访问更快。
        缓存是相对而言的,相对的是主存,主存的容量更大、但访问更慢。
        缓存的基本假设是,数据会被多次访问,一般访问数据时,都先从缓存中找,缓存中没有再从主存中找,找到后,再放入缓存,这样,下次如果再找相同数据,访问就快了。

        替换算法:一般而言,缓存容量有限,不能无限存储所有数据,如果缓存满了,当需要存储新数据时,就需要一定的策略将一些老的数据清理出去,这个策略一般称为替换算法。LRU是一种流行的替换算法,它的全称是Least Recently Used

LinkedHashMap对容量没有限制,因为removeEldestEntry默认返回false。但它可以被子类重写,LRUCache重写了该方法并返回true,所以LRUCache有容量限制。



TreeMap:相比于HashMap它有顺序,底层是红黑树
    结构示意图:
          K key;
        V value;
        TreeMapEntry<K, V> left = null;
        TreeMapEntry<K, V> right = null;
        TreeMapEntry<K, V> parent;
        boolean color = BLACK;

排序二叉树算法:
    1  首先与根节点比较,如果相同,就找到了
    2  如果小于根节点,则到左子树中递归查找
    3  如果大于根节点,则到右子树中递归查找


如何保证按 键 顺序?
    1    键实现Comparable接口
    2    创建TreeMap时,传进去Comparator对象

 

集合总结