Java集合汇总

﹏ヽ暗。殇╰゛Y 2023-09-26 09:27 45阅读 0赞

#### 文章目录 ####

*  集合框架
 *   *  一、框架的概念
     *  二、集合
     *  三、Collection体系集合
     *  四、List集合
     *   *  4.1 有序无序排序
         *  4.2 ArrayList【重点】
         *  4.3 ArrayList原理
         *  4.4 LinkedList用法
         *   *  4.4.1数组和链表
             *  4.4.2 LinkedList特有的具有链表特点的方法
         *  4.5 LinkedList原理
         *  4.6 Vector
     *  五、泛型
     *   *  5.1 泛型的基本使用
         *  5.2 自定义泛型
         *   *  5.2.1 自定义泛型类
             *  5.2.2 自定义泛型方法
         *  5.3 泛型中的extends 和 super
     *  六、Collections类
     *  七、Set集合
     *   *  7.1 HashSet【重点】
         *   *  7.1.1 用法
             *  7.1.2 原理
         *  7.2 LinkedHashSet用法
         *  7.3 TreeSet
     *  八、Map体系集合
     *   *  8.1 HashMap【重点】
         *  8.2 HashMap的原理
         *  8.3 Hashtable\[了解\]
         *  8.4 Properties
         *  8.5 TreeMap

## 集合框架 ##

### 一、框架的概念 ###

> 系统或者第三方提供的有特定功能的类。作用是减少编程过程中的细节开发，提升编程效率，减少代码量。

### 二、集合 ###

> 和数组类似，可以存储多个对象。提供了一系列操作的方法（增删改查等）。

> 与数组的区别：
> 
>  *  数组长度固定，集合长度不固定（会自动扩容）
>  *  数组可以存储基本数据类型和引用数据类型，集合只能存储引用数据类型

> 所有的集合都在java.util包中。

### 三、Collection体系集合 ###

> 在Java中，集合的体系有几种，常见的有Collection，Map，Queue等。
> 
> Collection是一种线性集合，可以循环。
> 
> Map是采用key-value模式的集合。
> 
> Queue是一种采用队列的方式的集合。

> Collection是一个顶层接口，它有两个子接口：List和Set。

> Collection接口中的方法：

add(Object obj); // 添加对象
    addAll(Collection c); // 将另一个集合中的所有对象添加当前集合
    clear(); // 清空集合
    contains(Object obj); // 判断集合中是否包含某个对象
    isEmpty(); // 判断集合是否为空
    remove(Object obj); // 删除一个对象
    size(); // 得到集合中元素的数量
    toArray(); // 将集合转换成数组

### 四、List集合 ###

> 特点是：有序、有下标，元素可以重复。

#### 4.1 有序无序排序 ####

> 有序：即会记住元素添加的顺序。
> 
> 无序：不会记住元素添加的顺序。
> 
> 排序：虽然不会记住元素添加的顺序，但是会按照指定的规则将元素进行排序 。

> List接口添加的方法：

add(int index, Object obj); // 将元素插入到指定的下标位置
    addAll(int index, Collection c); // 将另一个集合中的所有对象添加当前集合的指定下标位置
    get(int index); // 得到指定下标处的元素
    subList(int fromIndex, int toIndex); // 截取集合中的一部分形成一个新的集合

#### 4.2 ArrayList【重点】 ####

> 是以数组的形式为底层，存放元素的集合。

> 基本使用：

public class TestArrayList {
        
