Collection接口

2020-12-04  本文已影响0人  得力小泡泡

三代集合类发展过程

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()

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写法
（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、存入指定的位置

image.png
2、HashMap的原理

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

jdk7版本

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

为什么负载因子是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] 也是一个可行的构造方案。

提示：

算法分析

时间复杂度O(n)

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);
    }
}
上一篇 下一篇

猜你喜欢

热点阅读