Java中常见数据结构：list与map -底层如何实现详解编程语言

1:集合 
    Collection(单列集合) 
        List(有序,可重复) 
            ArrayList 
                底层数据结构是数组,查询快,增删慢 
                线程不安全,效率高 
            Vector 
                底层数据结构是数组,查询快,增删慢 
                线程安全,效率低 
            LinkedList 
                底层数据结构是链表,查询慢,增删快 
                线程不安全,效率高 
        Set(无序,唯一) 
            HashSet 
                底层数据结构是哈希表。 
                哈希表依赖两个方法：hashCode()和equals() 
                执行顺序： 
                    首先判断hashCode()值是否相同 
                        是：继续执行equals(),看其返回值 
                            是true:说明元素重复，不添加 
                            是false:就直接添加到集合 
                        否：就直接添加到集合 
                最终： 
                    自动生成hashCode()和equals()即可 
                     
                LinkedHashSet 
                    底层数据结构由链表和哈希表组成。 
                    由链表保证元素有序。 
                    由哈希表保证元素唯一。 
            TreeSet 
                底层数据结构是红黑树。(是一种自平衡的二叉树) 
                如何保证元素唯一性呢? 
                    根据比较的返回值是否是0来决定 
                如何保证元素的排序呢? 
                    两种方式 
                        自然排序(元素具备比较性) 
                            让元素所属的类实现Comparable接口 
                        比较器排序(集合具备比较性) 
                            让集合接收一个Comparator的实现类对象 
    Map(双列集合) 
        A:Map集合的数据结构仅仅针对键有效，与值无关。 
        B:存储的是键值对形式的元素，键唯一，值可重复。 
         
        HashMap 
            底层数据结构是哈希表。线程不安全，效率高 
                哈希表依赖两个方法：hashCode()和equals() 
                执行顺序： 
                    首先判断hashCode()值是否相同 
                        是：继续执行equals(),看其返回值 
                            是true:说明元素重复，不添加 
                            是false:就直接添加到集合 
                        否：就直接添加到集合 
                最终： 
                    自动生成hashCode()和equals()即可 
            LinkedHashMap 
                底层数据结构由链表和哈希表组成。 
                    由链表保证元素有序。 
                    由哈希表保证元素唯一。 
        Hashtable 
            底层数据结构是哈希表。线程安全，效率低 
                哈希表依赖两个方法：hashCode()和equals() 
                执行顺序： 
                    首先判断hashCode()值是否相同 
                        是：继续执行equals(),看其返回值 
                            是true:说明元素重复，不添加 
                            是false:就直接添加到集合 
                        否：就直接添加到集合 
                最终： 
                    自动生成hashCode()和equals()即可 
        TreeMap 
            底层数据结构是红黑树。(是一种自平衡的二叉树) 
                如何保证元素唯一性呢? 
                    根据比较的返回值是否是0来决定 
                如何保证元素的排序呢? 
                    两种方式 
                        自然排序(元素具备比较性) 
                            让元素所属的类实现Comparable接口 
                        比较器排序(集合具备比较性) 
                            让集合接收一个Comparator的实现类对象 
     
2.关于集合选取原则 
     
    是否是键值对象形式: 
        是：Map 
            键是否需要排序: 
                是：TreeMap 
                否：HashMap 
            不知道，就使用HashMap。 
             
        否：Collection 
            元素是否唯一: 
                是：Set 
                    元素是否需要排序: 
                        是：TreeSet 
                        否：HashSet 
                    不知道，就使用HashSet 
                     
                否：List 
                    要安全吗: 
                        是：Vector 
                        否：ArrayList或者LinkedList 
                            增删多：LinkedList 
                            查询多：ArrayList 
                        不知道，就使用ArrayList 
            不知道，就使用ArrayList 
             
3:集合的常见方法及遍历方式 
    Collection: 
        add() 
        remove() 
        contains() 
        iterator() 
        size() 
         
        遍历： 
            增强for 
            迭代器 
             
        |--List 
            get() 
             
            遍历： 
                普通for 
        |--Set 
     
    Map: 
        put() 
        remove() 
        containskey(),containsValue() 
        keySet() 
        get() 
        value() 
        entrySet() 
        size() 
         
        遍历： 
            根据键找值 
            根据键值对对象分别找键和值