Table of Contents generated with DocToc (opens new window)

• 集合框架
  • 概述
  • Collection接口方法 :
  • 迭代器(主要用来遍历Collection接口及其实现类，而不是Map接口)
    • foreach循环(jdk5.0新增，用于遍历集合和数据)
• List接口
  • ArrayList、LinkedList和Vector的异同
  • ArrayList源码分析(JDK7、8)
  • LinkedList源码分析
  • Vector
  • List接口常用方法
  • List接口的遍历方式
• Set接口
  • HashSet
    • 重写hashCode()方法的基本原则
  • LinkedHashSet
  • TreeSet
• Map接口
  • HashMap
    • 一、HashMap的底层实现原理 (以jdk7为例说明：)
    • 二、jdk8相较于jdk7在底层实现方面的不同
    • 三、HashMap源码中的重要常量
  • Hashtable
  • LinkedHashMap
  • TreeMap
  • Properties
• Collections工具类

---

集合框架

概述

Java集合可分为Colledtion和 Map 两种体系

Collection接口:单列数据，定义了存取一组对象的方法的集合：
- List接口:元素有序、可重复的集合
	- ArrayList、LinkedList、Vector
	
- Set接口:元素无序、不可重复的集合
	- HashSet、LinkedHashSet、TreeSet
	
Map接口:双列数据，保存具有映射关系“key-value对”的集合
	- HashMap、LinkedHashMap、TreeMap、HashTable、Properties

Collection接口方法 :

Collection若储存的是自定义类的对象，需要自定义类重写equals方法

List：重写equals方法

Set(HashSet、LinkedHashSet为例)：equals、hashcode方法

​ (TreeSet为例)：排序时指定比较方式，以比较方法返回0为准判断是否相同

包含基本的增删改查抽象方法

• contains方法在判断集合中是否包含某元素时，调用的是元素的equals方法，例如：是否包含new String("xxx")时，比较的是字面值

  在判断是否包含new 自定义类(相同属性值)时，如果没有重写equals方法，均为false，重写了即为true

• remove方法同理，重写equals方法后即可

• removeAll(Collection collection)：相当于求两个集合的差集，会把调用此方法的集合中的值修改

• retainAll(Collection collection) ：相当于求两个集合的交集，也会把调用此方法的集合中的值修改

• 集合转换为数组：toArray()

• iterator()：返回Iterator接口的实例，用于遍历集合元素。

迭代器(主要用来遍历Collection接口及其实现类，而不是Map接口)

lterator对象称为迭代器(设计模式的一种)，主要用于遍历Collection集合中的元素。 GOF给迭代器模式的定义为:提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、“空姐”。

Collection接口继承了java.lang.lterable接口，该接口有一个iterator()方法，那么所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了lterator接口的对象。

lterator仅用于遍历集合，Iterator本身并不提供承装对象的能力。如果需要创建lterator对象，则必须有一个被迭代的集合。

集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。

• hasNext()方法：返回是否还有下一个元素
• next()方法：移动到下一个元素
• remove()方法：删除当前元素

注意：

lterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，不是集合对象的remove方法。

如果还未调用next()或在上一次调用next方法之后已经调用了remove方法，再调用remove都会报legalstateException。

foreach循环(jdk5.0新增，用于遍历集合和数据)

底层仍是使用iterator

使用增强for循环，修改(String s: list)中的s的值，list中的值并不会被修改，因为s是一个新的遍历，只是循环时先被赋予了list中的值，而其自身并不是list中的元素

List接口

• 鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组

• List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。

• List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。

• JDK API中List接口的实现类常用的有:ArrayList、LinkedList和Vector。

ArrayList、LinkedList和Vector的异同

同：

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

异：

• ArrayList作为List接口主要实现类，最常用，是线程不安全的，效率高；底层使用object[]存储
• LinkedList：底层使用双向链表存储，对于频繁的插入和删除操作，使用此类效率比ArrayList高
• Vector：作为List接口的古老实现类，基本不用，线程安全的，效率低；底层也使用object[]存储

