Collection接口

三代集合类发展过程

1、第一代线程安全集合类

Vector、Hashtable
是怎么保证线程安全的：使用synchronized修饰方法
缺点效率低下

2、第二带线程非安全集合类（主流）

ArrayList、HashMap（LinkedList也是线程不安全的）
线程不安全，但性能好，用来替代Vector、Hashtable

使用ArrayList和HashMap，需要线程安全怎么办？
使用
Collection.synchronizedList(List);
Collection.synchronizedList(map);

底层使用synchronized代码块锁
虽然也是锁住了所有的代码，但是锁在方法里边，比所在方法外边性能可以理解为稍有提高吧，毕竟方法本身就要分批资源的

等看完锁再看这个视频https://www.bilibili.com/video/BV15Z4y1G7RY?p=12

2、第二带线程安全集合类（波浪式前进，螺旋式上升）

在大量并发情况下如何提高集合的效率和安全呢？

java.util.concurrent.*
ConcurrentHashMap:
CopyOnWriteArrayList:
CopyOnWriteArraySet: 注意不是CopyOnWriteHashSet

底层大都是采用Lock锁（1.8的ConcurrentHashMap不使用Lock锁），保证安全的同时，性能也很高

集合和数组的区别

1、集合与数组存储数据概述：
集合、数组都是对多个数据进行存储操作的结构，简称Java容器
说明：此时的存储，主要值的是内存层次的存储，不涉及到持久化的存储（.txt, .jpg, .avi, 数据库中）
2、数组存储的特点

• 一旦初始化以后，其长度就确定了
• 数组一旦定义好，其元素的类型也就确定了。我们也就只能操作指定类型的数据了。

3、数组存储的弊端：

• 一旦初始化以后，其长度不能被修改
• 数组中提供的方法非常限制，对于添加，删除，插入数据等操作，非常不便，同时效率不高
• 获取数组中实际元素的个数的需求，数组没有现成的属性或方法可用
• 对于无序、不可重复的需求，不能满足

4、集合存储的优点
解决数组存储数据方面的缺点

Collection接口：单例集合，用来存储一个一个对象

image.png

Collection接口的注意事项
（1）向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals()，例如contains(Object obj)方法中，判断当前集合是否包含obj，判断时会调用obj对象所在类的equals()
（2）集合 --> 数组：toArray()

        Collection coll = new ArrayList();
        Object[] arr = coll.toArray();

（3）数组 -> 集合：调用Arrays类的静态方法asList()

• 若数组中元素的类型是封装类型或String时，使用Arrays.asList()能顺利的将数组转换成List<T>

• 若数组中元素的类型是基础数据类型时，使用Arrays.asList()只能将其转换成List<T[ ]>

public class MyTest5 {
    public static void main(String[] args) {
        Collection coll = new ArrayList();

        List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
        System.out.println(list);//[AA, BB, CC]

        List arr1 = Arrays.asList(new int[]{123, 456});
        System.out.println(arr1.size());//1

        List arr2 = Arrays.asList(new Integer[]{123, 456});
        System.out.println(arr2.size());//2
    }
}

一、Iterator迭代器接口

作用：可以通过迭代器遍历集合中的数据
3个主要方法
1、hasNext()判断是否还有下一个元素
2、next() （1）指针下移（2）将下移以后集合位置上的元素返回
3、remove() 可以在遍历时删除集合中的元素。此方法不同于集合直接调用remove()
4、集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前

二、foreach循环

首先说一下foreach有的也叫增强for循环，foreach其实是for循环的一个特殊简化版。相比于for循环，foreach循环在简洁性、灵活性、以及出错预防性方面都占有绝对优势，并没有性能惩罚的问题

• foreach适用于只是进行集合或数组遍历，for则在较复杂的循环中效率更高。
• foreach不能对数组或集合进行修改（添加删除操作），如果想要修改就要用for循环。

