集合（全）

集合概述：方便对多个对象的操作区别A: 数组虽然可以存储对象，可以存基本类型。但是长度固定。B：集合只能存储引用类型，长度可变。特点A：集合只用于存储对象，集合长度可变，可以存不同类型对象。B：不同集合类数据接口不同体系图常见集合：Java集合就像一个容器，可以存储任何类型的数据，也可以结合泛型来存储具体的类型对象。在程序运行时，Java集合可以动态的进行扩展，...

refuse-debug

1883人浏览 · 2020-02-03 02:09:55

refuse-debug · 2020-02-03 02:09:55 发布

集合

概述：

方便对多个对象的操作

区别

A: 数组虽然可以存储对象，可以存基本类型。但是长度固定。

B：集合只能存储引用类型，长度可变。

特点

A：集合只用于存储对象，集合长度可变，可以存不同类型对象。

B：不同集合类数据接口不同

体系图

常见集合：
在这里插入图片描述

Java集合就像一个容器，可以存储任何类型的数据，也可以结合泛型来存储具体的类型对象。在程序运行时，Java集合可以动态的进行扩展，随着元素的增加而扩大。在Java中，集合类通常存在于java.util包中。

Java集合主要由2大体系构成，分别是Collection体系和Map体系，其中Collection和Map分别是2大体系中的顶层接口。

Collection主要有三个子接口，分别为List(列表)、Set(集)、Queue(队列)。其中，List、Queue中的元素有序可重复，而Set中的元素无序不可重复；

List中主要有ArrayList、LinkedList两个实现类；Set中则是有HashSet实现类；而Queue是在JDK1.5后才出现的新集合，主要以数组和链表两种形式存在。

Map同属于java.util包中，是集合的一部分，但与Collection是相互独立的，没有任何关系。Map中都是以key-value的形式存在，其中key必须唯一，主要有HashMap、HashTable、TreeMap三个实现类。

Collection 接口

集合顶层接口。

功能

一、添加

 public boolean add(E e);//把给定的数据存储到集合当中
 public boolean addAll(Collection c);//添加一个集合元素

addAll：可以有重复

	public class CollectionDemo2 {
	public static void main(String[] args) {
      Collection c1 = new ArrayList();
		c1.add("abc1");
		c1.add("abc2");
		c1.add("abc3");
		c1.add("abc4");
		
		
		Collection c2 = new ArrayList();
		c2.add("abc4");
		c2.add("abc5");
		c2.add("abc6");
		c2.add("abc7");
		
		System.out.println(c1.addAll(c2));
		System.out.println(c1);
		System.out.println(c2);
    }
    }
/*输出：
true
[abc1, abc2, abc3, abc4, abc4, abc5, abc6, abc7]
[abc4, abc5, abc6, abc7]*/

二、删除

 public void clear(); // 清空集合所有元素
 public boolean remove(E e); //把给定的数据在当前集合中删除，若是有该数据返回True，否则False
 public boolean removeAll(E e);//移除一个集合元素，只要删除一个，返回true

removeAll：没有重复

public class CollectionDemo2 {
	public static void main(String[] args) {
	
		Collection c1 = new ArrayList();
		c1.add("abc1");
		c1.add("abc2");
		c1.add("abc3");
		c1.add("abc4");
		
		Collection c2 = new ArrayList();
		c2.add("abc4");
		c2.add("abc5");
		c2.add("abc6");
		c2.add("abc7");
		
		System.out.println(c1.addAll(c2));//[abc1, abc2, abc3, abc4, abc4, abc5, abc6, abc7]
		System.out.println(c1.removeAll(c2));
	
		
		System.out.println(c1);
		System.out.println(c2);
	
	}
}
/*
输出：
true
true
[abc1, abc2, abc3]
[abc4, abc5, abc6, abc7]
*/

三、判断

public boolean contains(E e);  //判断当前集合中是否包含给定的对象
public boolean containsAll(E e);//判断集合中是否包含指定集合元素。全部包含返回true
public boolean isEmpty(); //判断当前集合是否为空

四、获取功能

Iterator<E> iterator;//重点

五、长度功能

int size （）;//元素个数

相关题目：数组有没有length()方法？字符串有没有length()方法？集合呢
数组求长度用length属性

字符串求长度用length()方法

集合求长度用size()方法

六、交集功能

boolean retainAll(Collection c);//两个都有的元素

思考：元素去哪了？ boolean什么意思？

1、谁调用则元素被谁保存。

2、假设集合A，集合B，A对B做交集，结果存在A中B不变。返回值表示A是否发生改变

public class CollectionDemo2 {
	public static void main(String[] args) {
	
		Collection c1 = new ArrayList();
		c1.add("abc1");
		c1.add("abc2");
		c1.add("abc3");
		c1.add("abc4");
		
		
		Collection c2 = new ArrayList();
		c2.add("abc4");
		c2.add("abc5");
		c2.add("abc6");
		c2.add("abc7");

		System.out.println(c1.retainAll(c2));
		
		System.out.println(c1);
		System.out.println(c2);
	
	}
}
/*输出：
true
[abc4]
[abc4, abc5, abc6, abc7]
*/

七、集合转换数组

Object[] toArray()://能够将集合转换成数组并把集合中的元素存储到数组中

public class CollectionDemo {
	public static void main(String[] args) {
		// 创建集合对象
		Collection c = new ArrayList(); // 多态，父类引用指向子类对象

		// boolean add(E e):添加元素
		System.out.println(c.add("hello"));
		System.out.println(c.add("world"));
		System.out.println(c);

		// void clear():清空集合
		// c.clear();

		// boolean contains(Object o) :判断集合中是否包含指定元素
		System.out.println(c.contains("hello"));

		// boolean isEmpty():是否为空
		System.out.println(c.isEmpty());

		// boolean remove(Object o):删除元素
		System.out.println(c.remove("hello"));

		// int size() :返回集合中元素的个数
		System.out.println(c.size());

		// Object[] toArray():将集合转换成一个Object类型的数组
		Object[] objs = c.toArray();
		for (int i = 0; i < objs.length; i++) {
			System.out.println(objs[i]);
		}
		System.out.println(c);
	}

迭代器：Iterator接口

Collection 里的iterator() 方法返回一个Iterator子类对象，Iterator里有next()，hasNext()方法

Iterator iterator()；//迭代器，集合专用遍历方式
      Object next();//获取元素
   boolean hasNext();//如果有元素迭代返回true

案例：

public class IteratorDemo {
public static void main(String[] args) {
	//创建集合元素
	Collection c = new ArrayList();
	
	//添加元素列表
	c.add("hello");
	c.add("world");
	c.add("java");
	
	 Iterator it = c.iterator();//返回其子类对象
	 while(it.hasNext()) {
		 String s = (String) it.next();
		 System.out.println(s);
	 }
	}
}

理解：

迭代器为什么不定义成一个类，而是一个接口呢？

