java集合和泛型(一)---集合篇

集合

写在前面：

一直对java集合久仰大名，但却不太知道java语言中的集合究竟是什么？究竟是为了解决什么问题设计的？

翻阅《Java核心技术卷一：基础知识》，我们知道，java集合是实现对传统数据结构封装的类库，便于我们更加方便地使用传统数据结构进行软件开发，而不用去关注底层数据结构的具体实现，(当然如果你像我一样准备面试的话还是要了解的)，属于是一种黑盒，同时由于java设计者的高超水平，还为我们提供了一系列方便易用的方法实现基本操作，这也是java类库如此吸引人的一个原因。

只想简单的使用集合CRUD是非常简单易学的，本文试图在韩顺平老师的讲解下总结设计底层源码的知识，也会不断完善和补充。

引言：

简单地来说，数组也是一个集合，但是数组和集合又有什么区别呢？集合有什么特点呢？

首先：

• 数组是固定长度的；集合可变长度的。
• 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
• 数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。

集合的特点为：

• 对象封装数据，对象多了也需要存储。集合用于存储对象。
• 对象的个数确定可以使用数组，对象的个数不确定的可以用集合。因为集合是可变长度的。

由以上两点我们可以知道集合框架中存储的都是引用对象，也就是Object类及其子类，故我们的基本数据类型在集合中要使用对应的封装类。

使用集合框架的好处:

1. 容量自增长；
2. 提供了高性能的数据结构和算法，使编码更轻松，提高了程序速度和质量；
3. 允许不同 API 之间的互操作，API之间可以来回传递集合；
4. 可以方便地扩展或改写集合，提高代码复用性和可操作性。
5. 通过使用JDK自带的集合类，可以降低代码维护和学习新API成本。

框架体系：

本文整理自韩顺平老师的集合专题,强推一手。

本图还需补充的常见集合为：ConcurrentHashMap…

单列集合（Collection）：

双列集合（Map）：K-V

Collection接口和常用方法

为了避免本文过于冗杂，接口的常用方法参考jdk1.8的官网API文档.

Collection接口常用方法列举：

操作元素方法

1. add：添加单个元素
2. remove：删除指定元素
3. contains：查找元素是否存在
4. size：获取元素个数
5. isEmpty：判断是否为空
6. clear：清空
7. addAll：添加多个元素
8. containsAll：查找多个元素是否都存在
9. removeAll：删除多个元素

重点说明一下遍历方式。

Iterator对象称为迭代器，主要用于遍历Collection集合中的元素，如图可见Collection接口下的子接口都实现了Iterator。

执行效果如下；

我们通常不使用此方式遍历集合，因为增强for循环（for-each），就是简化版的iterator，本质一样。

for(Object obj: col){
    System.out.println(obj);
}

List接口

一个有序（元素存入集合的顺序和取出的顺序一致）的容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

常用方法同样建议查阅官方文档，可使用iterator，增强for，普通for遍历。

ArrayList底层机制和源码分析

ArrayList中可以加入重复元素，可以加入null（同样可多个），是由数组实现数据存储的，线程不安全，多线程情况下不建议使用，但执行效率高，非常常用。

ArrayList底层操作机制源码分析：

结论：

• ArrayList中维护了一个Object类型的数组elementData。

transient Object[] elementData;

• 当创建ArrayList对象时，如果使用的是无参构造器，则初始化数组容量为0，第一次添加则扩容elementData为10，如果需要再次扩容，则扩容elementData为1.5倍。
• 如果使用的是指定大小的构造器，则初始化为指定大小，需要扩容则扩容为1.5倍。

强烈建议自己debug一遍创建和扩容的源码

注意：扩容1.5倍使用的是如下代码。

int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);

Vector注意事项和源码解读

底层也是一个数组，但是Vector是线程安全的，该类的操作方法都带有synchronized关键字，考虑线程同步安全时，可以考虑使用。（基本废弃

Vector扩容机制底层源码：

机制如下：

如果是使用无参构造，默认按10，当数组容量满了之后，按二倍扩容；

指定大小的构造器，满了按照二倍扩容。