ArrayList源码分析(JDK7、8)

1. JDK7：

   • ArrayList list = new ArrayList()；//底层elementData数组初始大小为10
   • 执行add()时，如果此次的添加导致底层elementData数组容量不够，则扩容。默认情况下，扩容为原来容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中

   结论：建议开发中不要使用空参构造器，指定好预计容量，避免频繁扩容

2. JDK8：

   • 底层elementData初始化为{}，并没有初始化为长度10的数组，而是第一次调用add的时候，底层才创建了长度为10的数组，并将数据加入到数组。后续的添加和扩容操作与JDK7无异

总结：JDK7中的ArrayList的对象创建类似于单例模式中的饿汉式，而JDK8中的类似于懒汉式，延迟了数组的创建，节省了内存

LinkedList源码分析

底层实现为双向链表

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

Vector

JDK7、8通过构造器创建对象时，底层都创建了长度为10的数组；在扩容方面，默认扩容为原来的数组长度的2倍

List接口常用方法

List除了从Collection集合继承的方法外，List集合里添加了一些根据索引来操作集合元素的方法。

• void add(int index, Object ele):在index位置插入ele元素
• boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
• Object get(int index):获取指定index位置的元素
• int indexOf(Object obj):返回obj在集合中首次出现的位置
• int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
• Object remove(int index):移除指定index位置的元素，并返回此元素
• Object set(int index,Object ele):设置指定index位置的元素为ele
• List subList(int fromIndex, int tolndex):返回从fromIndex到tolndex位置的左闭右开的 子集合

List接口的遍历方式

• Iterator迭代器方式
• 增强for循环
• 普通for循环

Set接口

Set接口是Collection的子接口，set接口没有提供额外的方法 Set集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set集合中，则添加操作失败。 Set判断两个对象是否相同不是使用==运算符，而是根据equals()方法

Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。

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

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

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