   假设迭代器是一个类，我们就可以创建该类的对象，调用该类的方法
来实现集合的遍历。但是，Java中有很多集合类，这些集合数据结构是不
同的，进而遍历方式也不同，一旦定义成类，方法就要具体实现，方法就一
样了,最终没有定义迭代器类。

真正具体的实现类在哪？

在真正具体的子类中，内部类实现

源码：

在这里插入图片描述

List接口

特点

有序的集合，存储元素和取出元素的顺序是一致的（存储123 取出123）
有索引，包含了一些带索引的方法
允许存储重复的元素

特有功能

List接口中带索引的方法（特有）：

public void add(int index,E element)

1、将指定的元素，添加到该集合中的指定位置上。

public E get(int index)

2、返回集合中指定位置的元素。

public E remove(int index)

3、移除列表中指定位置的元素，返回的是被移除的元素。

public E set(int index,E element)

4、用指定元素替换集合中指定位置的元素，返回值的更新前的元素。

ListIterator listIterator()

5、列表迭代器

代码：

//创建一个List集合对象，多态
    List<String> list = new ArrayList<>();
    {
        //public void add(int index,E element):将指定的元素，添加到该集合中的指定位置上。
        //在索引2和索引3之间添加一个cainiao
        list.add(3,"cainiao");//{a,b,c,d}-->{a,b,c,cainiao,d}
        //移除元素
        String removeE = list.remove(2)
        //替换元素
        String setE = list.set(4,"A");
        }

注意：
操作索引的时候，一定要防止索引越界异常

IndexOutOfBoundsException:索引越界异常，集合会报
ArrayIndexOutOfBoundsException:数组索引越界异常
StringIndexOutOfBoundsException:字符串索引越界异常

列表迭代器ListIterator

ListIterator listierator()

ListIterator迭代器继承了Iterator迭代器，所以可以直接使用Iterator的hasNext()和Next()方法。
它多了个逆向遍历，它必须先正向遍历，才能逆向遍历，所以一般意义不大，不使用。
提供了**boolean hasPrevious()和E previous()**方法，实现逆向遍历。

ListIterator接口还提供了一些方法：

**void add(E e) 😗*将指定的元素插入列表，在刚才迭代的元素后面添加。
**void remove() ：**从列表中删除由 next()或 previous()返回的最后一个元素。
**void set(E e) ：**用指定的元素替换由 next()或 previous()返回的最后一个元素。

这些方法的存在说明我们可以使用列表迭代器去修改元素。

遍历

一、（List特有）

get() 和 size()结合

public class ListDemo1 {
	public static void main(String[] args) {
		List list = new ArrayList();

		list.add("hello");
		list.add("world");
		list.add("java");

		for (int x = 0; x < list.size(); x++) {
			String s = (String) list.get(x);
			System.out.println(s);
		}
	}
}

二、迭代器

public class ListDemo1 {
	public static void main(String[] args) {
		List list = new ArrayList();

		list.add("hello");
		list.add("world");
		list.add("java");

		Iterator it = list.iterator;
        while(it.hasNext()){
            String s = (String) it.next();
            System.out.println(s);
        }
		
	}
}

子类特点

在这里插入图片描述

并发修改异常

在这里插入图片描述

ArrayList

基本操作：

public class ArrayListTest {
    public static void main(String[] agrs){
        //创建ArrayList集合：
        List<String> list = new ArrayList<String>();
        System.out.println("ArrayList集合初始化容量："+list.size());

        //添加功能：
        list.add("Hello");
        list.add("world");
        list.add(2,"!");
        System.out.println("ArrayList当前容量："+list.size());

        //修改功能：
        list.set(0,"my");
        list.set(1,"name");
        System.out.println("ArrayList当前内容："+list.toString());

        //获取功能：
        String element = list.get(0);
        System.out.println(element);

        //迭代器遍历集合：(ArrayList实际的跌倒器是Itr对象)
        Iterator<String> iterator =  list.iterator();
        while(iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next);
        }

        //for循环迭代集合：
        for(String str:list){
            System.out.println(str);
        }

        //判断功能：
        boolean isEmpty = list.isEmpty();
        boolean isContain = list.contains("my");

        //长度功能：
        int size = list.size();

        //把集合转换成数组：
        String[] strArray = list.toArray(new String[]{});

        //删除功能：
        list.remove(0);
        list.remove("world");
        list.clear();
        System.out.println("ArrayList当前容量："+list.size());
    }
}
//输出：
ArrayList集合初始化容量：0
ArrayList当前容量：3
ArrayList当前内容：[my, name, !]
my
my
name
!
my
name
!
ArrayList当前容量：0

Vector

特有功能：

（1）添加功能
public void addElement（Object obj） – add（）
（2）获取功能
public Object elementAt（int index） – get（）
public Enumeration elements（） – Iterator iterator（）

Enumeration （Interface）：

boolean hasMoreElements（） – hasNext（）
Object nextElement（） – next（）

package cn.itcast_02;

import java.util.Enumeration;
import java.util.Vector;

/*
 * Vector的特有功能：
 * 1：添加功能
 *         public void addElement(Object obj)        --    add()
 * 2：获取功能
 *         public Object elementAt(int index)        --  get()
 *         public Enumeration elements()            --    Iterator iterator()
 *                 boolean hasMoreElements()                hasNext()
 *                 Object nextElement()                    next()
 * 
 * JDK升级的原因：
 *         A:安全
 *         B:效率
 *         C:简化书写
 */
public class VectorDemo {
    public static void main(String[] args) {
        // 创建集合对象
        Vector v = new Vector();

        // 添加功能
        v.addElement("hello");
        v.addElement("world");
        v.addElement("java");

        // 遍历
        for (int x = 0; x < v.size(); x++) {
            String s = (String) v.elementAt(x);
            System.out.println(s);
        }

        System.out.println("------------------");

        Enumeration en = v.elements(); // 返回的是实现类的对象
        while (en.hasMoreElements()) {
            String s = (String) en.nextElement();
            System.out.println(s);
        }
    }
}

Linkedlist

特有方法

public void addFirst(E e)
             addLast(E e)
    
public E getFirst()；
          getLast()；
          
public E removeFirst()//移除那个元素，并返回该元素
         removeLast()
    
public E get(int index);

public class LinkedListTest01 {

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        //在LinkedList中最前面的位置上添加元素
        list.addFirst("a");
        list.addFirst("b");
        list.addFirst("c");
        list.addFirst("d");
        //在LinkedList中最后面的位置上添加元素
        list.addLast("e");

        //获取LinkedList中的第一个元素
        System.out.println(list.getFirst());
        //获取LinkedList中的最后一个元素
        System.out.println(list.getLast());
        //删除LinkedList中的第一个元素
        System.out.println(list.removeFirst());
        //删除LinkedList中的最后一个元素
        System.out.println(list.removeLast());

        //获取LinkedList中的第二个元素
        System.out.println(list.get(1));
        System.out.println(list);
    }

}

去除集合中重复元素

public class ArrayListDemo {
	public static void main(String[] agrs) {
		// 创建ArrayList集合：
		ArrayList array = new ArrayList();
		// 添加元素
		array.add("hello");
		array.add("hello");
		array.add("world");
		array.add("hello");
		array.add("java");
		array.add("javaee");
		array.add("javaee");

		ArrayList newarray = new ArrayList();

		Iterator it = array.iterator();
		while (it.hasNext()) {
			String s = (String) it.next();
			if (!newarray.contains(s)) {
				newarray.add(s);
			}
		}
        //遍历新集合
		for (int x = 0; x < newarray.size(); x++) {
			String s = (String) newarray.get(x);
			System.out.println(s);
		}

	}
}

应用

用LinkedList模拟栈内存结构的集合

public class MyStaticDemo {
public static void main(String[] args) {
	MyStatic ms = new MyStatic();
	ms.add("hello");
	ms.add("world");
	ms.add("java");
	
	while(!ms.isEmpty()) {
		ms.get();
		
	}
}
}

public class MyStatic {
	private LinkedList link;

	public MyStatic() {
		link = new LinkedList();
	}

	public void add(Object obj) {
		link.addFirst(obj);
	}