//1. new Vector() 底层
        /*
            public Vector() {
                this(10);
            }
         补充：如果是  Vector vector = new Vector(8);
            走的方法:
            public Vector(int initialCapacity) {
                this(initialCapacity, 0);
            }
         2. vector.add(i)
         2.1  //下面这个方法就添加数据到vector集合
            public synchronized boolean add(E e) {
                modCount++;
                ensureCapacityHelper(elementCount + 1);
                elementData[elementCount++] = e;
                return true;
            }
          2.2  //确定是否需要扩容条件 ： minCapacity - elementData.length>0
            private void ensureCapacityHelper(int minCapacity) {
                // overflow-conscious code
                if (minCapacity - elementData.length > 0)
                    grow(minCapacity);
            }
          2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法
              //newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);
              
              //就是扩容两倍.
            private void grow(int minCapacity) {
                // overflow-conscious code
                int oldCapacity = elementData.length;
                int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                                 capacityIncrement : oldCapacity);
                if (newCapacity - minCapacity < 0)
                    newCapacity = minCapacity;
                if (newCapacity - MAX_ARRAY_SIZE > 0)
                    newCapacity = hugeCapacity(minCapacity);
                elementData = Arrays.copyOf(elementData, newCapacity);
            }

注意：扩容的算法

newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);

在扩容的时候，capacityIncrement是0，newCapacity=oldCapacity+oldCapacity,就是两倍。

比较ArrayList&Vector:

LinkedList源码解读

LinkedList底层是双向链表，实现了双端队列的特点，可以添加任意元素，包括null，线程不安全。

• LinkedList维护了两个属性first和last分别指向头节点和尾节点。

• 每个节点里面维护了prev,next,item属性，prev指向前一个，next指向后一个，item存储数据，最终实现双向链表。

• 添加删除效率较高。

LinkedList源码解读：

创建、添加、删除

/* 	   1. LinkedList linkedList = new LinkedList();
             public LinkedList() {}
          2. 这时 linkeList 的属性 first = null  last = null
          3. 执行 添加
              public boolean add(E e) {
                   linkLast(e);
                   return true;
               }
           4.将新的结点，加入到双向链表的最后
            void linkLast(E e) {
               final Node<E> l = last;
               final Node<E> newNode = new Node<>(l, e, null);
               last = newNode;
               if (l == null)
                   first = newNode;
               else
                   l.next = newNode;
               size++;
               modCount++;
           }
           

/*linkedList.remove(); // 这里默认删除的是第一个结点
          1. 执行 removeFirst
            public E remove() {
                return removeFirst();
            }
         2. 执行
            public E removeFirst() {
                final Node<E> f = first;
                if (f == null)
                    throw new NoSuchElementException();
                return unlinkFirst(f);
            }
          3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉
            private E unlinkFirst(Node<E> f) {
                // assert f == first && f != null;
                final E element = f.item;
                final Node<E> next = f.next;
                f.item = null;
                f.next = null; // help GC
                first = next;
                if (next == null)
                    last = null;
                else
                    next.prev = null;
                size--;
                modCount++;
                return element;
            }
         */

ArrayList和LinkedList比较：

Set接口

一个无序（存入和取出顺序有可能不一致）（但是取出顺序是固定的）的容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

Set接口是Collection的子接口，所以常用方法和Collection一样，遍历方式也一样，不再能使用索引获取。

HashSet(底层HashMap，重点!)底层机制说明

HashSet实现了Set接口，底层实际上是HashMap，可以存放但只能有一个null，不保证元素有序，取hash后决定索引，即无法保证存放元素顺序和取出一致，不可有重复对象。

底层引入：

1.HashSet构造器和添加：

//1. 构造器走的源码
        /*
            public HashSet() {
                map = new HashMap<>();
            }
         2. HashSet 可以存放null ,但是只能有一个null,即元素不能重复
         */
        Set hashSet = new HashSet();
        hashSet.add(null);
        hashSet.add(null);
        System.out.println("hashSet=" + hashSet);

输出：

2.一个练习：

public class HashSet01 {
    public static void main(String[] args) {
        HashSet set = new HashSet();

        //说明
        //1. 在执行add方法后，会返回一个boolean值
        //2. 如果添加成功，返回 true, 否则返回false
        //3. 可以通过 remove 指定删除哪个对象
        System.out.println(set.add("john"));//T
        System.out.println(set.add("lucy"));//T
        System.out.println(set.add("john"));//F
        System.out.println(set.add("jack"));//T
        System.out.println(set.add("Rose"));//T


        set.remove("john");
        System.out.println("set=" + set);//3个

        //
        set  = new HashSet();
        System.out.println("set=" + set);//0
        //4 Hashset 不能添加相同的元素/数据?
        set.add("lucy");//添加成功
        set.add("lucy");//加入不了
        set.add(new Dog("tom"));//OK
        set.add(new Dog("tom"));//Ok
        System.out.println("set=" + set);

        //在加深一下. 非常经典的面试题.
        //看源码，做分析， 先给小伙伴留一个坑，以后讲完源码，你就了然
        //去看他的源码，即 add 到底发生了什么?=> 底层机制.
        set.add(new String("hsp"));//ok
        set.add(new String("hsp"));//加入不了.
        System.out.println("set=" + set);


    }
}
class Dog { //定义了Dog类
    private String name;