    	public static void main(String[] args) {
        
    		// 以数组为底层，所以在创建时可以指定大小
    		ArrayList<String> list = new ArrayList<String>(20); 
    		// 添加元素
    		list.add("hello");
    		list.add("world");
    		list.add("aaa");
    //		list.add(3);
    		// 根据下标获取元素
    		String s = list.get(1);
    		System.out.println(s);
    		// 遍历元素
    		// list.size()得到元素的个数
    		for (int i = 0; i < list.size(); i++) {
        
    			String str = list.get(i);
    			System.out.println(str);
    		}
    		// 清空
    //		list.clear();
    		
    		// 根据下标删除，不要在循环遍历时删除元素
    //		list.remove(1);
    		// 根据元素删除，如果是自定义类型，需要重写equals
    //		list.remove("hello");
    		
    		// 根据下标修改元素
    //		list.set(1, "bbb");
    		
    		// 判断集合是否包含元素
    //		System.out.println(list.contains("hello"));
    		// 查找元素的下标，没找到返回-1
    		int index = list.indexOf("world");
    		System.out.println(index);
    		// 从最后开始查找
    		int index1 = list.lastIndexOf("world");
    		System.out.println(index1);
    		
    		ArrayList<String> list1 = new ArrayList<String>(); 
    		list1.add("1111");
    		list1.add("2222");
    		// 将list1中的所有元素添加到list中
    		list.addAll(list1);
    		
    		// 判断是否为空
    		System.out.println(list.isEmpty());
    		
    		// 使用foreach遍历
    		for (String string : list) {
        
    			System.out.println(string);
    		}
    		
    		// 得到迭代器，并使用迭代器进行循环
    		Iterator<String> it = list.iterator();
    		while(it.hasNext()) {
        
    			String temp = it.next();
    			System.out.println(temp);
    		}
    		
    		String s1 = "hellohellohello";
    		System.out.println(s1.indexOf("llo")); // 2
    		System.out.println(s1.lastIndexOf("llo")); // 12
    	}
    }

#### 4.3 ArrayList原理 ####

>  *  当使用无参构造方法时会创建空数组
>  *  当使用无参构造方法创建空数组后，第一次添加元素会将数组大小扩容为10
>  *  数组扩容的临界点为当数组已满，再次添加新的元素时需要扩容
>  *  扩容因子为：每次扩容大小为原大小的1.5倍。
>  *  当扩容1.5倍超出范围时，就只扩容一个
>  *  当扩容后的空间大小大于最大值-8，直接使用最大值，如果已经是最大值，无法扩容，报错