	public Object get() {
		return link.removeFirst();
	}

	public boolean isEmpty() {
		return link.isEmpty();
	}
}

增强For

用来代替迭代器

格式

for(元素数据类型 变量：数组或数组或者Collection集合)｛
                使用变量即可，变量及元素
｝

案例：

public class ForDemo {
public static void main(String[] args) {
	int [] array = {12,21,54,65,88};
    
	for(int x:array) {
		System.out.println(x);
	}
}
}

增强型for循环注意事项

在使用增强型for循环不支持遍历时删除元素
使用增强型for循环时，对遍历的集合需要做null判断，不然可能引发空指针异常。

静态导入

概述：

Java从1.5开始，增加了静态导入的语法，静态导入使用import static语句，分为两种：

导入指定类的某个静态成员变量、方法。
导入指定类的全部的静态成员变量、方法。
下面是代码演示：

格式

import static 包名…类名.方法名

方法必须为静态


/*
 * 使用import static,导入java.lang.System下的out这个静态成员变量
 * 这个out,是个打印流
 */
import static java.lang.System.out;

public class StaticImporTest {

    public static void main(String[] args) {
        out.println("hello world");
    }

}
/*
 * 使用import static,导入java.lang.Math这个类中的round方法
 */
import static java.lang.Math.round;

public class StaticImporTest {

    public static void main(String[] args) {
        round(123.123);
    }

}
/*
 * 像这样使用.*,则表示类中所有的静态成员变量和静态方法都被导入了
 */
import static java.lang.System.*;
import static java.lang.Math.*;

public class StaticImporTest {

    public static void main(String[] args) {
        out.println("hello world");
        random();
    }

}

可变参数

可变参数就是传入的参数个数是可变的，可以是1个、2个到任意个，还可以是0个
可变参数允许你传入0个或任意个参数，这些可变参数在函数调用时自动组装为一个tuple

public class paramDemo {

	public static void main(String[] args) {
//		1
		int[] arr = {23,43,54};
		int sum = add(arr);
		System.out.println("sum="+sum);
//	    2
		int[] arr1 = {25,46,50,23,54,66,78};
		int sum1 = add(arr1);
		System.out.println("sum1="+sum1);
//		API1.5之后出现了简化操作    ...只用于参数上称之为可变参数
//		同样是代表数组但是在调用这个可变参数时不可以创建数组（这就是简单之处）
//		直接将数组中的元素作为实际参数进行传递，其实编译成的class文件将这些实参先封装到一个数组中在进行传递
//		这些动作在编译器生成class文件时就帮你完成了
		
//		注意：可变参数一定要定义在参数列表的最后
//		public static int add(int a,int...arr)  正确
//		public static int add(int...arr，int a)  错误
		
		int sum2 =add(23,43,54);
		System.out.println("sum2="+sum2);
		int sum3 = add(25,46,50,23,54,66,78);
		System.out.println("sum3="+sum3);
	}


//		两个整数 的和
		public static int add(int a , int b)
		{
			return a + b ;
		}
//		三个整数和
		public static int add(int a , int b ,int c)
		{
			return a + b + c;
		}
//		多个整数和1
		/*public static int add(int[] arr)
		{
			int sum = 0 ;
			for(int i = 0 ; i < arr.length ; i++ )
			{
				sum += arr[i];
			}
			return sum;
		}*/
//		多个整数和2   API1.5之后的方法
		public static int add(int.../*int类型的数据*/arr)//数组参数的简化表现形式
		{
			int sum = 0 ;
			for(int i = 0 ; i < arr.length ; i++ )
			{
				sum += arr[i];
			}
			return sum;
		}
}

Set接口

无序、唯一!

HashSet

特点

它存储唯一元素并允许空值
它由HashMap支持
它不保持插入顺序
它不是线程安全的
底层HashMap

在这里插入图片描述

如何保证唯一性？

依赖于 **hashCode()和equals()**两个方法

（一些类需要重写该方法而 String 类重写了这两个方法）

首先比较哈希值
- 相同：比较地址值或者走equals()方法
- 不同：直接添加元素到集合

通过源码看HashMap中的 put 方法

// hashmap中put的方法
    public V put(K key, V value) {
    // 判断 entry[] 数组是否为空数组 如果为空 初始化entry数组
    if (table == EMPTY_TABLE) {
    	// 初始化hashmap
        inflateTable(threshold);
    }
    // 如果key 为null 把这个value对应的entry放进table[0]位置中
    if (key == null)
        return putForNullKey(value);
    // 计算 key的hash值
    int hash = hash(key);
    // 计算 key对应的 entry所在数组的下标
    int i = indexFor(hash, table.length);
    // 获取上面计算的下标的链表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 如果存在hash值相同,并且key相同的entry,对value进行覆盖,并返回覆盖区的value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    // 如果链表中没有,则添加
    modCount++;
    addEntry(hash, key, value, i);
    return null;
	}


	// 初始化 hashmap 
    private void inflateTable(int toSize) {
        // 根据初始化的值,获取对应的小的大于这个值的 2 的n次方的值,也就是hashmap的容量
        int capacity = roundUpToPowerOf2(toSize);
        // 通过容量与扩容因子的相乘,获取最大不触发扩容的容量
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        // 创建数组
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

    // 获取当前数值最接近并且大于当前数值的最小2的n次方
	private static int roundUpToPowerOf2(int number) {
        // Integer.highestOneBit((number - 1) << 1) 获取当前数值减去1后向左位移1位,并且第二位往后都为0的值
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

    // 当key为null的时候,对应value存放的位置
    private V putForNullKey(V value) {
    	// 获取table[0]的entry, 遍历这个链表
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        	// 如果存在key为null的entry,把value进行覆盖,并返回覆盖前的value
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        // 如果对应key为null的entry不存在,则在table[0]位置添加一个key为null的entry,并modcount加1
        modCount++;
        // 添加entry
        addEntry(0, null, value, 0);
        // 返回null
        return null;
    }
    // 添加 entry 参数是key的hash值,key,value,下标
    void addEntry(int hash, K key, V value, int bucketIndex) {
    	// 判断hashmap中所有entry的数量是否大于扩容临界值并且指定下标处的entry[]数组元素不为null 触发扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
        	// 扩容后的容量是原先的两倍
            resize(2 * table.length);
            // 获取key的hash值
            hash = (null != key) ? hash(key) : 0;
            // 重新计算下标
            bucketIndex = indexFor(hash, table.length);
        }
        // 创建entry
        createEntry(hash, key, value, bucketIndex);
    }

    // 创建entry的方法
    void createEntry(int hash, K key, V value, int bucketIndex) {
    	// 获取指定下标的entry
        Entry<K,V> e = table[bucketIndex];
        // 新创建的entry作为原先链表的最顶端,覆盖创建前的entry
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        // 数组内总的entry加1
        size++;
    }

    // 扩容算法
    void resize(int newCapacity) {
    	// 首先把老的数组复制到一个临时数组中
        Entry[] oldTable = table;
        // 保存老的数组的长度
        int oldCapacity = oldTable.length;
        // 判断 老的数组长度是否等于最大值  如果等于, 扩容阙值为integer的最大值
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        // 如果不相等,根据新的数组长度创建数组
        Entry[] newTable = new Entry[newCapacity];
        // 移动老的数组中的数据到新的数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        // 把table的引用指向新的数组
        table = newTable;
        // 获取扩容的阙值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

    // 移到老的数组中的数据到新的数组里面
    void transfer(Entry[] newTable, boolean rehash) {
    	// 获取新的数组的长度
        int newCapacity = newTable.length;
        // 遍历老的entry数组
        for (Entry<K,V> e : table) {
        	// 判断entry不为null
            while(null != e) {
            	// 获取链表中的entry
                Entry<K,V> next = e.next;

                if (rehash) {
                	// 获取hash值
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // 通过hash与新的数组长度,获取key在新的数组中的下标
                int i = indexFor(e.hash, newCapacity);
                // 当前entry添加到数组之前,先原来的entry存进当前entry下
                e.next = newTable[i];
                // 把当前entry赋给entry数组
                newTable[i] = e;
                // 对当前entry链表的下一个entry进行赋值
                e = next;
            }
        }
    }

LinkedHashSet

特点

元素有序唯一，底层由哈希表和链表组成

TreeSet

特点

能够对元素按照某种规则排序

底层：二叉树（红黑树自平衡二叉树）基于TreeMap实现

排序

根据构造函数参数确定

A：自然排序

元素具备比较性：元素的类实现该接口。例子：给一个教室每个学生排好编码，学生有序。

通过源码发现TreeSet的add()方法基于TreeMap的**put()**方法实现
依赖的是Comparable接口的compareTo()方法，要想重写方法必须实现Comparable接口，这个接口表示的就是自然排序

在这里插入图片描述

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

		// 自然排序（无参构造）
		TreeSet<Integer> ts = new TreeSet<Integer>();

		// 创建元素并添加
		ts.add(20);
		ts.add(65);
		ts.add(30);
		ts.add(47);
		ts.add(90);
		ts.add(16);
		
		for(Integer x :ts) {
			System.out.println(x);
		}
	}
}

B:比较器排序

集合具备比较性：让集合构造方法接收一个比较器接口的子类对象。例子：给教室每个座位贴好编码，教室有序。

public TreeSet(Comparator comparator)

如果一个方法参数是接口，那么真正需要的是接口的实现类的对象

内部类可以实现这个

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

		// 构造器排序（参数是接口）
		TreeSet<Student> ts = new TreeSet<Student>(new Comparator<Student>() {
			public int compare(Student s1, Student s2) {
				int num = s1.getName().length() - s2.getName().length();
				int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
				int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
				return num3;
			}
		});

		// 创建元素并添加
		Student s1 = new Student("linqingxia",27);
		Student s2 = new Student("linsdfdsfgxia",27);
		Student s3 = new Student("lifsdngxia",27);
		Student s4 = new Student("linasdngxia",27);
		Student s5 = new Student("liadsadingxia",27);
		Student s6 = new Student("lsdfsdngxia",27);
		
		ts.add(s1);
		ts.add(s2);
		ts.add(s3);
		ts.add(s4);
		ts.add(s5);
		ts.add(s6);
		

		for (Student x : ts) {
			System.out.println(x);
		}
	}
}