    public Dog(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                '}';
    }
}

输出：

值得思考的地方：

set.add(new Dog("tom"));//OK
set.add(new Dog("tom"));//Ok

set.add(new String("hsp"));//ok
set.add(new String("hsp"));//加入不了.

HashSet底层机制说明：

HashMap底层是：数组+链表+红黑树

分析添加元素底层是如何实现的：

先说结论：

• HashSet底层是一个HashMap
• 添加一个元素时，先得到hash值，会转化成（不是直接拿哈希值）索引值。
• 找到存储数据表table，看这个索引位置是否有已经存放的元素
• 没有直接加入
• 如果有，调用equals比较，如果相同，舍弃；不同则添加到最后
• Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认值是8)，并且table的大小到达了MIN_TREEIFY_CAPACITY(默认64)，就会进行树化，成为一棵红黑树。

源码分析：

public class HashSetSource {
    public static void main(String[] args) {

        HashSet hashSet = new HashSet();
        hashSet.add("java");//到此位置，第1次add分析完毕.
        hashSet.add("php");//到此位置，第2次add分析完毕
        hashSet.add("java");
        System.out.println("set=" + hashSet);
    }
}

代码十分简洁，简单的添加通过debug方式查看底层复杂的源码运行机制。

1.执行 HashSet()

此处明确了HashSet()底层就是一个HashMap.

public HashSet() {
    map = new HashMap<>();
}

2.执行 add()

public boolean add(E e) {//e = "java"
        return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();
   }

此处PRESENT，由于HashMap是存储键值对类型的集合，此处的HashSet只用到key,所以Value部分都用一个PRESENT对象来占位。

3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值

算法h = key.hashCode() ^ (h >>> 16)

public V put(K key, V value) {//key = "java" value = PRESENT 共享
       return putVal(hash(key), key, value, false, true);
   }

4.执行 putVal()：重点难点！

putVal()代码底层如下：视频讲解

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i;//定义了辅助变量
                //table 就是 HashMap 的一个数组，类型是 Node[]
                //if 语句表示如果当前table 是null, 或者 大小=0
                //就是第一次扩容，到16个空间.
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;

                //(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置
                //并把这个位置的对象，赋给 p
                //(2)判断p 是否为null
                //(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)
                //(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)

                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    //一个开发技巧提示： 在需要局部变量(辅助变量)时候，再创建
                    Node<K,V> e; K k;
                    //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
                    //并且满足 下面两个条件之一:
                    //(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象
                    //(2)  p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同
                    //就不能加入
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    //再判断 p 是不是一颗红黑树,
                    //如果是一颗红黑树，就调用 putTreeVal , 来进行添加
                    else if (p instanceof TreeNode)
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {
                       //如果table对应索引位置，已经是一个链表, 就使用for循环比较
                       //(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
                       //    注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点
                       //    , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
                       //    注意，在转成红黑树时，要进行判断, 判断条件
            //    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                      //            resize();
                      //    如果上面条件成立，先table扩容.
                      //    只有上面条件不成立时，才进行转成红黑树
                      //(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接break

                        for (int binCount = 0; ; ++binCount) {//死循环：只有两种情况break，一个是加入链表尾部break，一个是发现重复break
                            if ((e = p.next) == null) {//上面已经和第一个元素比较过了，现在只需要和下一个元素比较就可以，为空就直接加入链表尾部
                                p.next = newNode(hash, key, value, null);
                                //binCount是从0开始的，到达7就已经8个了，所以TREEIFY_THRESHOLD(8) - 1
                               if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash &&
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value;
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;
                //size 就是我们每加入一个结点Node(k,v,h,next), size++
                if (++size > threshold)
                    resize();//扩容
                afterNodeInsertion(evict);
                return null;
            }
         */

分析HashSet扩容和转化成红黑树的机制：

先说结论：

• HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值（threshold）是 16*加载因子（loadFactor固定是0.75）= 12
• 如果table数组使用到临界值12，就会扩容到 16*2 = 32，新的threshold=32*0.75 = 24,以此类推
• Java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认值是8)，并且table的大小到达了MIN_TREEIFY_CAPACITY(默认64)，就会进行树化，成为一棵红黑树；否则仍然采用数组扩容机制。

@SuppressWarnings({"all"})
public class HashSetIncrement {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
//        for(int i = 1; i <= 100; i++) {
//            hashSet.add(i);//1,2,3,4,5...100
//        }
        
//        for(int i = 1; i <= 12; i++) {
//            hashSet.add(new A(i));//
//        }
        
        /*
当我们向hashset增加一个元素，-> Node -> 加入table , 就算是增加了一个size++
         */

        for(int i = 1; i <= 7; i++) {//在table的某一条链表上添加了 7个A对象
            hashSet.add(new A(i));//
        }

        for(int i = 1; i <= 7; i++) {//在table的另外一条链表上添加了7个B对象
            hashSet.add(new B(i));//
        }



    }
}