foreach写法
（1）这里的str就是为了获取每次循环的arr中的值
（2）就相当于 String str=arr[i]

public static void main(String[] args) {
        List<String> arr = new ArrayList<String>();
        arr.add("你好");
        arr.add("我好");
        arr.add("大家好");

        //foreach循环
        for(String str : arr){                    　　//这里的str就是为了获取每次循环的arr中的值
            System.out.println(str);           　　　 //就相当于 String str=arr[i]
        }
    }

for写法

public static void main(String[] args) {
        List<String> arr = new ArrayList<String>();
        arr.add("你好");
        arr.add("我好");
        arr.add("大家好");
        
        //for循环
        for(int i=0;i<arr.size();i++){
            System.out.println(arr.get(i));    //要获取list中元素需要用get方法    
        }
    }

易错:

public class MyTest5 {
    public static void main(String[] args) {
        String[] arr = new String[]{"MM", "MM", "MM"};

        //写法1：普通for赋值
        for(int i = 0;i < arr.length;i ++){
            arr[i] = "GG";
        } 
        //写法2：foreach赋值
        for(String str : arr){
            str = "GG";
        }
        for(int i = 0;i < arr.length;i ++){
            System.out.println(arr[i]);
        }
    }
}

写法1：输出"GG"，"GG"，“GG”
写法2：输出“MM”，“MM”，“MM”
foreach赋值的时候，是将元素赋值到str中，然后修改str，可是本质上arr[i]位置的元素却没有变

三、List接口：存储有序，可重复的数据（动态数组）

1、ArrayList：作为List接口的主要实现类，线程不安全，效率高，底层使用Object[] elementData存储（查询快，插入慢）
2、LInkedList：对于频繁的插入、删除操作，使用此类效率比ArrayList高；底层使用双向链表存储（查询慢，插入快）
3、Vector：作为List接口的古老实现类，线程安全，效率低，底层使用Object[] elementData存储

1、ArrayList的源码分析

ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}，并没有创建长度是10的数组
list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData数组中
...
list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容
默认情况下，扩容为原来的容量的1.5倍，同时需要将原来数组中的数据复制到新的数组中

结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity)

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

2、LinkedList的源码分析

LinkedList list = new ArrayList();//内部声明了Node类型的first和last属性，默认值为null
list.add(123);//将123封装到Node中，创建Node对象

3、Vector的源码分析

jdk7和jdk88中通过Vector()构造器创建对象时，底层都创建了长度为10的数组，在扩容方面，默认扩容为原来的数组长度的2倍

四、Set接口：存储无序，不可重复的数据（高中讲的集合）

1、哈希表原理

1、计算哈希码 x = key.hashCode()
2、根据哈希码计算存储位置 y = x % 11
3、存入指定的位置

• 情况1：如果是空，直接添加一个结点即可
• 情况2：如果不为空，调用equals进行比较，如果没有相同的内容，添加到链表中
• 情况3：如果不为空，调用equals进行比较，如果有相同的内容，就不再添加，保证了唯一性

image.png

2、HashMap的原理

HashMap和Hashtable的区别
HashMap：作为Map的主要实现类，线程不安全，效率高，存储null的key和value
Hashtable：作为古老的实现类，线程安全，效率低，不能存null的key和value

jdk7版本

• 1、底层结构是哈希表，采用了顺序表 + 链表结合结构；同一个链表上所有元素的存储地址都是相同的，是发生冲突的元素

• 2、链表上每个结点的就是一个Entry，字段包括四部分
  hash（哈希码）key（键） value（值） next（指向下一个Entry结点）
  问：同一个链表上结点的哈希表相同吗？
  答：哈希码可能不相同，存储地址相同

• 3、（1）无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值（2）不可重复性：保证添加的元素按照equals（）判断时，不能返回true，即：相同的元素只能添加一个