Map集合

概念

将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。

Map集合的数据结构只针对键有效，与值无关

特点

Key和Value是1对1的关系
Map与Collection在集合框架中属并列存在
Map存储的是键值对
Map存储元素使用put方法，Collection使用add方法
Map集合没有直接取出元素的方法，而是先转成Set集合，在通过迭代获取元素
Map集合中键要保证唯一性
也就是Collection是单列集合, Map 是双列集合。

Map学习体系：
 ---| Map  接口    将键映射到值的对象。一个映射不能包含重复的键；每个键最多
 只能映射到一个值。
 
			---| HashMap  采用哈希表实现，所以无序
            ---| TreeMap   可以对健进行排序
 
---|Hashtable:
底层是哈希表数据结构，线程是同步的，不可以存入null键，null值。
效率较低，被HashMap 替代。
---|HashMap:
底层是哈希表数据结构，线程是不同步的，可以存入null键，null值。
要保证键的唯一性，需要覆盖hashCode方法，和equals方法。
---| LinkedHashMap：
该子类基于哈希表又融入了链表。可以Map集合进行增删提高效率。
---|TreeMap:
底层是二叉树数据结构。可以对map集合中的键进行排序。需要使用Comparable或者
Comparator 进行比较排序。return 0，来判断键的唯一性。

常用方法

1、添加

void put(Object key,Object value)    添加一个键值对，如果已有相同的key，会覆盖原有的键值对，添加重复的键值（值不同）,会返回集合中原有（重复键）的值，

2、删除

void  clear()    清空Map所有键值对
Object remove(Object key)  删除指定的键值对，返回value值。如果key不存在，返回null

3、判断功能

boolean  containsKey(Object key)  是否包含指定的key
boolean  containsValue(Object value)   是否包含指定的值（一个或多个）
boolean  isEmpty()   是否是空Map

4、获取功能

Set<Map.Entry<K,V> entrySet();  获取所有键值对集合的对象
V get (Object key)              根据键获取值
Set<K> keySet()                 获取集合中所有键的集合
Collection<V> values()          获取集合中所有值的集合

5、长度：

Int size（）

添加：

该案例使用了HashMap，建立了学生姓名和年龄之间的映射关系。并试图添加重复的键。

public class Demo1 {
	public static void main(String[] args) {
		// 定义一个Map的容器对象
		Map<String, Integer > map1 = new HashMap<String, Integer >();
		map1.put("jack", 20);
		map1.put("rose", 18);
		map1.put("lucy", 17);
		map1.put("java", 25);
		System.out.println(map1);
		// 添加重复的键值（值不同）,会返回集合中原有（重复键）的值，		 System.out.println(map1.put("jack", 30)); //20
		       
		Map<String, Integer> map2 = new HashMap<String, Integer>();
		map2.put("张三丰", 100);
		map2.put("虚竹", 20);
		System.out.println("map2:" + map2);
// 从指定映射中将所有映射关系复制到此映射中。
		map1.putAll(map2);
		System.out.println("map1:" + map1);
         //
	}

}

添加：

public class MapDemo {


	public static void main(String[] args) {
		// 定义一个Map的容器对象
		Map<String, Integer > map1 = new HashMap<String, Integer >();
		map1.put("jack", 20);
		map1.put("rose", 18);
		map1.put("lucy", 17);
		map1.put("java", 25);
		map1.put("java", 35);
		System.out.println(map1);
		// 添加重复的键值（值不同）,会返回集合中原有（重复键）的值，	
		       
		Map<String, Integer> map2 = new HashMap<String, Integer>();
		map2.put("张三丰", 100);
		map2.put("虚竹", 20);
		System.out.println("map2:" + map2);
        // 从指定映射中将所有映射关系复制到此映射中。
		map1.putAll(map2);
		System.out.println("map1:" + map1);
	}
}

获取

// 获取：
		// V get(Object key) 通过指定的key对象获取value对象
		// int size() 获取容器的大小
		Map<String, Integer> map1 = new HashMap<String, Integer>();
		map1.put("jack", 20);
		map1.put("rose", 18);
		map1.put("lucy", 17);
		map1.put("java", 25);
		System.out.println(map1);
		// V get(Object key) 通过指定的key对象获取value
		// int size() 获取容器的大小
		System.out.println("value:" + map1.get("jack"));
		System.out.println("map.size:" + map1.size());
     //获取所有键的集合
        Set<String> set = map1.keySet()  ;
                for(String key : set){
                    System.out.print(key);
        }
    //获取所有值的集合
       Collection<Integer> c= map1.values() ;
				for(Integer x : c) {
					System.out.println(x);
				}

	}
}

遍历

方式一

1、获取所有的键

2、遍历所有的键，获取每一个键