class B {
    private int n;

    public B(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 200;
    }
}

class A {
    private int n;

    public A(int n) {
        this.n = n;
    }
    @Override
    public int hashCode() {
        return 100;
    }
}

HashSet课堂练习

题目：

解答：

public class HashSetExercise {
    public static void main(String[] args) {
        /**
         定义一个Employee类，该类包含：private成员属性name,age 要求:
         创建3个Employee 对象放入 HashSet中
         当 name和age的值相同时，认为是相同员工, 不能添加到HashSet集合中
         */
        HashSet hashSet = new HashSet();
        hashSet.add(new Employee("milan", 18));//ok
        hashSet.add(new Employee("smith", 28));//ok
        hashSet.add(new Employee("milan", 18));//加入不成功.
        System.out.println("hashSet=" + hashSet);
    }
}

//创建Employee
class Employee {
    private String name;
    private int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    public void setAge(int age) {
        this.age = age;
    }
    //如果name 和 age 值相同，则返回相同的hash值
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age &&
                Objects.equals(name, employee.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

此类问题关键就在于自定义类要设置不重复加入需要重写equals()方法和hashcode()方法，因为hashmap的底层机制。

LinkedHashSet

• 是HashSet子类（实际底层是LinkedHashMap，HashMap子类）
• 底层维护了一个数组+双向链表
• 根据元素hashCode值来决定存储位置，同时使用链表维护元素的次序，使得元素看起来是以插入顺序保存的。
• 不允许添加重复元素

LinkedHashSet底层源码：

public class LinkedHashSetSource {
    public static void main(String[] args) {
        //分析一下LinkedHashSet的底层机制
        Set set = new LinkedHashSet();
        set.add(new String("AA"));
        set.add(456);
        set.add(456);
        set.add(new Customer("刘", 1001));
        set.add(123);
        set.add("HSP");

        System.out.println("set=" + set);
        //老韩解读
        //1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致
        //2. LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)
        //3. LinkedHashSet 底层结构 (数组table+双向链表)
        //4. 添加第一次时，直接将 数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry
        //5. 数组是 HashMap$Node[] 存放的元素/数据是 LinkedHashMap$Entry类型
             //此处是子类对象存储在父类引用的数组中，多态数组。
             
        /*
                //继承关系是在内部类完成.
                //Node是一个静态内部类，这样才可以通过HashMap.Node访问
                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);
                    }
                }

         */

    }
}
class Customer {
    private String name;
    private int no;
    public Customer(String name, int no) {
        this.name = name;
        this.no = no;
    }
}

LinkedHashSet课堂练习

题目：

public class LinkedHashSetExercise {
    public static void main(String[] args) {

        LinkedHashSet linkedHashSet = new LinkedHashSet();
        linkedHashSet.add(new Car("奥拓", 1000));//OK
        linkedHashSet.add(new Car("奥迪", 300000));//OK
        linkedHashSet.add(new Car("法拉利", 10000000));//OK
        linkedHashSet.add(new Car("奥迪", 300000));//加入不了
        linkedHashSet.add(new Car("保时捷", 70000000));//OK
        linkedHashSet.add(new Car("奥迪", 300000));//加入不了

        System.out.println("linkedHashSet=" + linkedHashSet);

    }
}

/**
 * Car 类(属性:name,price)，  如果 name 和 price 一样，
 * 则认为是相同元素，就不能添加。 5min
 */

class Car {
    private String name;
    private double price;

    public Car(String name, double price) {
        this.name = name;
        this.price = price;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    @Override
    public String toString() {
        return "\nCar{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    //重写equals 方法 和 hashCode
    //当 name 和 price 相同时， 就返回相同的 hashCode 值, equals返回t

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Car car = (Car) o;
        return  Double.compare(car.price, price) == 0 &&
                Objects.equals(name, car.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, price);
    }
}

TreeSet

概述：

TreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet, Cloneable, java.io.Serializable接口。
TreeSet 继承于AbstractSet，所以它是一个Set集合，具有Set的属性和方法。
TreeSet 实现了NavigableSet接口，意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。
TreeSet 实现了Cloneable接口，意味着它能被克隆。
TreeSet 实现了java.io.Serializable接口，意味着它支持序列化。
TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序 或者 根据创建TreeSet 时提供的 Comparator 进行排序。这取决于使用的构造方法。
TreeSet为基本操作（add、remove 和 contains）提供受保证的 log(n) 时间开销。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。

public class TreeSet_ {
    public static void main(String[] args) {

        //1. 当我们使用无参构造器，创建TreeSet时，是字典序（自然排序）
        //2. 老师希望添加的元素，按照字符串大小来排序
        //3. 使用TreeSet 提供的一个构造器，可以传入一个比较器(匿名内部类)
        //   并指定排序规则
       
        
        /*
        1. 构造器把传入的比较器对象，赋给了 TreeSet的底层的 TreeMap的属性this.comparator

         public TreeMap(Comparator<? super K> comparator) {
                this.comparator = comparator;
            }
         2. 在 调用 treeSet.add("tom"), 在底层会执行到

             if (cpr != null) {   //cpr 就是我们的匿名内部类(对象)
                do {
                    parent = t;
                    //动态绑定到我们的匿名内部类(对象)compare
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else //如果相等，即返回0,这个Key就没有加入
                        return t.setValue(value);
                } while (t != null);
            }
         */

//        TreeSet treeSet = new TreeSet();
        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //下面 调用String的 compareTo方法进行字符串大小比较
                //如果老韩要求加入的元素，按照长度大小排序
                //return ((String) o2).compareTo((String) o1);
                return ((String) o1).length() - ((String) o2).length();
            }
        });
        //添加数据.
        treeSet.add("jack");
        treeSet.add("tom");//3
        treeSet.add("sp");
        treeSet.add("a");
        treeSet.add("abc");//3，此时和tom长度相同按照现在的Comparator是无法加入的
        System.out.println("treeSet=" + treeSet);
    }
}