二、添加元素的过程：以HashSet为例：

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为:索引位置），判断数组此位置上是否已经有元素: 如果此位置上没有其他元素，则元素α添加成功。---->情况1 如果此位置上有其他元素b(或以链表形式存在的多个元素），则比较元素a与元素b的hash值: 如果hash值不相同，则元素α添加成功。---->情况2 如果hash值相同，进而需要调用元素α所在类的equals()方法: 如果equals()返回true,元素α添加失败 如果equals()返回false,则元素α添加成功。---->情况3

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

jdk 7：元素α放到数组中，指向原来的元素。 jdk 8：原来的元素在数组中，指向元素α

HashSet

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

HashSet是 Set接口的典型实现，大多数时候使用Set集合时都使用这个实现类。

HashSet按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。

HashSet具有以下特点:

1. 不能保证元素的排列顺序
2. HashSet不是线程安全的
3. 集合元素可以是null

HashSet集合判断两个元素相等的标准:两个对象通过hashCode()方法比较相等，并且两个对象的equals()方法返回值也相等。

对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode()方法，以实现对象相等规则。即:“相等的对象必须具有相等的散列码”。

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

​ 2.重写的hashCode()和equals()方法尽可能保持一致性

底层也是数组(是一个HashMap)，初始容量为16，当如果使用率超过0.75，(16*0.75=12)就会扩大容量为原来的2倍。(16扩容为32，依次为64,128.....等) 详情见HashMap源码

图示：

• jdk1.7时，是将hashCode相同，但equals不同的元素，按新的元素排在原来的位置，使用链表将原来的元素链到新元素的后面

• 而jdk1.8时，是将新的元素一直链到原来的元素的后面

重写hashCode()方法的基本原则

• 在程序运行时，同一个对象多次调用hashCode()方法应该返回相同的值
• 当两个对象的equals()方法比较返回true时，这两个对象的hashCode()方法的返回值也应相等
• 对象中用作equals()方法比较的Field，都应该用来计算hashCode值

LinkedHashSet

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

在添加数据的同时，每个数据还维护了两个引用，用于记录此数据的前后两个数据的地址，即可使得遍历"有序"；

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

TreeSet

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

向TreeSet中添加的数据应该是同一个类的对象，否则会报错。

1. 当类不是自定义对象的时候，类似Integer，String等实现了comparable接口的，可以自动排序

2. 当类为自定义类时，就会有两种排序方式：

• 自然排序：让自定义类实现comparable接口，重写compareTo方法。此时，比较两对象是否相同的标准为：compareTo()方法返回0，不再是equals()

• 使用定制排序：实现一个Comparator接口，将其作为参数构造TreeSet对象。此时，比较两对象是否相同的标准为：compare()方法返回0，不再是equals()

  @Test
      public void TreeSetTest2(){
          Comparator<Person> comparator = (o1, o2) -> {
              int compare = o1.name.compareTo(o2.name);
              if (compare!=0){
                  return compare;
              }else {
                  return Integer.compare(o1.age, o2.age);
              }
          };
          TreeSet<Person> people = new TreeSet<>(comparator);
          people.add(new Person("zdk", 20));
          people.add(new Person("wk", 19));
          people.add(new Person("wb", 20));
          people.add(new Person("zzm", 18));
          people.add(new Person("zzm", 20));
          for (Person person : people) {
              System.out.println("person = " + person);
          }
      }
  //person = Person{name='wb', age=20}
  //person = Person{name='wk', age=19}
  //person = Person{name='zdk', age=20}
  //person = Person{name='zzm', age=18}
  //person = Person{name='zzm', age=20}
  

Map接口

HashMap

• 是Map的主要实现类
• 线程不安全，效率高
• 可以存储null的key和value
• 底层：
  • 数组+链表 (jdk1.7及之前)
  • 数组+链表+红黑树 (jdk8)

一、HashMap的底层实现原理 (以jdk7为例说明：)

1. HashMap map = new HashMap();在实例化以后，底层创建了长度为16的一维数组Entry[] table

2. 在执行多次put操作后，调用map.put(key1,value1)：

   • 情况1：首先，先调用HaspMap中的hash()方法计算key1的哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置，如果此位置上的数据为空，此时的key1-value1添加成功

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

     如果key1的哈希值与已经存在的数据的key的哈希值都不相同，此时key1-value1添加成功

   • 情况3：如果key1的哈希值与已存在的某一个数据(key2-value2)的key的哈希值相同，就继续比较：

     调用key1所在类的equals()方法，比较：

     如果equals()返回false，证明两个key不同，key1-value1添加成功

     如果equals()返回true，证明两个key相同，会使用value1区替换value2

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

3. 扩容问题：当超出临界值(且要存放的位置非空)，就扩容为原来容量的2倍，并将原来的数据复制过来

二、jdk8相较于jdk7在底层实现方面的不同

1. new HashMap()时，底层没有创建一个长度为16的数组；

2. jdk8底层的数组 是：Node[]，而不是Entry[]

   static class Node<K,V> implements Map.Entry<K,V> {
           final int hash;
           final K key;
           V value;
           Node<K,V> next;
   }
   

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

4. jdk7底层结构只有：数组+链表。jdk8中变为：数组+链表+红黑树。

   当数组的某一个索引位置上的元素以链表形式存在的数据个数大于8且当前数组的长度小于64时，此时此索引位置上的所有数据改为使用红黑树存储

三、HashMap源码中的重要常量

• DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

• MAXIMUM_CAPACITY : HashMap的最大支持容量，2的30次方

• DEFAULT_LOAD_FACTOR: HashMap的默认加载因子 0.75

• TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值，转化为红黑树 ：8

• UNTREEIFY_THRESHOLD: Bucket中红黑树存储的Node小于该默认值，转化为链表：6

• MIN_TREEIFY_CAPACITY: 桶中的Node被树化时最小的hash表容量：64。(当桶中Node的数量大到需要变红黑树时，若hash表容量小于MIN_TREEIFY_CAPACITY时，此时应执行resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。)

• table: 存储元素的数组，总是2的n次幂

• entrySet: 存储具体元素的集

• size: HashMap中存储的键值对的数量

• modCount: HashMap扩容和结构改变的次数。

• threshold: 扩容的临界值，=容量*填充因子

• loadFactor: 填充因子

Hashtable

• Map的古老实现类
• 线程安全的，效率低
• 不可以存储null的key和value

LinkedHashMap

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

  原因：在原有的HashMap底层结构基础上增加了一对指针，指向前一个和后一个元素，对于频繁的遍历操作，此类的执行效率高于HashMap

  一下是LinkedHashMap中的内部类

static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

TreeMap

• 保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key 的自然排序和定制排序
• 底层使用红黑树
• 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
• 按key进行排序：自然排序、定制排序

1. 自然排序

   @Test
       public void TreeMapTest(){
           TreeMap<Person, Integer> treeMap = new TreeMap<>();
           Person zdk = new Person("zdk", 20);
           Person wk = new Person("wk", 19);
           Person wb = new Person("wb", 20);
           Person zzm = new Person("zzm", 18);
           treeMap.put(zdk,99);
           treeMap.put(wk,96);
           treeMap.put(wb,100);
           treeMap.put(zzm,98);
           System.out.println(treeMap);
       }
   

2. 定制排序

   @Test
       public void TreeMapTest1(){
           TreeMap<Person, Integer> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o1.age, o2.age));
           Person zdk = new Person("zdk", 10);
           Person wk = new Person("wk", 19);
           Person wb = new Person("wb", 15);
           Person zzm = new Person("zzm", 18);
           treeMap.put(zdk,99);
           treeMap.put(wk,96);
           treeMap.put(wb,100);
           treeMap.put(zzm,98);
           System.out.println(treeMap);
       }
   