3、根据键获取值

public class MapDemo {

	public static void main(String[] args) {
		// 定义一个Map的容器对象

		Map<String, Integer> map1 = new HashMap<String, Integer>();
		map1.put("jack", 20);
		map1.put("rose", 18);
		map1.put("lucy", 17);
		map1.put("java", 25);
		// 遍历
		// 获取所有的键
		Set<String> set = map1.keySet();
		// 遍历所有的键
		for (String key : set) {
			 Integer value = map1.get(key);
			System.out.println(key+"-----"+value);
		}
	}
}

方式二

思路：

获取所有键值对对象的集合

遍历键值对集合得到每一个键值对

通过键值对对象获取键和值

public class MapDemo {

	public static void main(String[] args) {
		// 定义一个Map的容器对象

		Map<String, Integer> map1 = new HashMap<String, Integer>();
		map1.put("jack", 20);
		map1.put("rose", 18);
		map1.put("lucy", 17);
		map1.put("java", 25);
		// 遍历
		Set<Map.Entry<String,Integer>> set = map1.entrySet();
		for(Entry<String, Integer> me:set) {
			String key = me.getKey();
			Integer value = me.getValue();
			System.out.println(key+"...."+value);
		}	
	}
}

HashMap

底层是哈希表数据结构，线程是不同步的，可以存入null键，null值。要保证键的唯一性，需要覆盖hashCode方法，和equals方法。

案例：自定义对象作为Map的键。

public class MapDemo {
		public static void main(String[] args) {
			HashMap<Person, String> hm = new HashMap<Person, String>();
			hm.put(new Person("jack", 20), "1001");
			hm.put(new Person("rose", 18), "1002");
			hm.put(new Person("lucy", 19), "1003");
			hm.put(new Person("hmm", 17), "1004");
			hm.put(new Person("ll", 25), "1005");
			System.out.println(hm);
			System.out.println(hm.put(new Person("rose", 18), "1006"));
	 
			Set<Entry<Person, String>> set= hm.entrySet();
			for(Entry<Person, String> e:set) {
				Person K = e.getKey();
				String V = e.getValue();
				System.out.println(K+"..."+V);		
			}
		}
	}
	 
	class Person {
		private String name;
		private int age;
	 
		Person() {
	 
		}
	 
		public Person(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;
		}
	 
		public void setAge(int age) {
			this.age = age;
		}
	 
		@Override
		public int hashCode() {
	 
			return this.name.hashCode() + age * 37;
		}
	 
		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Person) {
				Person p = (Person) obj;
				return this.name.equals(p.name) && this.age == p.age;
			} else {
				return false;
			}
		}
	 
		@Override
		public String toString() {
	 
			return  this.name + " age:" + this.age;
		}
	 
	}

TreeMap

TreeMap的排序，TreeMap可以对集合中的键进行排序。如何实现键的排序？

方式一：元素自身具备比较性

和TreeSet一样原理，需要让存储在键位置的对象实现Comparable接口，重写compareTo方法，也就是让元素自身具备比较性，这种方式叫做元素的自然排序也叫做默认排序。

方式二：容器具备比较性

当元素自身不具备比较性，或者自身具备的比较性不是所需要的。那么此时可以让容器自身具备。需要定义一个类实现接口Comparator，重写compare方法，并将该接口的子类实例对象作为参数传递给TreeMap集合的构造方法。

注意：当Comparable比较方式和Comparator比较方式同时存在时，以Comparator的比较方式为主；

**注意：**在重写compareTo或者compare方法时，必须要明确比较的主要条件相等时要比较次要条件。（假设姓名和年龄一直的人为相同的人，如果想要对人按照年龄的大小来排序，如果年龄相同的人，需要如何处理？不能直接return 0，以为可能姓名不同（年龄相同姓名不同的人是不同的人）。此时就需要进行次要条件判断（需要判断姓名），只有姓名和年龄同时相等的才可以返回0.）

通过return 0来判断唯一性。

public class Demo4 {
	public static void main(String[] args) {
		TreeMap<String, Integer> tree = new TreeMap<String, Integer>();
		tree.put("张三", 19);
		tree.put("李四", 20);
		tree.put("王五", 21);
		tree.put("赵六", 22);
		tree.put("周七", 23);
		tree.put("张三", 24);
		System.out.println(tree);
		System.out.println("张三".compareTo("李四"));//-2094
	}
}

自定义元素排序

public class Demo3 {
	public static void main(String[] args) {
		TreeMap<Person, String> hm = new TreeMap<Person, String>(
				new MyComparator());
		hm.put(new Person("jack", 20), "1001");
		hm.put(new Person("rose", 18), "1002");
		hm.put(new Person("lucy", 19), "1003");
		hm.put(new Person("hmm", 17), "1004");
		hm.put(new Person("ll", 25), "1005");
		System.out.println(hm);
		System.out.println(hm.put(new Person("rose", 18), "1006"));
 
		Set<Entry<Person, String>> entrySet = hm.entrySet();
		Iterator<Entry<Person, String>> it = entrySet.iterator();
		while (it.hasNext()) {
			Entry<Person, String> next = it.next();
			Person key = next.getKey();
			String value = next.getValue();
			System.out.println(key + " = " + value);
		}
	}
}
 
class MyComparator implements Comparator<Person> {
 
	@Override
	public int compare(Person p1, Person p2) {
		if (p1.getAge() > p2.getAge()) {
			return -1;
		} else if (p1.getAge() < p2.getAge()) {
			return 1;
		}
		return p1.getName().compareTo(p2.getName());
	}
 
}
 
class Person implements Comparable<Person> {
	private String name;
	private int age;
 
	Person() {
 
	}
 
	public Person(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;
	}
 
	public void setAge(int age) {
		this.age = age;
	}
 
	@Override
	public int hashCode() {
 
		return this.name.hashCode() + age * 37;
	}
 
	@Override
	public boolean equals(Object obj) {
		if (obj instanceof Person) {
			Person p = (Person) obj;
			return this.name.equals(p.name) && this.age == p.age;
		} else {
			return false;
		}
	}
 
	@Override
	public String toString() {
 
		return "Person@name:" + this.name + " age:" + this.age;
	}
 
	@Override
	public int compareTo(Person p) {
 
		if (this.age > p.age) {
			return 1;
		} else if (this.age < p.age) {
			return -1;
		}
		return this.name.compareTo(p.name);
	}
 
}

LinkedHashMap

先来一张LinkedHashMap的结构图，不要虚，看完文章再来看这个图，就秒懂了，先混个面熟：

LinkedHashMap结构.png

2.1 应用场景

HashMap是无序的，当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了。

        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("name1", "josan1");
        hashMap.put("name2", "josan2");
        hashMap.put("name3", "josan3");
        Set<Entry<String, String>> set = hashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

image.png

我们是按照xxx1、xxx2、xxx3的顺序插入的，但是输出结果并不是按照顺序的。

同样的数据，我们再试试LinkedHashMap

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name1", "josan1");
        linkedHashMap.put("name2", "josan2");
        linkedHashMap.put("name3", "josan3");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

image.png

结果可知，LinkedHashMap是有序的，且默认为插入顺序。

2.2 简单使用

跟HashMap一样，它也是提供了key-value的存储方式，并提供了put和get方法来进行数据存取。

        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name", "josan");
        String name = linkedHashMap.get("name");

2.3 定义

LinkedHashMap继承了HashMap，所以它们有很多相似的地方。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

2.4 构造方法

image.png