// 默认空间大小
    private static final int DEFAULT_CAPACITY = 10;
    // 空数组
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    // 默认空间时的空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    // 存储元素的空间
    transient Object[] elementData;
    // 集合元素的个数
    private int size;
    // 最大大小
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 使用无参构造方法时创建空数组
    public ArrayList() {
        
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // 根据大小创建集合
    public ArrayList(int initialCapacity) {
        
        // 当空间大于0时，会创建指定大小的数组
        if (initialCapacity > 0) {
        
            this.elementData = new Object[initialCapacity];
            // 当为0时，创建空数组
        } else if (initialCapacity == 0) {
        
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        
            // 当大小为负数时，报错
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    // 返回元素个数
    public int size() {
        
        return size;
    }
    
    // 添加元素
    public boolean add(E e) {
        
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 添加元素到当前(元素个数)位置，并且元素个数加1
        elementData[size++] = e;
        return true;
    }
    
    //
    private void ensureCapacityInternal(int minCapacity) {
        
        // 当通过无参构造创建了空数组时，如果要添加元素
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        
            // 第一次添加元素时，会将数组扩容为10
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        
        modCount++; // 修改次数
    
        // overflow-conscious code
        // 当需要的最小空间比原来的空间大，必须扩容
        if (minCapacity - elementData.length > 0)
            // 扩容
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        
        // overflow-conscious code
        // 原始大小
        int oldCapacity = elementData.length;
        // 新大小等于原大小的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 当超出范围时，就只扩容一个
        // 当空数组第一次扩容时，为10
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        
        // 如果新的空间大小大于最大值-8，直接使用最大值，如果已经是最大值，报错
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
    
    private static int hugeCapacity(int minCapacity) {
        
        // 如果原大小+1得到的minCapacity小于零，说明原大小已经是最大值，此时无法扩容，直接报错
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
    }

> 经典面试题：
> 
> 使用无参构造方法创建了一个ArrayList，向其中添加11个元素，扩容了几次。
> 
> 答：2次

#### 4.4 LinkedList用法 ####

> LinkedList的基本用法与ArrayList的基本用法基本一致。
> 
> 但是添加了一些Linked链表相关的用法。

##### 4.4.1数组和链表 #####

> 数组的特点：
> 
>  *  长度固定，超出长度需要扩容
>  *  增删慢，遍历快
> 
> 链表特点：
> 
>  *  不需要关心扩容问题
>  *  有单向链表和双向链表之分
>  *  增删快（最快是首尾），遍历较慢

##### 4.4.2 LinkedList特有的具有链表特点的方法 #####

public class Test1 {
        
    	public static void main(String[] args) {
        
    		LinkedList<String> list = new LinkedList<String>(); 
    		// 添加元素
    		list.add("aaa"); // 添加默认添加到尾
    		list.addFirst("bbb");// 添加到头
    		list.addLast("ccc"); // 添加到尾
    		
    		String first = list.getFirst(); // 获取头部元素
    		String last = list.getLast(); // 获取尾部元素
    		
    		// 删除头部和尾部
    //		list.removeFirst();
    //		list.removeLast();
        }
    }

#### 4.5 LinkedList原理 ####

>  *  每一个元素被封装成一个节点，包含当前元素，以及上下节点的地址
>  *  当添加元素时，默认添加到尾部

// 头位置
    transient Node<E> first;
    // 尾位置
    transient Node<E> last;
    
    // 节点类
    private static class Node<E> {
        
        E item; // 当前元素
        Node<E> next; // 下一个节点
        Node<E> prev; // 上一个节点
    
        // 上一个节点，当前元素，下一个节点
        Node(Node<E> prev, E element, Node<E> next) {
        
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    public LinkedList() {
        
    }
    
    // 添加
    public boolean add(E e) {
        
        linkLast(e); // 添加到尾部
        return true;
    }
    
    // 尾部添加
    public void addLast(E e) {
        
        linkLast(e);
    }
    
    // 头部添加
    public void addFirst(E e) {
        
        linkFirst(e);
    }
    
    void linkLast(E e) {
        
        // 记住当前的尾部节点
        final Node<E> l = last;
        // 将添加的元素创建成一个新的节点，上一个节点为原来的尾部，下一个节点为null，意味着当前节点就是尾部
        final Node<E> newNode = new Node<>(l, e, null);
        // 将当前节点指定为尾部
        last = newNode;
        // 当前添加的节点是第一个节点
        if (l == null)
            // 将当前节点也设置为头部
            first = newNode;
        else
            // 将之前的尾部的下一个地址记录为当前节点
            l.next = newNode;
        size++; // 元素个数加1
        modCount++; // 修改次数加1
    }
    
    
    private void linkFirst(E e) {
        
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

#### 4.6 Vector ####

> 与ArrayList用法几乎一样。
> 
> Vector绝大部分的操作方法都添加了线程安全的方式，性能非常低下。
> 
> 不推荐使用，如果要使用线程安全的ArrayList，应该使用CopyOnWriteArrayList。

### 五、泛型 ###

#### 5.1 泛型的基本使用 ####

> 作用：
> 
>  *  在设置或传递参数时，限制参数的类型，编译时检查
>  *  在获得值，转换类型

public class Test2 {
        
    	public static void main(String[] args) {
        
    		ArrayList list = new ArrayList();
    		// 在没有使用泛型时，可以添加任意类型，没有限制
    		list.add("aaa");
    		list.add(3);
    		
    		// 在没有使用泛型时，返回类型需要自己转换
    		String str = (String)list.get(0);
    		System.out.println(str);
    		
    		ArrayList<String> list1 = new ArrayList<String>();
    		// 在没有使用泛型时，只能添加指定泛型类型，会编译检查
    //		list1.add(4); // 编译报错
    		list1.add("hello");
    		
    		// 在使用泛型时，返回类型会自动转换
    		String str1 = list1.get(0);
    		System.out.println(str1);
    	}
    }

> 泛型有泛型类（接口）、泛型方法。

> 语法：
> 
> 一般使用一个字母代替类型（Object）。称为类型占位符，代表一种引用类型。

> 泛型集合，就是使用泛型的集合。

#### 5.2 自定义泛型 ####

> 自定义泛型分为泛型类和泛型方法。

##### 5.2.1 自定义泛型类 #####

public class MyClass<T> {
         // 如果需要定义多个泛型，可以使用逗号隔开
    	private T obj;
    	
    	public void set(T obj) {
        
    		this.obj = obj;
    	}
    	
    	public T get() {
        
    		return obj;
    	}
    }

public class Test3 {
        
    	public static void main(String[] args) {
        
    		MyClass<String> c = new MyClass<>();
    		c.set("hello");
    		String str = c.get();
    		System.out.println(str);
    	}
    }

##### 5.2.2 自定义泛型方法 #####

public class MyClass1 {
        
    	public static <T> T test(T t) {
        
    		return null;
    	}
    }

#### 5.3 泛型中的extends 和 super ####

> 在泛型参数时使用，extends 表示必须是该类或者该类的子类。super表示必须是该类或者该类的父类

public class MyClass {
        
        // 使用ArrayList泛型必须是B或者B的父类
    	private ArrayList<? super B> list;
    	
    	public void set(ArrayList<? super B> list) {
        
    		this.list = list;
    	}
    	
    	public ArrayList<? super B> get() {
        
    		return list;
    	}
    }

public class MyClass {
        
        // 使用ArrayList泛型必须是B或者B的子类
    	private ArrayList<? extends B> list;
    	
    	public void set(ArrayList<? extends B> list) {
        
    		this.list = list;
    	}
    	
    	public ArrayList<? extends B> get() {
        
    		return list;
    	}
    }

> 经典面试题：
> 
> 为什么说Java中的泛型是伪泛型（假泛型）？
> 
> Java中的泛型仅仅是在设置时进行了编译检查，在取出的时候进行强转，在使用过程中还是Object，并没有在内部进行检查，所以说Java中的泛型是一个伪泛型。

### 六、Collections类 ###

> 是集合的工具类，给集合添加一些操作方法，类似于Arrays类。

> 常用方法：
> 
> reverse(List list)反转集合。
> 
> sort(List list)排序，自定义类需要重写comparable接口
> 
> shuffle(List list)随机打乱

public class Test4 {
        
    	public static void main(String[] args) {
        
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		list.add(23);
    		list.add(45);
    		list.add(9);
    		list.add(11);
    		list.add(34);
    		
    		System.out.println(list);
    		// 排序
    		Collections.sort(list);
    		System.out.println(list);
    		
    		// 随机打乱
    		Collections.shuffle(list);
    		System.out.println(list);
    		
    		// 反序
    		Collections.reverse(list);
    		System.out.println(list);
    		
    		
    		ArrayList<Student> list1 = new ArrayList<Student>();
    		
    		list1.add(new Student("3", "张三3"));
    		list1.add(new Student("1", "张三1"));
    		list1.add(new Student("4", "张三4"));
    		list1.add(new Student("5", "张三5"));
    		list1.add(new Student("2", "张三2"));
    		
    		System.out.println(list1);
    		// 排序
    		Collections.sort(list1);
    		System.out.println(list1);
    	}
    }

public class Student implements Comparable<Student>{
        
    	private String id;
    	private String name;
    	public String getId() {
        
    		return id;
    	}
    	public void setId(String id) {
        
    		this.id = id;
    	}
    	public String getName() {
        
    		return name;
    	}
    	public void setName(String name) {
        
    		this.name = name;
    	}
    	public Student(String id, String name) {
        
    		super();
    		this.id = id;
    		this.name = name;
    	}
    	public Student() {
        
    		super();
    	}
    	@Override
    	public String toString() {
        
    		return "Student [id=" + id + ", name=" + name + "]";
    	}
    	
    	// 比较
    	@Override
    	public int compareTo(Student o) {
        
    //		if(this.id.hashCode() > o.id.hashCode()) {
        
    //			return 1;
    //		}else if(this.id.hashCode() < o.id.hashCode()){
        
    //			return -1;
    //		}else {
        
    //			return 0;
    //		}
    		return this.id.hashCode() - o.id.hashCode();
    	}
    }

> 经典面试题：
> 
> Collection与Collections的区别？
> 
> 答：Collection是一个集合的顶层接口。Collections是集合的帮助（工具）类。

### 七、Set集合 ###

> 无序、无下标，元素不可重复

#### 7.1 HashSet【重点】 ####

##### 7.1.1 用法 #####

> 注意：自定义类的对象如果要用HashSet去重，需要重写equals和hashCode方法。

public class TestHashSet {
        
    	public static void main(String[] args) {
        
    		HashSet<String> set = new HashSet<String>();
    		// 添加元素
    		set.add("aaa");
    		set.add("bbb");
    		set.add("ccc");
    		// 重复元素不能添加
    		set.add("aaa");
    		set.add("bbb");
    		set.add("ccc");
    		// 使用迭代器遍历
    		Iterator<String> it = set.iterator();
    		while(it.hasNext()) {
        
    			String str = it.next();
    			System.out.println(str);
    		}
    		set.remove("bbb");
    		// 遍历
    		for (String string : set) {
        
    			System.out.println(string);
    		}
    	}
    }

> 经典面试题：
> 
> 有一个ArrayList，里面存放了很多个元素，有部分元素是重复的，如果去掉重复的元素？
> 
> 答：直接使用HashSet保存，会去重。

##### 7.1.2 原理 #####

>  *  底层使用的HashMap实现，将添加的元素放置到map的key上，所以无序，无下标，元素不能重复。
>  *  不能重复是通过hashCode和equals来比较。

// 利用HashMap实现HashSet
    private transient HashMap<E,Object> map;
    // 使用最小空间占位
    private static final Object PRESENT = new Object();
    // 创建时实际创建的是一个HashMap
    public HashSet() {
        
        map = new HashMap<>();
    }
    
    // 实际上就是向map中添加了一个元素，将添加的内容作为key，所以不能重复，将Object的对象作为值
    public boolean add(E e) {
        
        return map.put(e, PRESENT)==null;
    }

#### 7.2 LinkedHashSet用法 ####

> 将HashSet使用链表记录了添加的顺序。
> 
> 继承了HashSet，在创建对象时使用LinkedHashMap构造，添加了顺序。

public class TestLinkedHashSet3 {
        
    	public static void main(String[] args) {
        
    		LinkedHashSet<String> set = new LinkedHashSet<String>();
    		// 添加元素
    		set.add("aaa");
    		set.add("bbb");
    		set.add("ccc");
    		
            // 如果是Hashset，遍历顺序是aaa\ccc\bbb，使用了LinkedHashSet，记录了添加的顺序，遍历时顺序还是aaa\bbb\ccc
    		
    		// 遍历
    		for (String string : set) {
        
    			System.out.println(string);
    		}
    	}
    }

#### 7.3 TreeSet ####

> 以树为底层，元素进行排序，
> 
>  *  基于排序实现的元素不重复
>  *  存放的对象需要使用Comparable接口

public class TestTreeSet {
        
    	public static void main(String[] args) {
        
    		TreeSet<Student> set = new TreeSet<Student>();
    		set.add(new Student("1", "张三1"));
    		set.add(new Student("3", "张三3"));
    		set.add(new Student("4", "张三4"));
    		set.add(new Student("2", "张三2"));
    		
    		// 遍历
    		for (Student student : set) {
        
    			System.out.println(student);
    		}
    	}
    }

### 八、Map体系集合 ###

> 含义是映射。
> 
> 存放元素时使用key-value（键值对）方式，key不能重复，value可以重复。

> 当需要快速在集合中找到想要的元素时，使用map。

// 常见方法
    put(Object key, Object value); // 添加，名称和内容，名称推荐用String
    get(Object key); // 根据key查找值
    Set keySet(); // 键集，得到所有的key形成的一个集合
    Collection values(); // 值集，得到所有的值形成的一个集合
    Set entrySet(); // 键值的集合

#### 8.1 HashMap【重点】 ####

> 基本用法：

public class TestHashMap {
        
    	public static void main(String[] args) {
        
    		HashMap<String, Student> map = new HashMap<>();
    		// 添加元素
    		map.put("1001", new Student("1", "张三1"));
    		map.put("1002", new Student("2", "张三2"));
    		map.put("1003", new Student("3", "张三3"));
    		map.put("1004", new Student("4", "张三4"));
    		// 键不能重复，如果重复，会覆盖前面的值
    		map.put("1004", new Student("5", "张三5"));
            // key和value都可以为null，但是key不能重复
    		map.put(null, null);
    		map.put(null, new Student("6", "张三6"));
    		
    		// 获取元素，如果key不存在，会返回null
    		Student stu = map.get("1003");
    		System.out.println(stu);
    		
    		// 得到值集
    		Collection<Student> values = map.values();
    		for (Student student : values) {
        
    			System.out.println(student);
    		}
    		
    		// 得到键集
    		Set<String> set = map.keySet();
    		for (String string : set) {
        
    			System.out.println(string + "====" + map.get(string));
    		}
    		
    		// 通过key删除，当key不存在时，不会进行删除
    		map.remove("1008");
    		
    		// 得到键值集合
    		Set<Entry<String, Student>> entrySet = map.entrySet();
    		for (Entry<String, Student> entry : entrySet) {
        
    			System.out.println(entry.getKey() + "===" + entry.getValue());
    		}
    	}
    }

public class TestHashMap1 {
        
    	public static void main(String[] args) {
        
    		HashMap<Student, String> map = new HashMap<>();
    		// 如果使用对象作为key，还是通过hashCode和equals方法判断key是否相同
    		map.put(new Student("1", "张三1"),  "1001");
    		map.put(new Student("1", "张三2"),  "1002");
    		
    		// 得到键集
    		Set<Student> set = map.keySet();
    		for (Student student : set) {
        
    			System.out.println(student + "====" + map.get(student));
    		}
    	}
    }

#### 8.2 HashMap的原理 ####

> JDK1.7之前都是数组+链表的形式，既有数组的优点，也有链表的优点。
> 
> JDK1.8后，增加了红黑树。

>  *  当创建HashMap后，首次添加元素后会创建空间。
>  *  如果没有指定空间大小，默认为16。
>  *  每次扩容为原本的两倍。
>  *  默认扩容因子为0.75，临界点大小为原本的长度\*扩容因子。
>  *  添加元素时，先通过key的hash与hash表的长度求余数，找到对应的桶（bucket）的位置。
>  *  如果该位置没有内容，直接将元素以链表的形式放在首节点。
>  *  如果该位置有链表的节点，那么依次比较整条链表的元素，查找是否有相同的key，如果有，则覆盖值，如果没有则添加到尾部。添加时判断是否满足变树的要素，如果满足，则变树。
>  *  如果该位置有树的节点，那么依次比较树上的元素，查找是否有相同的key，如果有，则覆盖值，如果没有则添加树中。
>  *  hash表需要的空间大小，会根据传入的大小计算最小需求的2的整数次方。
>  *  每次扩容需要将整个结构中的元素重新排列。
>  *  当数组长度达到64，并且某个链表上节点数量大于等于8，则变树，如果只是节点数量达到8，但是长度没有达到64，则扩容。

// 默认空间大小16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    // 最大空间大小2^30
    static final int MAXIMUM_CAPACITY = 1 << 30;
    // 默认扩容的加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    // 变树临界点
    static final int TREEIFY_THRESHOLD = 8;
    // 变链表临界点
    static final int UNTREEIFY_THRESHOLD = 6;
    // 总元素超过64个才会变树
    static final int MIN_TREEIFY_CAPACITY = 64;
    
    // 节点，包含键值，hash，下一个元素，单向链表
    static class Node<K,V> implements Map.Entry<K,V> {
        
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    
        Node(int hash, K key, V value, Node<K,V> next) {
        
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        public final K getKey()        {
         return key; }
        public final V getValue()      {
         return value; }
        public final String toString() {
         return key + "=" + value; }
    
        public final int hashCode() {
        
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        public final V setValue(V newValue) {
        
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
    
        // 节点比较相等，键值都相等
        public final boolean equals(Object o) {
        
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
        
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }
    
    // 根据key计算hash
    static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    // map存储数据空间，数组存放链表
    transient Node<K,V>[] table;
    
    // 仅指定加载因子为0.75，数组都没有创建
    public HashMap() {
        
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    
    // 指定大小
    public HashMap(int initialCapacity) {
        
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public HashMap(int initialCapacity, float loadFactor) {
        
        // 大小为负数，报错
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // 大小大于2^30，直接等于2^30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        
        // 加载因子为负数或不数字，报错
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        
        // 根据设置的大小，计算最终的大小
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    // 根据传入的大小，计算结果为最近的2的n次方，例如传入11，会计算为16，传入17，计算为32，传入33，计算为64
    static final int tableSizeFor(int cap) {
        
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
        // 定义了链表数组tab，节点p
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 将table赋值到tab中，当table为null或者长度为0，即判断是否为空
        if ((tab = table) == null || (n = tab.length) == 0)
            // 创建数组，此时为16
            n = (tab = resize()).length;
        // 将key计算出来的hash与长度减1进行与运算（即与长度求模）
        // i为数组中存放的下标
        // p即为数组中的首节点
        // 如果首节点为空
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 直接将对象放到首节点
            tab[i] = newNode(hash, key, value, null);
        // 如果首节点有内容
        else {
        
            // 定义一个节点，一个key
            Node<K,V> e; K k;
            // 如果hash相同，并且地址相同，或者当地址不同时，key不为空，equals比较相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                // 把原来的首节点记住
                e = p;
            // 如果首节点是树的节点
            else if (p instanceof TreeNode)
                // 将对象挂在树上(可能是覆盖，可能是添加)
                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
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 变树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果在链表上发现key相同
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    // 将p赋值为key相同的节点
                    p = e;
                }
            }
            // 将相同key的对象，value进行覆盖
            if (e != null) {
         // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        
        // 修改次数+1
        ++modCount;
        // 长度+1
        // 如果长度大于临界点长度，则需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
    
    final Node<K,V>[] resize() {
        
        // 定义临时变量记住原map内容
        Node<K,V>[] oldTab = table;
        // 得到原table的数组长度，如果为空，则为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 原扩容临界点大小
        int oldThr = threshold;
        // 新的数组大小，和扩容临界点大小
        int newCap, newThr = 0;
        // 如果原大小大于0
        if (oldCap > 0) {
        
            // 如果原本大小大于等于最大大小
            if (oldCap >= MAXIMUM_CAPACITY) {
        
                // 将扩容临界点设置为最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 新的空间大小是原空间大小的2倍（扩大1倍）
            // 大于等于16，并且小于2^30
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 临界点扩大1倍
                newThr = oldThr << 1; // double threshold
        }
        // 如果原需要大小大于0（手动指定空间大小）
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {
                       // zero initial threshold signifies using defaults
            // 指定空间大小为16
            newCap = DEFAULT_INITIAL_CAPACITY;
            // 扩容临界点为12（0.75 * 16）
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 扩容临界点为0时
        if (newThr == 0) {
        
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 设置下一次扩容需要的大小
        threshold = newThr;
        @SuppressWarnings({
        "rawtypes","unchecked"})
        // 创建节点数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // 使用属性记住空间
        table = newTab;
        // 如果原来的table中有内容，重新放置内容
        if (oldTab != null) {
        
            for (int j = 0; j < oldCap; ++j) {
        
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
        
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
         // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
        
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
        
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
        
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
        
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
        
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        
        // 将新的空间返回
        return newTab;
    }
    
    
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        
        int n, index; Node<K,V> e;
        // 如果数组长度小于64，会扩容，而不会变树
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
        
            TreeNode<K,V> hd = null, tl = null;
            do {
        
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
        
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

#### 8.3 Hashtable\[了解\] ####

> Hashtable用法与HashMap几乎一样。
> 
> 但是key和value都不能为空。
> 
> Hashtable绝大部分的操作方法都添加了线程安全的方式，性能非常低下。
> 
> 不推荐使用，如果要使用线程安全的HashMap，应该使用ConcurrentHashMap。

#### 8.4 Properties ####

> 是Hashtable的子类，键值都应该使用String，用来读取配置文件。

> 在src目录下新建一个config.properties文件

jdbc.username=admin
    jdbc.password=123456
    jdbc.url=jdbc:mysql://localhost:3306/shop?useUnicode=true&characterEncoding=utf-8
    jdbc.driver=com.mysql.jdbc.Driver

public class TestProperties {
        
    	public static void main(String[] args) throws IOException {
        
    		// 创建一个集合
    		Properties prop = new Properties();
    		// 将配置文件加载成一个流
    		InputStream inputStream = TestProperties.class
    				.getResourceAsStream("/config.properties"); // 路径
    		// 将流中的信息保存到集合中
    		prop.load(inputStream);
    //		System.out.println(prop);
    		// 获取信息并打印
    		String url = prop.getProperty("jdbc.url");
    		System.out.println(url);
    		String username = prop.getProperty("jdbc.username");
    		System.out.println(username);
    		String password = prop.getProperty("jdbc.password");
    		System.out.println(password);
    		String driver = prop.getProperty("jdbc.driver");
    		System.out.println(driver);
    	}
    }

#### 8.5 TreeMap ####

> 会将key进行排序。不会对值排序。
> 
> 如果key是自定义对象，那么需要实现Comparable接口。重写compareTo方法。用法与HashMap基本一致。
> 
> 由于要使用key进行排序，所以不能为空。