Java Collection（List+Set+Map）学习笔记 &附源码分析

集合框架的概述

1. 集合和数组都是对多个数据进行存储操作的结构，简称Java容器

   •  此时的存储，主要指的是内存层面的存储，不涉及到持久化的存储

2. 数组与集合

   • 数组在存储多个数据方面的特点

     • 一旦初始化后，其长度确定

     • 比如：String[] arr，int[]  一旦定义好，元素的类型也就确定了。

   • 数组缺点 ：

     • 长度不可修改

     • 数组中提供的方法非常有限，对于添加、删除。插入数据等操作，非常不便。同时效率不高

     • 获取数组中的实际元素的个数的需求，数组没有现成的属性或方法可用

     • 数组存储数据的特点：有序、可重复。对于无需、不可重复的需求。不可满足。

3. Java集合可分为Collection和Map两种体系

   • Collection接口：单列数据，定义了存取一组对象的方法的集合

     • List接口：元素有序、可重复的集合   ---->“动态”数组

       • ArrayList、LinkedList、Vector

     • Set接口：元素无需、不可重复的集合----->集合  无序、确定、互异性   去重

       • HahSet、LinkedHashSet、TreeSet

   • Map接口：双列数据，保存具有映射关系“key-value键值对”的集合   key不可重复  value可重复

     • • HashMap、LinkedHashMap、TreeMap、HashTable、Properties

 

 