注意：

在构造器中传入Comparator,匿名内部类！

new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //下面 调用String的 compareTo方法进行字符串大小比较
                return ((String) o2).compareTo((String) o1);
                //如果要求加入的元素，按照长度大小排序
                return ((String) o1).length() - ((String) o2).length();
            }
        }



TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //下面 调用String的 compareTo方法进行字符串大小比较
                //如果老韩要求加入的元素，按照长度大小排序
                //return ((String) o2).compareTo((String) o1);
                return ((String) o1).length() - ((String) o2).length();
            }
        });

ps.

treeSet.add("abc");//3，此时和tom长度相同按照现在的Comparator是无法加入的

总结：

(1) TreeSet实际上是TreeMap实现的。当我们构造TreeSet时；

若使用不带参数的构造函数，则TreeSet的使用自然比较器；

若用户需要使用自定义的比较器，则需要使用带比较器的参数。

(2) TreeSet是非线程安全的。

(3) TreeSet实现java.io.Serializable的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。

Map接口

Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap。

Map接口的特点

1.Map与Collection并列存在。用于保存具有映射关系的数据:Key-Value(双列元素)
2.Map 中的 key 和 value 可以是任何引用类型的数据，会封装到HashMap$Node 对象中
3.Map 中的 key 不允许重复，原因和HashSet 一样，前面分析过源码.
4.Map 中的 value 可以重复
5.Map 的key 可以为 null, value 也可以为null ，注意 key 为null,只能有一个，value 为null ,可以多个，当有相同的k , 就等价于替换。
6.常用String类作为Map的 key
7.key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value

8.Map.Entry

概述：

Map是java中的接口，Map.Entry是Map的一个内部接口。Map提供了一些常用方法，如keySet()、entrySet()等方法。keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry。

Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。

但是k-v并不是存储在Entry里的，是存储在HashMap$Node中，Set和Collection只是引用，指向了Node中存储的K-V.

public class MapSource_ {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("no1", "韩顺平");//k-v
        map.put("no2", "张无忌");//k-v
        map.put(new Car(), new Person());//k-v
       
        Set set = map.entrySet();
        System.out.println(set.getClass());// HashMap$EntrySet
        for (Object obj : set) {

            System.out.println(obj.getClass()); //HashMap$Node
            //为了从 HashMap$Node 取出k-v
            //1. 先做一个向下转型
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "-" + entry.getValue() );
        }

        Set set1 = map.keySet();
        System.out.println(set1.getClass());
        Collection values = map.values();
        System.out.println(values.getClass());


    }
}

class Car {

}

class Person{

}

输出：

注意：

1.k-v 最后是 HashMap$Node node = newNode(hash, key, value, null)

2.k-v 为了方便程序员的遍历，还会 创建 EntrySet 集合 ，该集合存放的元素的类型 Entry, 而一个Entry对象就有k,v。EntrySet<Entry<K,V>> 即： transient Set<Map.Entry<K,V>> entrySet;

3.entrySet 中， 定义的类型是 Map.Entry ，但是实际上存放的还是 HashMap$Node
这是因为 static class Node<K,V> implements Map.Entry<K,V>