Properties

• 是HashMap的子类，常用来处理配置文件。

• key和value都是String类型

• 存取数据时，建议使用setProperty(String key,String value)方法和getProperty(String key)方法

  

• 按文件名读取时，路径默认为项目路径，如果是多模块，则为模块路径(实例中的jdbc.properties文件放在当前模块下，而不是父项目下)

  @Test
      public void propertiesTest() throws Exception {
          Properties properties = new Properties();
          properties.load(new FileInputStream("jdbc.properties"));
          Enumeration<String> propertyNames = (Enumeration<String>) properties.propertyNames();
          while (propertyNames.hasMoreElements()){
              String element = propertyNames.nextElement();
              String property = properties.getProperty(element);
              System.out.println(element+" = " + property);
          }
      }
  

问：1. HashMap的底层实现原理？

	2. HashMap和Hashtable的异同？
	3. CurrentHashMap与Hashtable的异同？

Collections工具类

• Collections是一个操作Set、List、Map等集合的工具类
• Collections中提供了一系列静态的方法对集合元素进行排序、查询、和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法

1. 排序操作(均为static方法)

   • reverse(List)：反转List中的元素的顺序
   • shuffle(List)：对List集合元素进行随机排序
   • sort(List)：根据元素的自然顺序对指定List集合元素按升序排序
   • sort(List，Comparator)：根据指定的Comparator产生的顺序对List集合元素进行排序
   • swap(List，int，int)：将指定list集合中的i处元素和j处元素进行交换
   • Object max(Collection):根据元素的自然顺序，返回给定集合中的最大元素
   • Object max(Collection，Comparator):根据Comparator指定的顺序，返回给定集合中的最大元素
   • Object min(collection)
   • Object min(collection，Comparator)
   • int frequency(collection，object):返回指定集合中指定元素的出现次数
   • void copy(list dest,List src):将src中的内容复制到dest中
   • boolean replaceAll(List list,object oldVal，object newVal):使用新值替换List对

   注意：在使用copy()方法时，首先需要将目标集合的size填充到大于等于源集合的size

   一般使用：List dest = Arrays.asList(new Object[list.size()]);

2. 同步控制

   Collections类中提供了多个synchronizedXxx()方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题