• 4、put(Object key, Object value)方法
  1、计算key哈希码
  2、根据哈希码计算存储位置（主数组的索引）
  3、存入指定的位置

  • 情况1：如果是空，直接添加一个结点即可
  • 情况2：如果不为空（发生冲突），调用equals进行比较，如果没有相同的内容，添加到链表中
  • 情况3：如果不为空（发生冲突），调用equals进行比较，如果有相同的内容，就不再添加，保证了唯一性

JDK 7是头插法，JDK 8是尾插法

• 5、get(Object key)方法
  1、计算key哈希码
  2、根据哈希码计算存储位置（主数组的索引）
  3、遍历对应的链表，找到对应的结点，返回value值

• 6、重要常量
  DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16 （方便计算对应的位置 以及 方便数据迁移）
  MAXIMUM_CAPACITY：HashMap的最大支持容量，2^30
  DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75
  loadFactor：填充因子，就是默认加载因子
  threshold：扩容的临界值 = 容量 * 填充因子，元素个数超过此值就会扩容
  table：存储元素的数组，总是2的n次幂
  entrySet：存储具体元素的集
  size：HashMap中存储的键值对的个数
  TREEIFY_THRESHOLD：桶中链表长度大于该默认值8，转化为红黑树
  UNTREEIFY_THRESHOLD：桶中红黑树存储的Node小于该默认值6，转化为链表

• 7、jdk8 相较于jdk7在底层实现方面的不同：
  1、new HashMap()：底层没有创建一个长度为16的数组
  2、jdk8 底层的数组是：Node[]，而非Entry[]
  3、首次调用put()方法时，底层创建长度为16的数组
  4、jdk7底层结构只有：数组 + 链表，jdk8底层结构：数组 + 链表 + 红黑树。当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8，此时此索引位置上的所有数据改为使用红黑数存储

• 8、扩容
  当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
  　　那么HashMap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小 * loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩容为原来容量的2倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。

为什么负载因子是0.75

手写HashMap
Map接口

package com.test;

public interface Map {
    //定义方法
    public void put(Object key, Object value);
    public Object get(Object key);
    public int size();
    public boolean isEmpty();

    //定义内接接口
    interface Entry{
        public Object getKey();
        public Object getValue();
    }
}

HashMap

package com.test;

public class HashMap implements Map{
    transient Entry[] table = null;//table是指向哈希表的主数组的引用变量
    transient int size = 0;//哈希表中结点的数量

    public HashMap(){
        this(11);
    }
    public HashMap(int capacity){
        table = new Entry[capacity];
    }

    class Entry implements Map.Entry{
        final Object key;//key
        Object value;//value
        Entry next;//指向下一个结点
        int hash;//key的哈希值

        //链表中的结点结构体
        Entry(int h, Object k, Object v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Object getValue() {
            return value;
        }

        @Override
        public String toString() {
            return "Entry{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    ", hash=" + hash +
                    '}';
        }
    }

    @Override
    public void put(Object key, Object value) {
        //1、计算key哈希码
        int hash = key.hashCode();
        //2、根据哈希码计算存储位置（主数组的索引）
        int index = hash % table.length;
        //3、存入指定的位置
        //情况1：位置为空，直接加入即可
        if(table[index] == null){
            table[index] = new Entry(hash, key, value, null);
            size ++;
        }else {
            //情况2：使用新的value覆盖旧的value
            //如果指定位置不为空，发生了冲突，需要逐个比较
            Entry entry = table[index]; //指向链表的第一个结点
            while(entry != null){
                if(entry.hash == hash && (entry.key == key || entry.key.equals(key))){
                    //使用新的value覆盖相同的value
                    entry.value = value;
                    return ;
                }
                //指向下一个结点
                entry = entry.next;
            }
            //情况3：如果发生了冲突，并且没有相同的key，添加一个新的结点做链表的首结点（头插法）
            Entry firstEntry = table[index];
            table[index] = new Entry(hash, key, value, firstEntry);
            size ++;
        }
    }