1. Collection接口中的方法的使用（常用14个方法）

   • add():将元素e添加到集合中

   • size():获取添加元素的个数

   • addAll() :将另一个集合中的元素全部添加到集合中

   • isEmpty():判断当前集合是否为空

   • clear()：清空集合中所有元素

   • contains(Object obj)：返回boolean  是否包含内容  （非地址） 在判断时会调用obj对象所在类的equals()方法，要求对象重写equals（）方法

   • containsAll（Collection coll）：判断形参coll中的所有元素是否都存在于当前集合中 

   • remove(Obj o)   需要重写equals方法  从当前集合中移除obj元素 返回boolean

   • removeAll(Coll coll）从当前集合中移除coll中的所有元素

   • retainAll(Coll coll)  求两个集合的交集 返回交集赋值为当前集合

   • equals(Obj obj)  比较两个集合是否相同 

   • hashCode（） 输出当前集合的哈希值

   • 集合转换为数组  Object[] arr=coll.toArray ()

   • 数组转换为集合  Collection list=Arrays.asList(arr)         注意：数组整体可能会被当做为一个对象  new Integer[]{123,456}

   • iterator:返回Iterator 接口的示例，用于遍历集合元素

2. 集合遍历操作

   • 迭代器Iterator 

   • 

   • Iterator iterator =coll.iterator();

   • while（iterator.hasnext()）

     • iterator.next()

     • iterator.remove(),在遍历的时候，移除迭代器中的元素

             

• JDK 5.0 新增了foreach循环，用于遍历集合、数组

  • for(Object obj :coll) 

1. List接口

   • ArrayList  ：作为List接口的主要实现类，线程不安全的，效率高：底层使用Object[] elementData存储

   • LinkedList：对于频繁的插入、删除操作，效率比ArrayList高；底层使用双向链表存储

   • Vector：作为List接口的古老实现类，线程安全的，效率不高：底层使用Object[] elementData存储

     • 三个类都实现了List接口，存储数据的特点相同：有序，可重复

2. 源码分析

• ArrayList源码分析 ：

  • jdk 7.0 情况下：

    • ArrayList arr=new ArrayList（）；底层创建初始长度是10的数组

    • 扩容 1.5倍  扩容完后copyOf原来数组 Object[] elementData

    • 

    • 结论：建议开发中使用带参构造器

    • 

  • jdk 8.0 情况下

    • ArrayList arr=new ArrayList（）；底层Object[] elementData初始化为{}，并没有创建长度为的数组

    • List.add(123):第一次调用add()时，底层才创建了长度1的数组，并将数据123添加到elementData中

    • 之后的操作与jdk 1.7相同

  • 总结：

    • jdk7中的ArrayList创建类似于单例的饿汉式，而jdk8中的ArrayList对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

• LinkedList源码分析：

  • LinkedList ：数据都存在Node中  first头  last尾

  •  

  • 

  • LinkedList list=new LinkedList();内部声明了N ode类型的first和last属性，默认值为null

  • 其中Node定义为

  • 体现了LinkedList的双向链表的说法

synchronizedList(List<T> list)

    Vector源码分析：初始大小10，默认扩容二倍。

 

 

1. List接口中的常用方法

   • 

     • 返回List subList 左闭右开

   • 总结：常用方法

     • 增 ：add(Object obj)

     • 删:remove（Object obj）/remove（int index）

     • 改:set(int index,Object obj)

     • 查:get(int index)

     • 插:add(int index,Object obj)

     • 长度:size()

     • 遍历:

       • Iterator

         • 

       • 增强for循环

         • 

       • 普通循环

         • 

 

面试题：

 

remove(2)  删3// 两种可能  

• • • • Object

      • index  默认是index  无需装箱

list.remove(new Integer(2)); 删的是2

 

1. Set接口：没有额外定义新的方法，使用的都是Collection中的方法

   • HashSet：作为Set接口的主要实现类；线程不安全；可以存储null值

     • LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加顺序遍历

   • TreeSet：可以按照添加对象的指定属性进行排序。

2. Set：存储无序的、不可重复的数据

   • 以HashSet为例说明

   • 无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的HashCode决定的

   • 不可重复性：保证添加的元素按照equals()判断时，不能返回true，相同的元素只能添加一个。

3. 添加数据的过程：以HashSet为例： 散列函数--以拉链法为基础  七上八下     jdk7 新元素赋值给原来元素    jdk8 新元素再下边

   • Hash值相同则 调用equals方法  如果equals返回false则添加    返回true则不添加

   • 初始化长度为16

   • 我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(索引位置)，判断数组此位置上是否已经有元素：

     • 如果此位置上没有其他元素，则a添加成功。

       • 如果此位置上有其他元素，则比较元素a与其他元素的hash值：

         • 如果hash值不相同，则元素a添加成功

         • 如果hash值相同，进而需要调用元素a所在类的equals()方法：

           • equals返回true，元素a添加失败

           • equals返回false，元素a添加成功

   • 对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表方式存储

   • jdk7： 元素a放入数组中，指向原来的元素

   • jdk8：原来的元素在数组中，元素的last指向元素a

     • 七上八下

4. HashSet底层：数组+链表

5. 要求：向Set中添加的数据，其所在的类一定要重写equals()和hashCode(Objectobj)

   • 重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码

     • 重写两个方法的小技巧： 对象中用equals()方法比较的Field，都应该用来计算hashCode

6. LinkedHashSet的使用

   • 作为HashSet的子类，再添加数据的同时，每个数据还维护了两个引用，记录次数据前一个数据和后一个数据

   • 优点：对于频繁的遍历操作。效率高于HashSet

7. TreeSet ：

   • 向TreeSet中添加的数据，要求是相同类的对象。

   • 两种排序方式：

     • 自然排序 impl  comparable 重写compareTo

       • 按照姓名从小到大排列

       • 

       • 按照姓名从小到大排列，年龄从小到大排列

       • 

       • 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()

     • 定制排序（Comparator接口）

       • 

     • 定制排序中，比较两个对象是否相同的标准为：compare()返回0，不再是equals()

 

难题

第一次 两个

第二次 两个

第三次 三个

第四次 四个

 

1. Map接口

• Map：双列数据，存储具有key-value对的数据  ---类似于高中的函数：y=f(x)

  • HashMap：作为Map的主要实现类；线程不安全的，效率高；存储null的key和value

    • LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。

      • 原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素

        • 对于频繁的遍历操作，此类执行效率高于HashMap。

  • TreeMap：保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序。

    • 底层使用红黑树

  • Hashtable：作为古老的实现类；线程安全，效率低；不能存储null的key和value

    • Properties：常用来处理配置文件。key和value都是String类型

• HashMap的底层：数组+链表 （jdk 7及之前）

  • • • • 数组+链表+红黑树（jdk 8）

• 面试题：

  1. HashMap的底层实现原理？

  2. HashMap和Hashtable的异同？

  3. CurrentHashMap 与Hashtable的异同？

• Map中key-value的理解

  • Entry(k,v)   Map中的key：无序的、不可重复的，使用Set存储所有的key        ---->key所在的类要重写equals()和hashCode（）  以hashSet为例

    • • Map中的value：无序的，可重复的。使用Collection存储所有的value  --->value所在的类要重写equals(）

            一个key-value 构成了一个Entry对象

Map中的entry：无序的，不可重复的，使用Set存储所有的entry

• HashMap的底层实现原理？以jdk7为例

  • HashMap map=new HashMap（）;

  • 在实例化之后，底层创建了长度是16的一维数组 Entry[] table

    • 可能已经执行过多次put..

    • map.put(key1,value1):

      • 首先，调用key1所在类的hashCode()计算key1的哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。

      • 如果此位置上的数据为空，此时的key1-value1添加成功newNode

        • 

      • 如果此位置上的数据不为空（意味着此位置上存在一个或多个数据（以链表形式存在）），比较key1和已经存在的 一个或多个数据的哈希值：

        • 如果key1的哈希值与已经存在的数据哈希值都不相同，此时key1-value1添加成功。--直接填入

          • 当链表后数据元素超过8个，调用方法：判断如果数组的长度<64扩容；否则变为红黑树

          • 

          • 

            • • 不相同则p=e 继续进行for循环

            • break到

            • 替换

    • • • 如果key1的哈希值与已经存在的某个(key2-value2)数据哈希值相同，继续比较：调用key1所在类的equals(key2)方法，比较：

          • 如果equals()返回false：此时key1-value1添加成功。---尾插链表

            • 

            • 替换

          • 如果equals()返回true：使用value1替换相同key的value2值。  

    • 补充：关于情况2和情况3：此时key1-value1和原来的数据以链表方式存储

    • 在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放位置不为空）时，默认的扩容方式：扩容为原来容量的2倍，并将原油的数据复制过来。

• jdk8 相较于jdk7在底层实现方面的不同：

  • new HashMap（）：底层没有创建一个长度为16的数组

  • jdk 8底层的数组是：Node[] ，而非Entry[]

  • 首次调用put()方法时，底层创建长度为16的数组

  • jdk7的底层结构只有数组+链表。jdk8中底层结构：数组+来表+红黑树

    • 当数组的某个索引位置上的元素以链表形式存在的数据个数> 8

    • 且当前数组的长度>64时，此时索引位置上的所有数据改为红黑树存储。

• jdk 7 HashMap源码分析

• 

  • 初始默认大小16，初始负载因子0.75 

  • 临界值 16*0.75=12   影响扩容    

  • 覆盖

  • 添加

  •  大于临界值 && 存入位置当前不为空  ->扩容2倍放  （如果存入位置为空，即使大于临界值也可存入key- value）

  • “七上八下”

• jdk 8 HashMap源码分析

  • new HashMap（）：底层没有创建一个长度为16的数组

  • 

  • jdk 8底层的数组是：Node[] ，而非Entry[]

    • 

  • 首次调用put()方法时，底层创建长度为16的数组

    • 

    • 

    • 

  • jdk7的底层结构只有数组+链表。jdk8中底层结构：数组+来表+红黑树

    • 当数组的某个索引位置上的元素以链表形式存在的数据个数> 8

    • 且当前数组的长度>64时，此时索引位置上的所有数据改为红黑树存储。

 

 为什么提前扩容：

    尽量避免形成树结构，减少链表长度。  可以适当降低加载因子0.0 数组的利用率---balance---链表出现

 

 

 

 

 

 

 

面试题：

 

 

 

 

1. LinkedHahMap底层实现原理（了解）

   • • • put putVal 使用父类HashMap中的方法

   • 重写了newNode   

   • 多定义了before，after 

能够记录添加元素的先后顺序，频繁遍历可考虑使用LinkedHashMap 

 

HashSet中  定义了

静态常量对象，所有的key都指向PRESENT   对象

 

1. Map中常用的方法-以HashMap为例:

   • 添加

     • Object put(Object key,Object value):将指定的key-value添加（或修改）当前map对象中

     • void putAll(Map m):将m中所有键值对存放到当前map中

   • 删除

     • Object remove（Object key）：移除指定key的key-value对，并返回被删除key对应的value

     • void clear()：清空当前map中的所有数据 

   • 修改

     • Object put(Object key,Object value):将指定的key-value添加（或修改）当前map对象中

   • 元素查询的相关方法

     • 

   • 元视图操作方法

     • 

     • map不可用迭代器直接遍历，需要使用获取key，value或者key-value的方法

     • Map.Entry   内部有getKey和getValue方法

     • 

     • 方式二：采用value=map.get(key)遍历

 

总结：常用方法：

• TreeMap

  • 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象

  • 因为要按照key进行排序：自然排序，定制排序

• 

 

 

try+catch  =alt+shift+z

• Collections工具类  Collection（List、Set）、Map

• 接口和工具类

• 常用方法

  • 

  •  

            

 

int 出现次数=frequency(list,"stw");

• copy    需保证目的list的size>=源list的size