4.当把 HashMap$Node 对象 存放到 entrySet 就方便我们的遍历, 因为 Map.Entry 提供了重要方法

K getKey(); V getValue()。

Map接口常用方法

详见jdk1.8帮助文档。

(1)V put(K key, V value); 向集合中添加元素。

(2)V get(Object key); 通过指定key获取value。

(3)int size(); 获取集合中元素的个数。

(4)void clear(); 清空集合，元素个数清0。

(5)boolean isEmpty(); 判断集合元素个数是否为0。

(6)boolean containsKey(Object key); 判断集合中是否包含指定key。

(7)boolean containsValue(Object value); 判断集合中是否包含指定value。

注意：contains()方法底层都调用了equals()方法，再次强调存入集合元素的类一定要重写equals()方法。

(8)Set keySet(); 获取集合中所有的key，返回一个包含所有key元素的Set集合。

(9)Collection values(); 获取集合中所有的value，返回一个包含所有value元素的Collection集合。

(10)V remove(Object key); 删除指定key的键值对。

(11)default boolean replace(K key, V oldValue, V newValue) 修改键值对<key, oldValue>的value为newValue。

(12)Set<Map.Entry<K,V>> entrySet(); 将Map集合转换成Set集合

Map接口遍历方法

三组六种：

第一组: 先取出所有的 Key , 通过 Key 取出对应的 Value

Set keyset = map.keySet();

(1) 增强for

(2) 迭代器

第二组: 把所有的 values 取出

Collection values = map.values();

(1) 增强for

(2) 迭代器

第三组: 通过 EntrySet 来获取 k-v

Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>

(1) 增强for

(2) 迭代器

public class MapFor {
    public static void main(String[] args) {

        Map map = new HashMap();
        map.put("邓超", "孙俪");
        map.put("王宝强", "马蓉");
        map.put("宋喆", "马蓉");
        map.put("刘令博", null);
        map.put(null, "刘亦菲");
        map.put("鹿晗", "关晓彤");

        //第一组: 先取出 所有的Key , 通过Key 取出对应的Value
        Set keyset = map.keySet();
        //(1) 增强for
        System.out.println("-----第一种方式-------");
        for (Object key : keyset) {
            System.out.println(key + "-" + map.get(key));
        }
        //(2) 迭代器
        System.out.println("----第二种方式--------");
        Iterator iterator = keyset.iterator();
        while (iterator.hasNext()) {
            Object key =  iterator.next();
            System.out.println(key + "-" + map.get(key));
        }

        //第二组: 把所有的values取出
        Collection values = map.values();
        //这里可以使用所有的Collections使用的遍历方法
        //(1) 增强for
        System.out.println("---取出所有的value 增强for----");
        for (Object value : values) {
            System.out.println(value);
        }
        //(2) 迭代器
        System.out.println("---取出所有的value 迭代器----");
        Iterator iterator2 = values.iterator();
        while (iterator2.hasNext()) {
            Object value =  iterator2.next();
            System.out.println(value);

        }

        //第三组: 通过EntrySet 来获取 k-v
        Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>
        //(1) 增强for
        System.out.println("----使用EntrySet 的 for增强(第3种)----");
        for (Object entry : entrySet) {
            //将entry 转成 Map.Entry
            Map.Entry m = (Map.Entry) entry;
            System.out.println(m.getKey() + "-" + m.getValue());
        }
        //(2) 迭代器
        System.out.println("----使用EntrySet 的 迭代器(第4种)----");
        Iterator iterator3 = entrySet.iterator();
        while (iterator3.hasNext()) {
            Object entry =  iterator3.next();
            //System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
            //向下转型 Map.Entry
            Map.Entry m = (Map.Entry) entry;
            System.out.println(m.getKey() + "-" + m.getValue());
        }


    }
}

HashMap底层机制和源码解读

概述：

HashMap是使用频率Map接口实现类，K-V方式存储（HashMap$Node类型）的数据，key不可以重复，但是Value可以重复，null键和null值均可；如果添加相同的key，会替换value，等同于修改；不保证映射顺序；没有实现同步，线程不安全，方法没有做互斥的操作，无synchronized。

HashMap底层机制和源码剖析

此处详细可参见美团技术团队博客：java8之重新认识HashMap

源码解读部分大多相同与HashSet处，因为底层相同。