LinkedHashMap提供了多个构造方法，我们先看空参的构造方法。

    public LinkedHashMap() {
        // 调用HashMap的构造方法，其实就是初始化Entry[] table
        super();
        // 这里是指是否基于访问排序，默认为false
        accessOrder = false;
    }

首先使用super调用了父类HashMap的构造方法，其实就是根据初始容量、负载因子去初始化Entry

然后把accessOrder设置为false，这就跟存储的顺序有关了，LinkedHashMap存储数据是有序的，而且分为两种：插入顺序和访问顺序。

这里accessOrder设置为false，表示不是访问顺序而是插入顺序存储的，这也是默认值，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap也提供了可以设置accessOrder的构造方法，我们来看看这种模式下，它的顺序有什么特点？

                // 第三个参数用于指定accessOrder值
        Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
        linkedHashMap.put("name1", "josan1");
        linkedHashMap.put("name2", "josan2");
        linkedHashMap.put("name3", "josan3");
        System.out.println("开始时顺序：");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
        System.out.println("通过get方法，导致key为name1对应的Entry到表尾");
        linkedHashMap.get("name1");
        Set<Entry<String, String>> set2 = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator2 = set2.iterator();
        while(iterator2.hasNext()) {
            Entry entry = iterator2.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

image.png

因为调用了get(“name1”)导致了name1对应的Entry移动到了最后，这里只要知道LinkedHashMap有插入顺序和访问顺序两种就可以，后面会详细讲原理。

还记得，上一篇HashMap解析中提到，在HashMap的构造函数中，调用了init方法，而在HashMap中init方法是空实现，但LinkedHashMap重写了该方法，所以在LinkedHashMap的构造方法里，调用了自身的init方法，init的重写实现如下：

    /**
     * Called by superclass constructors and pseudoconstructors (clone,
     * readObject) before any entries are inserted into the map.  Initializes
     * the chain.
     */
    @Override
    void init() {
        // 创建了一个hash=-1，key、value、next都为null的Entry
        header = new Entry<>(-1, null, null, null);
        // 让创建的Entry的before和after都指向自身，注意after不是之前提到的next
        // 其实就是创建了一个只有头部节点的双向链表
        header.before = header.after = header;
    }

这好像跟我们上一篇HashMap提到的Entry有些不一样，HashMap中静态内部类Entry是这样定义的：

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

没有before和after属性啊！原来，LinkedHashMap有自己的静态内部类Entry，它继承了HashMap.Entry，定义如下:

    /**
     * LinkedHashMap entry.
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

所以LinkedHashMap构造函数，主要就是调用HashMap构造函数初始化了一个Entry[] table，然后调用自身的init初始化了一个只有头结点的双向链表。完成了如下操作：

LinkedHashMap构造函数.png

2.5 put方法

LinkedHashMap没有重写put方法，所以还是调用HashMap得到put方法，如下：

    public V put(K key, V value) {
        // 对key为null的处理
        if (key == null)
            return putForNullKey(value);
        // 计算hash
        int hash = hash(key);
        // 得到在table中的index
        int i = indexFor(hash, table.length);
        // 遍历table[index]，是否key已经存在，存在则替换，并返回旧值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        
        modCount++;
        // 如果key之前在table中不存在，则调用addEntry，LinkedHashMap重写了该方法
        addEntry(hash, key, value, i);
        return null;
    }

我们看看LinkedHashMap的addEntry方法：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 调用父类的addEntry，增加一个Entry到HashMap中
        super.addEntry(hash, key, value, bucketIndex);

        // removeEldestEntry方法默认返回false，不用考虑
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

这里调用了父类HashMap的addEntry方法，如下：

    void addEntry(int hash, K key, V value, int bucketIndex) {
        // 扩容相关
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // LinkedHashMap进行了重写
        createEntry(hash, key, value, bucketIndex);
    }

前面是扩容相关的代码，这里主要看createEntry方法，LinkedHashMap进行了重写。

   void createEntry(int hash, K key, V value, int bucketIndex) {
       HashMap.Entry<K,V> old = table[bucketIndex];
       // e就是新创建了Entry，会加入到table[bucketIndex]的表头
       Entry<K,V> e = new Entry<>(hash, key, value, old);
       table[bucketIndex] = e;
       // 把新创建的Entry，加入到双向链表中
       e.addBefore(header);
       size++;
   }

我们来看看LinkedHashMap.Entry的addBefore方法：

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

从这里就可以看出，当put元素时，不但要把它加入到HashMap中去，还要加入到双向链表中，所以可以看出LinkedHashMap就是HashMap+双向链表，下面用图来表示逐步往LinkedHashMap中添加数据的过程，红色部分是双向链表，黑色部分是HashMap结构，header是一个Entry类型的双向链表表头，本身不存储数据。

首先是只加入一个元素Entry1，假设index为0：

LinkedHashMap结构一个元素.png

当再加入一个元素Entry2，假设index为15：

LinkedHashMap结构两个元素.png

当再加入一个元素Entry3, 假设index也是0：

LinkedHashMap结构三个元素.png

以上，就是LinkedHashMap的put的所有过程了，总体来看，跟HashMap的put类似，只不过多了把新增的Entry加入到双向列表中。

2.6 扩容

在HashMap的put方法中，如果发现前元素个数超过了扩容阀值时，会调用resize方法，如下：

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
       // 把旧table的数据迁移到新table
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

LinkedHashMap重写了transfer方法，数据的迁移，它的实现如下：

    void transfer(HashMap.Entry[] newTable, boolean rehash) {
        // 扩容后的容量是之前的2倍
        int newCapacity = newTable.length;
        // 遍历双向链表，把所有双向链表中的Entry，重新就算hash，并加入到新的table中
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            if (rehash)
                e.hash = (e.key == null) ? 0 : hash(e.key);
            int index = indexFor(e.hash, newCapacity);
            e.next = newTable[index];
            newTable[index] = e;
        }
    }

可以看出，LinkedHashMap扩容时，数据的再散列和HashMap是不一样的。

HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置。

LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置。

从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。

2.7 双向链表的重排序

前面分析的，主要是当前LinkedHashMap中不存在当前key时，新增Entry的情况。当key如果已经存在时，则进行更新Entry的value。就是HashMap的put方法中的如下代码：

        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                // 重排序
                e.recordAccess(this);
                return oldValue;
            }
        }

主要看e.recordAccess(this)，这个方法跟访问顺序有关，而HashMap是无序的，所以在HashMap.Entry的recordAccess方法是空实现，但是LinkedHashMap是有序的,LinkedHashMap.Entry对recordAccess方法进行了重写。

        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            // 如果LinkedHashMap的accessOrder为true，则进行重排序
            // 比如前面提到LruCache中使用到的LinkedHashMap的accessOrder属性就为true
            if (lm.accessOrder) {
                lm.modCount++;
                // 把更新的Entry从双向链表中移除
                remove();
                // 再把更新的Entry加入到双向链表的表尾
                addBefore(lm.header);
            }
        }

在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会put时对更新的Entry进行重新排序，而如果是插入顺序模式时，不会重新排序，这里的排序跟在HashMap中存储没有关系，只是指在双向链表中的顺序。

举个栗子：开始时，HashMap中有Entry1、Entry2、Entry3，并设置LinkedHashMap为访问顺序，则更新Entry1时，会先把Entry1从双向链表中删除，然后再把Entry1加入到双向链表的表尾，而Entry1在HashMap结构中的存储位置没有变化，对比图如下所示：

LinkedHashMap重排序.png

2.8 get方法

LinkedHashMap有对get方法进行了重写，如下：

    public V get(Object key) {
        // 调用genEntry得到Entry
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        // 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序
        e.recordAccess(this);
        return e.value;
    }

先是调用了getEntry方法，通过key得到Entry，而LinkedHashMap并没有重写getEntry方法，所以调用的是HashMap的getEntry方法，在上一篇文章中我们分析过HashMap的getEntry方法：首先通过key算出hash值，然后根据hash值算出在table中存储的index，然后遍历table[index]的单向链表去对比key，如果找到了就返回Entry。

后面调用了LinkedHashMap.Entry的recordAccess方法，上面分析过put过程中这个方法，其实就是在访问顺序的LinkedHashMap进行了get操作以后，重新排序，把get的Entry移动到双向链表的表尾。

2.9 遍历方式取数据

我们先来看看HashMap使用遍历方式取数据的过程：

HashMap遍历.png

很明显，这样取出来的Entry顺序肯定跟插入顺序不同了，既然LinkedHashMap是有序的，那么它是怎么实现的呢？
先看看LinkedHashMap取遍历方式获取数据的代码：

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name1", "josan1");
        linkedHashMap.put("name2", "josan2");
        linkedHashMap.put("name3", "josan3");
                // LinkedHashMap没有重写该方法，调用的HashMap中的entrySet方法
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

LinkedHashMap没有重写entrySet方法，我们先来看HashMap中的entrySet，如下：

public Set<Map.Entry<K,V>> entrySet() {
        return entrySet0();
    }

    private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }

    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return newEntryIterator();
        }
        // 无关代码
        ......
    }

可以看到，HashMap的entrySet方法，其实就是返回了一个EntrySet对象。

我们得到EntrySet会调用它的iterator方法去得到迭代器Iterator，从上面的代码也可以看到，iterator方法中直接调用了newEntryIterator方法并返回，而LinkedHashMap重写了该方法

    Iterator<Map.Entry<K,V>> newEntryIterator() { 
        return new EntryIterator();
    }

这里直接返回了EntryIterator对象，这个和上一篇HashMap中的newEntryIterator方法中一模一样，都是返回了EntryIterator对象，其实他们返回的是各自的内部类。我们来看看LinkedHashMap中EntryIterator的定义：

    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { 
          return nextEntry();
        }
    }

该类是继承LinkedHashIterator，并重写了next方法；而HashMap中是继承HashIterator。
我们再来看看LinkedHashIterator的定义：

    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        // 默认下一个返回的Entry为双向链表表头的下一个元素
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        public boolean hasNext() {
            return nextEntry != header;
        }

        Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
        // 不相关代码
        ......
    }

我们先不看整个类的实现，只要知道在LinkedHashMap中，Iterator<Entry<String, String>> iterator = set.iterator()，这段代码会返回一个继承LinkedHashIterator的Iterator，它有着跟HashIterator不一样的遍历规则。

接着，我们会用while(iterator.hasNext())去循环判断是否有下一个元素，LinkedHashMap中的EntryIterator没有重写该方法，所以还是调用LinkedHashIterator中的hasNext方法，如下：

        public boolean hasNext() {
            // 下一个应该返回的Entry是否就是双向链表的头结点
            // 有两种情况：1.LinkedHashMap中没有元素；2.遍历完双向链表回到头部
            return nextEntry != header;
        }

nextEntry表示下一个应该返回的Entry，默认值是header.after，即双向链表表头的下一个元素。而上面介绍到，LinkedHashMap在初始化时，会调用init方法去初始化一个before和after都指向自身的Entry，但是put过程会把新增加的Entry加入到双向链表的表尾，所以只要LinkedHashMap中有元素，第一次调用hasNext肯定不会为false。

然后我们会调用next方法去取出Entry，LinkedHashMap中的EntryIterator重写了该方法，如下：

 public Map.Entry<K,V> next() { 
    return nextEntry(); 
}

而它自身又没有重写nextEntry方法，所以还是调用的LinkedHashIterator中的nextEntry方法：

        Entry<K,V> nextEntry() {
            // 保存应该返回的Entry
            Entry<K,V> e = lastReturned = nextEntry;
            //把当前应该返回的Entry的after作为下一个应该返回的Entry
            nextEntry = e.after;
            // 返回当前应该返回的Entry
            return e;
        }

这里其实遍历的是双向链表，所以不会存在HashMap中需要寻找下一条单向链表的情况，从头结点Entry header的下一个节点开始，只要把当前返回的Entry的after作为下一个应该返回的节点即可。直到到达双向链表的尾部时，after为双向链表的表头节点Entry header，这时候hasNext就会返回false，表示没有下一个元素了。LinkedHashMap的遍历取值如下图所示：

LinkedHashMap遍历.png

易知，遍历出来的结果为Entry1、Entry2…Entry6。
可得，LinkedHashMap是有序的，且是通过双向链表来保证顺序的。

2.10 remove方法

LinkedHashMap没有提供remove方法，所以调用的是HashMap的remove方法，实现如下：

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                // LinkedHashMap.Entry重写了该方法
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

在上一篇HashMap中就分析了remove过程，其实就是断开其他对象对自己的引用。比如被删除Entry是在单向链表的表头，则让它的next放到表头，这样它就没有被引用了；如果不是在表头，它是被别的Entry的next引用着，这时候就让上一个Entry的next指向它自己的next，这样，它也就没被引用了。

在HashMap.Entry中recordRemoval方法是空实现，但是LinkedHashMap.Entry对其进行了重写，如下：

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

易知，这是要把双向链表中的Entry删除，也就是要断开当前要被删除的Entry被其他对象通过after和before的方式引用。

所以，LinkedHashMap的remove操作。首先把它从table中删除，即断开table或者其他对象通过next对其引用，然后也要把它从双向链表中删除，断开其他对应通过after和before对其引用。

HashMap与LinkedHashMap的结构对比

再来看看HashMap和LinkedHashMap的结构图，是不是秒懂了。LinkedHashMap其实就是可以看成HashMap的基础上，多了一个双向链表来维持顺序。

HashMap结构.png

LinkedHashMap结构.png

4 LinkedHashMap在Android中的应用

在Android中使用图片时，一般会用LruCacha做图片的内存缓存，它里面就是使用LinkedHashMap来实现存储的。

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        // 注意第三个参数，是accessOrder，这里为true，后面会讲到
        this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
    }

前面提到了，accessOrder为true，表示LinkedHashMap为访问顺序，当对已存在LinkedHashMap中的Entry进行get和put操作时，会把Entry移动到双向链表的表尾（其实是先删除，再插入）。
我们拿LruCache的put方法举例：

    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }

        V previous;
        // 对map进行操作之前，先进行同步操作
        synchronized (this) {
            putCount++;
            size += safeSizeOf(key, value);
            previous = map.put(key, value);
            if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if (previous != null) {
            entryRemoved(false, key, previous, value);
        }
        // 整理内存，看是否需要移除LinkedHashMap中的元素
        trimToSize(maxSize);
        return previous;
    }

之前提到了，HashMap是线程不安全的，LinkedHashMap同样是线程不安全的。所以在对调用LinkedHashMap的put方法时，先使用synchronized 进行了同步操作。

我们最关心的是倒数第一行代码，其中maxSize为我们给LruCache设置的最大缓存大小。我们看看该方法：

    /**
     * Remove the eldest entries until the total of remaining entries is at or
     * below the requested size.
     *
     * @param maxSize the maximum size of the cache before returning. May be -1
     *            to evict even 0-sized elements.
     */
    public void trimToSize(int maxSize) {
        // while死循环，直到满足当前缓存大小小于或等于最大可缓存大小
        while (true) {
            K key;
            V value;
            // 线程不安全，需要同步
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }
                // 如果当前缓存的大小，已经小于等于最大可缓存大小，则直接返回
                // 不需要再移除LinkedHashMap中的数据
                if (size <= maxSize || map.isEmpty()) {
                    break;
                }
                // 得到的就是双向链表表头header的下一个Entry
                Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
                key = toEvict.getKey();
                value = toEvict.getValue();
                // 移除当前取出的Entry
                map.remove(key);
                // 从新计算当前的缓存大小
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

从注释上就可以看出，该方法就是不断移除LinkedHashMap中双向链表表头的元素，直到当前缓存大小小于或等于最大可缓存的大小。

由前面的重排序我们知道，对LinkedHashMap的put和get操作，都会让被操作的Entry移动到双向链表的表尾，而移除是从map.entrySet().iterator().next()开始的，也就是双向链表的表头的header的after开始的，这也就符合了LRU算法的需求。

下图表示了LinkedHashMap中删除、添加、get/put已存在的Entry操作。
红色表示初始状态
紫色表示缓存图片大小超过了最大可缓存大小时，才能够表头移除Entry1
蓝色表示对已存在的Entry3进行了get/put操作，把它移动到双向链表表尾
绿色表示新增一个Entry7，插入到双向链表的表尾（暂时不考虑在HashMap中的位置）

5 总结

LinkedHashMap是继承于HashMap，是基于HashMap和双向链表来实现的。
HashMap无序；LinkedHashMap有序，可分为插入顺序和访问顺序两种。如果是访问顺序，那put和get操作已存在的Entry时，都会把Entry移动到双向链表的表尾(其实是先删除再插入)。
LinkedHashMap存取数据，还是跟HashMap一样使用的Entry[]的方式，双向链表只是为了保证顺序。
LinkedHashMap是线程不安全的。

Hashtable与HashMap区别

1.线程安全
HashMap是线程不安全,Hashtable是线程安全,
原因:Hashtable线程不安全是因为其源码中的所有元素都是用synchronized同步关键字修饰的,HashMap没有,

2.效率性能优劣
HashMap因为是线程不安全的,所以效率比较高,Hashtable因为是线程安全的,每个方法都要阻塞其他的方法,排队执行,所有效率相比HashMap比较差
如果要线程安全又要保证性能，建议使用 JUC 包下的 ConcurrentHashMap。

3.null值
HashMap允许key和value为null,Hashtable不允许value为null;
HashMap允许为null是因为其对null做了处理,源码如下->

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

Hashtable不允许value为null是因为会报空指针异常,源码如下->

 public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

4.实现方式
HashMap继承的是AbstractMap类,Hashtable继承的是Dictionary类\

HashMap 的继承源码：

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

Hashtable 的继承源码：

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

5.容量扩容
HashMap初始容量:16,Hashtable初始容量:11,两个的负载因子都是0.75;
扩容规则:HashMap为翻倍,Hashtable为翻倍+1

HashMap源码如下:

    /**
     * Constructs an empty <tt>HashMap</tt> with the default initial capacity
     * (16) and the default load factor (0.75).
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

Hashtable源码如下:

    /**
     * Constructs a new, empty hashtable with a default initial capacity (11)
     * and load factor (0.75).
     */
    public Hashtable() {
        this(11, 0.75f);
    }

6.迭代器(Enumeration 和 Iterator 的区别)
HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
所以，当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出 ConcurrentModificationException 异常，而 Hashtable 则不会。

 public static void main(String[] args) {
        Map<String, String> hashtable = new Hashtable<>();
        hashtable.put("t1", "1");
        hashtable.put("t2", "2");
        hashtable.put("t3", "3");

        Enumeration<Map.Entry<String, String>> iterator1 = (Enumeration<Map.Entry<String, String>>) hashtable.entrySet().iterator();
        hashtable.remove(iterator1.nextElement().getKey());
        while (iterator1.hasMoreElements()) {
            System.out.println(iterator1.nextElement());
        }

        Map<String, String> hashMap = new HashMap<>();
        hashMap.put("h1", "1");
        hashMap.put("h2", "2");
        hashMap.put("h3", "3");

        Iterator<Map.Entry<String, String>> iterator2 = hashMap.entrySet().iterator();
        hashMap.remove(iterator2.next().getKey());
        while (iterator2.hasNext()) {
            System.out.println(iterator2.next());
        }
    }

t2=2
t1=1
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
	at com.utaka.united.promotion.service.DiscountActivityService.main(DiscountActivityService.java:1338)

Collections工具类

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

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 obj):返回指定集合中指定对象出现的次数
replaceAll(List list,Object old,Object new):替换


3、同步控制
Collections工具类提供了多个synchronizedXxx方法，该方法返回指定集合对象对应的同步对象，从而解决多线程并发访问集合时
线程的安全问题。HashSet、ArrayList、HashMap都是线程不安全的，如果需要考虑同步，则使用这些方法。这些方法主要有：synchronizedSet、synchronizedSortedSet、synchronizedList、synchronizedMap、synchronizedSortedMap
特别需要注意：在使用迭代方法遍历集合时需要手工同步返回的集合。{否则会有线程安全的问题}

4、设置不可变得结合
Collections工具类有三种方法返回一个不可变集合

emptyXxx():        返回一个空的不可变的集合对象
singletonXxx():    返回一个只包含指定对象的，不可变的集合对象
unmodifiableXxx(): 返回指定集合对象的不可变视图

5、其它
disjoint(Collections<?>c1,Collections<?>c2) 
    如果两个指定collection中没有相同的元素，则返回true
addAll(Collection<?super T>c,T...a) 
    一种方便的方式，将所有指定元素添加到指定collection中
Comparator<T>reverseOrder(Comparator<T>cmp)
    返回一个比较器，它强行反转指定比较器的顺序。如果指定比较器为null，则
此方法等同于reverseOrder(){返回一个比较器，它对实现 Comparable接口的对
象集合施加了 自然排序的相反}

向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

云原生

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

云原生

所有评论(0)

查看更多评论

refuse-debug

@refuse_debug

已为社区贡献1条内容

集合（全）

refuse-debug

集合

概述：

区别

特点

体系图

Collection 接口

功能

一、添加

二、删除

三、判断

四、获取功能

五、长度功能

六、交集功能

七、集合转换数组

迭代器 ：Iterator接口

理解：

源码：

List接口

特点

特有功能

列表迭代器ListIterator

遍历

一、（List特有）

二、迭代器

子类特点

并发修改异常

ArrayList

基本操作：

Vector

特有功能：

Linkedlist

特有方法

去除集合中重复元素

应用

增强For

格式

静态导入

概述：

可变参数

Set接口

HashSet

特点

LinkedHashSet

特点

TreeSet

特点

排序

A：自然排序

B:比较器排序

Map集合

概念

特点

常用方法

1、添加

2、删除

3、判断功能

4、获取功能

5、长度：

遍历

方式一

方式二

HashMap

TreeMap

自定义元素排序

LinkedHashMap

2.1 应用场景

2.2 简单使用

2.3 定义

2.4 构造方法

2.5 put方法

2.7 双向链表的重排序

2.8 get方法

2.9 遍历方式取数据

2.10 remove方法

HashMap与LinkedHashMap的结构对比

5 总结

Hashtable与HashMap区别

Collections工具类

迭代器：Iterator接口