    @Override
    public Object get(Object key) {
        Entry entry = getEntry(key);
        //4、返回Entry中的value
        return entry == null ? null : entry.getValue();
    }
    public Entry getEntry(Object key){
        //1、计算key哈希码
        int hash = key.hashCode();
        //2、根据哈希码计算存储位置（主数组的索引）
        int index = hash % table.length;
        //3、查找对应的Entry
        Entry entry = null;
        if(table[index] != null){
            Entry currentEntry = table[index]; //指向链表的第一个结点
            while(currentEntry != null){
                if(currentEntry.hash == hash && (currentEntry.key == key || currentEntry.key.equals(key))){
                    entry = currentEntry;
                    break;
                }
                currentEntry = currentEntry.next;
            }
        }
        return entry;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("{");
        for(int i = 0;i < table.length;i ++){
            if(table[i] != null){
                Entry entry = table[i];
                do{
                    sb.append(entry.key + "=" + entry.value + ",");
                    entry = entry.next;
                }while (entry != null);
            }
        }
        if(size > 0)sb.deleteCharAt(sb.length() - 1);
        sb.append("}");
        return sb.toString();
    }
}

3、HashSet的原理

HashSet底层就是HashMap，哈希表的每个Entry的key是每个元素，value统一都是new Object

package com.test;

public interface Set {
    public int size();
    public void add(Object obj);
    public boolean isEmpty();
    public boolean contains(Object obj);
}

package com.test;

public class HashSet implements Set{
    private HashMap map;
    private static final Object PRESENT = new Object();//都让它指定同一个对象
    public HashSet(){
        map = new HashMap();
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public void add(Object obj) {
        map.put(obj, PRESENT);
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public boolean contains(Object obj) {
        return map.getEntry(obj) != null;
    }
}

4、LinkedHashMap的原理（LInedHashMap是HashMap的子类）

保证在遍历map元素时，可以按照添加的顺序实现遍历。
原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个结构体，对于频繁的遍历操作，此类执行效率高于HashMap

其中LinkedHashSet的实现原理和LinkedHashMap的实现原理类型，LinkedHashSet是HashSet的子类，保证在遍历set元素时，可以按照添加的顺序实现遍历。

HashMap中的newNode方法 以及 内部类：Node

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

LinkedHashMap中的newNode方法 以及 内部类：Node

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    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);
        }
    }

5、TreeSet

保证按照添加的key-value对进行排序，实现排序遍历，此时考虑key的自然排序，底层使用红黑树

6、ConcurrentHashMap

image.png
image.png image.png

五、红黑树（平衡二叉搜索树）

最暴力的方法， LeetCode 1382. 将二叉搜索树变平衡

题目描述

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是平衡的 。

如果有多种构造方法，请你返回任意一种。

样例

image.png image.png

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示：

• 树节点的数目在 1 到 10^4 之间。

• 树节点的值互不相同，且在 1 到 10^5 之间。

---

算法分析

• 1、对本来的二叉搜索树通过中序遍历变成一个有序的数组
• 2、对于一个有序的数组构建一棵平衡二叉树的方法，最中间的元素当做根，左边的元素当做左子树，右边的元素当做右子树

时间复杂度

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static int N = 10010;
    static int[] val = new int[N];
    static int tt;
    static void dfs(TreeNode root)
    {
        if(root == null) return;
        dfs(root.left);
        val[++ tt] = root.val;
        dfs(root.right);
    }
    static TreeNode build(int left,int right)
    {
        if(left > right) return null;
        int mid = left + right >> 1;
        TreeNode root = new TreeNode(val[mid]);
        root.left = build(left,mid - 1);
        root.right = build(mid + 1,right);
        return root;
    }
    public TreeNode balanceBST(TreeNode root) {
        tt = 0;
        dfs(root);
        return build(1,tt);
    }
}