public class HashMapSource1 {
    public static void main(String[] args) {
        HashMap map = new HashMap();
        map.put("java", 10);//ok
        map.put("php", 10);//ok
        map.put("java", 20);//替换value

        System.out.println("map=" + map);//

        /*老韩解读HashMap的源码+图解
        1. 执行构造器 new HashMap()
           初始化加载因子 loadfactor = 0.75
           HashMap$Node[] table = null
        2. 执行put 调用 hash方法，计算 key的 hash值 (h = key.hashCode()) ^ (h >>> 16)
            public V put(K key, V value) {//K = "java" value = 10
                return putVal(hash(key), key, value, false, true);
            }
         3. 执行 putVal
         final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
                Node<K,V>[] tab; Node<K,V> p; int n, i;//辅助变量
                //如果底层的table 数组为null, 或者 length =0 , 就扩容到16
                if ((tab = table) == null || (n = tab.length) == 0)
                    n = (tab = resize()).length;
                //取出hash值对应的table的索引位置的Node, 如果为null, 就直接把加入的k-v
                //, 创建成一个 Node ,加入该位置即可
                if ((p = tab[i = (n - 1) & hash]) == null)
                    tab[i] = newNode(hash, key, value, null);
                else {
                    Node<K,V> e; K k;//辅助变量
                // 如果table的索引位置的key的hash相同和新的key的hash值相同，
                 // 并满足(table现有的结点的key和准备添加的key是同一个对象  || equals返回真)
                 // 就认为不能加入新的k-v
                    if (p.hash == hash &&
                        ((k = p.key) == key || (key != null && key.equals(k))))
                        e = p;
                    else if (p instanceof TreeNode)//如果当前的table的已有的Node 是红黑树，就按照红黑树的方式处理
                        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                    else {
                        //如果找到的结点，后面是链表，就循环比较
                        for (int binCount = 0; ; ++binCount) {//死循环
                            if ((e = p.next) == null) {//如果整个链表，没有和他相同,就加到该链表的最后
                                p.next = newNode(hash, key, value, null);
                                //加入后，判断当前链表的个数，是否已经到8个，到8个，后
                                //就调用 treeifyBin 方法进行红黑树的转换
                                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                    treeifyBin(tab, hash);
                                break;
                            }
                            if (e.hash == hash && //如果在循环比较过程中，发现有相同,就break,就只是替换value
                                ((k = e.key) == key || (key != null && key.equals(k))))
                                break;
                            p = e;
                        }
                    }
                    if (e != null) { // existing mapping for key
                        V oldValue = e.value;
                        if (!onlyIfAbsent || oldValue == null)
                            e.value = value; //替换，key对应value
                        afterNodeAccess(e);
                        return oldValue;
                    }
                }
                ++modCount;//每增加一个Node ,就size++
                if (++size > threshold[12-24-48])//如size > 临界值，就扩容
                    resize();
                afterNodeInsertion(evict);
                return null;
            }

              5. 关于树化(转成红黑树)
              //如果table 为null ,或者大小还没有到 64，暂时不树化，而是进行扩容.
              //否则才会真正的树化 -> 剪枝
              final void treeifyBin(Node<K,V>[] tab, int hash) {
                int n, index; Node<K,V> e;
                if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
                    resize();

            }
         */


    }
}

Put方法流程图：

HashTable

概述：

由于HashTable是遗留类，已经基本不使用，此处只简单介绍，线程安全的ConcurrentHashMap已经替代了它。

HashMap与HashTable比较

Hashtable的底层：

1.底层有数组 Hashtable$Entry[] 初始化大小为 11
2.临界值 threshold ： 8 = 11 * 0.75
3.扩容: 按照自己的扩容机制来进行即可（2倍再加1）.
4.执行 方法 addEntry(hash, key, value, index); 添加K-V 封装到Entry
5.当 if (count >= threshold) 满足时，就进行扩容；按照 int newCapacity = (oldCapacity << 1) + 1; 的大小扩容.

TreeMap

有一种Map内部会对Key进行排序，这种Map就是SortedMap。注意到SortedMap是接口，它的实现类是TreeMap。

public class TreeMap_ {
    public static void main(String[] args) {

        //使用默认的构造器，创建TreeMap, 是自然排序
        /*
            老韩要求：按照传入的 k(String) 的大小进行排序
         */
//      TreeMap treeMap = new TreeMap();
        TreeMap treeMap = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                //按照传入的 k(String) 的大小进行排序
                //按照K(String) 的长度大小排序
                //return ((String) o2).compareTo((String) o1);
                return ((String) o2).length() - ((String) o1).length();
            }
        });
        treeMap.put("jack", "杰克");
        treeMap.put("tom", "汤姆");
        treeMap.put("kristina", "克瑞斯提诺");
        treeMap.put("smith", "斯密斯");
        treeMap.put("hsp", "韩顺平");//加入不了

        System.out.println("treemap=" + treeMap);

        /*

             
            1. 构造器. 把传入的实现了 Comparator接口的匿名内部类(对象)，传给给TreeMap的comparator
             public TreeMap(Comparator<? super K> comparator) {
                this.comparator = comparator;
            }
            2. 调用put方法
            2.1 第一次添加, 把 k-v 封装到 Entry对象，放入root
            Entry<K,V> t = root;
            if (t == null) {
                compare(key, key); // type (and possibly null) check

                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            2.2 以后添加
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
                do { //遍历所有的key , 给当前key找到适当位置
                    parent = t;
                    cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类的compare
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else  //如果遍历过程中，发现准备添加Key 和当前已有的Key 相等，就不添加
                        return t.setValue(value);
                } while (t != null);
            }
         */
    }
}

ConcurrentHashMap（补充且重要）

概述：　

ConcurrentHashMap是J.U.C(java.util.concurrent包)的重要成员，它是HashMap的一个线程安全的、支持高效并发的版本。在默认理想状态下，ConcurrentHashMap可以支持16个线程执行并发写操作及任意数量线程的读操作。

无论是 1.7 还是 1.8 JDK 没有对HashMap做任何的同步操作，所以并发会出问题，甚至 1.7 中出现死循环导致系统不可用（1.8 已经修复死循环问题）。

ConcurrentHashMap

1.7：

是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。

原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

1.8：

1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。

那就是查询遍历链表效率太低。

因此 1.8 做了一些数据结构上的调整。

抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。

其中的 val next 都用了 volatile 修饰，保证了可见性。

put 方法

重点来看看 put 函数：

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
• 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
• 如果都不满足，则利用 synchronized 锁写入数据。
• 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

get 方法

• 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
• 如果是红黑树那就按照树的方式获取值。
• 就不满足那就按照链表的方式遍历获取值。

1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。

Properties

概述：

properties多用于做配置文件类型。

继承自HashTable

class Properties extends Hashtable<Object,Object>

Collections工具类

Collections工具类提供了大量针对Collection/Map的操作，总体可分为四类，都为静态（static）方法：

1、排序操作（主要针对List接口相关的）

• reverse(List list)：反转指定List集合中元素的顺序
• shuffle(List list)：对List中的元素进行随机排序（洗牌）
• sort(List list)：对List里的元素根据自然升序排序
• sort(List list, Comparator c)：自定义比较器进行排序
• swap(List list, int i, int j)：将指定List集合中i处元素和j出元素进行交换
• rotate(List list, int distance)：将所有元素向右移位指定长度，如果distance等于size那么结果不变

2. 查找和替换（主要针对Collection接口相关）

• binarySearch(List list, Object key)：使用二分搜索法，以获得指定对象在List中的索引，前提是集合已经排序
• max(Collection coll)：返回最大元素
• max(Collection coll, Comparator comp)：根据自定义比较器，返回最大元素
• min(Collection coll)：返回最小元素
• min(Collection coll, Comparator comp)：根据自定义比较器，返回最小元素
• fill(List list, Object obj)：使用指定对象填充
• frequency(Collection Object o)：返回指定集合中指定对象出现的次数
• replaceAll(List list, Object old, Object new)：替换

3. 同步控制

Collections工具类中提供了多个synchronizedXxx方法，该方法返回指定集合对象对应的同步对象，从而解决多线程并发访问集合时线程的安全问题。HashSet、ArrayList、HashMap都是线程不安全的，如果需要考虑同步，则使用这些方法。这些方法主要有：synchronizedSet、synchronizedSortedSet、synchronizedList、synchronizedMap、synchronizedSortedMap。

特别需要指出的是，在使用迭代方法遍历集合的时候需要手工同步返回的集合。

4. 设置不可变集合

Collections有三类方法可返回一个不可变集合：

1. emptyXxx()：返回一个空的不可变的集合对象
2. singletonXxx()：返回一个只包含指定对象的，不可变的集合对象。
3. unmodifiableXxx()：返回指定集合对象的不可变视图

选择集合类

习题

四个对象：分析如下。注意题目中重写了equals()和hashcode()方法

首先加入p1和p2没问题，之后修改了p1的name，在remove (p1)的时候，是用p1(1001-“CC”)计算哈希值找索引的，但是找不到，删除操作失败了…

新建p3不是同一对象，正常加入了

最后加入(1001-“AA”)的时候，因为p1的位置已经是(1001-“CC”)的对象了，所以没有重复，在p1索引处形成链表，加入表尾。

此处习题建议阅读参考中的Java集合面试题。

总结框图：

来源网络，侵删，可以在脑中形成大概的知识体系，知识点不全面，没必要记忆。

参考

1.韩顺平Java集合专题

2.Java集合容器面试题（2020最新版）

3.《Java核心技术 卷一：基础知识》

4.美团技术团队-java8之重新认识HashMap

5.Java中TreeSet的详细用法

6.Java 集合，Collections工具类的用法