万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

集合

List、Set、Map

集合中的最上层接口只有2类:Map和Collection,List和Set是Collection的下一层。

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

LIst

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

Queue

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

Set

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

Map

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

HashMap

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

存储数据的流程

  • 对key的hash后获得数组index;2.数组位置为空,初始化容量为16
  • 数组位置为空,初试化容量为16
  • hash后没有碰撞,就放入数组
  • 有碰撞且节点已存在,则替换掉原来的对象
  • 有碰撞且节点已经是树结构,则挂载到树上
  • 有碰撞且节点已经是链表结构,则添加到链表末尾,并判断链表是否需要转换为树结构(链表结点大于8就转换)
  • 完成put操作后,判断是否需要resize()操作

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

hashMap不安全原因

  1. 在JDK1.7中,当并发执行扩容操作时会造成环形链和数据丢失的情况。源码是1.7时的 transfer函数,自己点进去看
  2. 在JDK1.8中,在并发执行put操作时会发生数据覆盖的情况。源码是1.8时的resize函数,自己点进去看

HashMap和Hashtable

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

key,value为空的问题:

   public static void main(String[] args) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        hashmap.put(null, null);// hashmap两个都可以存null
        Hashtable<Integer, Integer> hashtable = new Hashtable<>();
        hashtable.put(null, null);//hashtable任一个都不能存null,但idea不会报错,运行会出现空指针异常
    }

HashMap的长度为什么是2的幂次方?

答:提高数组利用率,减少冲突(碰撞)的次数,提高HashMap查询效率

// 源码计算index的操作:n是table.length
 if ((p = tab[i = (n - 1) & hash]) == null)

ConcurrentHashMap

线程安全的底层原理:没有哈希冲突就大量CAS插入+如果有哈希冲突就Syn加锁

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

TreeMap

treeMap底层使用红黑树,会按照Key来排序

  • 如果是字符串,就会按照字典序来排序
  • 如果是自定义类,就要使用2种方法指定比较规则
    • 实现Compareable接口,但是需要重新定义比较规则就要修改源码,麻烦
    • 创建实例时候,传入一个比较器Comparator,重新定义规则不需要修改源码,推荐使用
public class TreeMapDemo {
    public static void main(String[] args) {
        // treeMap中自定义类需要指定比较器
        // 方式一:自定义类实现Comparable接口
        TreeMap<User, User> treeMap1 = new TreeMap<>();
        // 方式二:创建实例指定比较器Comparator
        TreeMap<User, User> treeMap2 = new TreeMap<>(new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                // 定义比较规则
                return 0;
            }
        });
    }
}
public class User implements Comparable {
    private String id;
    private String username;

    @Override
    public int compareTo(Object obj) {
        // 这里定义比较规则
        return 0;
    }
}

ArrayList和LinkedList

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

Vetor和CopyOnWriteList

list安全类是如下两个:Vetor、CopyOnWriteList; Collections.synchronizedLis是JDK包装实现线程安全的工具类

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

    public synchronized int capacity() {
        return elementData.length;
    }

	// Vetor锁都加在方法上
    public synchronized int size() {
        return elementCount;
    }

    public synchronized boolean isEmpty() {
        return elementCount == 0;
    }
    ...
    }

static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
        private static final long serialVersionUID = -7754090372962971524L;

        final List<E> list;
		// Collections.synchronizedList:内部类SynchronizedList,锁加载内部类里面
        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }
        ....
}

//  CopyOnWriteList 写加锁
public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            // CopyOnWriteList是复制数组保证线程安全
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

// CopyOnWriteList 读不加锁,原数组通过 transient volatile保证不可系列化和可见性
private transient volatile Object[] array;

final Object[] getArray() {
    return array;
} 

public E get(int index) {
    return get(getArray(), index);
}

LinkedHashMap和LinkedHashSet

答:LinkedHashMap可以记录下元素的插入顺序和访问顺序

  • LinkedHashMap内部的Entry继承于HashMap.Node,这两个类都实现了Map.Entry<K,V>
  • 底层链表是双向链表,Node不光有value,next,还有before和after属性,保证了各个元素的插入顺序
  • 通过构造方法public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder), accessOrder传入true可以实现LRU缓存算法(访问顺序)

LRU算法

最近最少使用算法: 根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。

public class LRUTest {
    // 0.指定map长度size=5
    private static final int size = 5;

    public static void main(String[] args) {
        // 1\. LinkedHashMap三大参数,重写removeEldestEntry
        Map<String, String> map = new LinkedHashMap<String, String>(size, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {

                return size() > size;
            }
        };
        // 2.添加5个数,使得map满
        map.put("1", "1");
        map.put("2", "2");
        map.put("3", "3");
        map.put("4", "4");
        map.put("5", "5");
        System.out.println("map:" + map.toString());
        // 3.指定map满了,再put就会移除表头第一个元素:1=1
        map.put("6", "6");
        System.out.println("map:" + map.toString());
        // 4.get取出的元素,表示是常用的,放回到表尾
        map.get("3");
        System.out.println("map:" + map.toString());
    }
}

执行结果:

map:{1=1, 2=2, 3=3, 4=4, 5=5}
map:{2=2, 3=3, 4=4, 5=5, 6=6}
map:{2=2, 4=4, 5=5, 6=6, 3=3}

手写LRU算法

public class LRUCache {
	// 力扣146同一题
    class DoubleNode {
        int key;
        int value;
        DoubleNode pre;
        DoubleNode next;

        DoubleNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        DoubleNode() {

        }
    }

    private HashMap<Integer, DoubleNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DoubleNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new DoubleNode();
        this.tail = new DoubleNode();
        // 创建伪头部和伪尾部,减少添加和删除的逻辑
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        // 1.获取get元素
        DoubleNode node = cache.get(key);
        // 2.get元素不存就返回-1
        if (node == null) {
            return -1;
        }
        // 3.get元素就移动至头部,规定常用元素移动至头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 1.获取put元素
        DoubleNode node = cache.get(key);
        // 2.put元素不存在
        if (node == null) {
            // 生成它
            DoubleNode nowNode = new DoubleNode(key, value);
            // 放进cache
            cache.put(key, nowNode);
            // 添加进头部
            addToHead(nowNode);
            // 长度++
            size++;
            // 判断是否超过指定长度
            if (size > capacity) {
                DoubleNode tail = removeTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            // 3.node存在就更新value,然后移动至头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DoubleNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    private DoubleNode removeTail() {
        DoubleNode del = tail.pre;
        removeNode(del);
        return del;
    }

    private void removeNode(DoubleNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(DoubleNode node) {
        removeNode(node);
        addToHead(node);
    }
}

Iterator和ListIterator

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

public class IteratorDemo {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

快速失败和安全失败

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedModCount值,是的话就返回遍历;否则抛出异常,终止遍历

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    ...
    // modCount记录当前线程更改状态    
    ++modCount;
	...
    return null;
}

数组和List和遍历转换

万字长文!阿里P7架构师整理的java集合笔记,你值得拥有!

public class ArrayAndList {
    public static void main(String[] args) {
        // 1.数组遍历:Arrays.toString
        int[] arr = {1, 2, 3};
        System.out.println(Arrays.toString(arr));
        // 2.数组转成list,泛型说明不推荐使用,多此一举
        List<int[]> ints1 = Arrays.asList(arr);
        List<int[]> ints = Collections.singletonList(arr);
        for (int[] anInt : ints) {
            System.out.println(Arrays.toString(anInt));
        }
        System.out.println("------------");
        // 3.list遍历:直接遍历即可
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(2);
        arrayList.add(3);
        System.out.println(arrayList);
        // 4.list转换成数组,list名.toArray(指定数组类型和长度)
        Integer[] integers = arrayList.toArray(new Integer[3]);
        System.out.println(Arrays.toString(integers));
    }
}

总结

感谢你看到这里,文章有什么不足还请指正,觉得文章对你有帮助的话记得给我点个赞,每天都会分享java相关技术文章或行业资讯,欢迎大家关注和转发文章!
欢迎关注公众号:前程有光,领取一线大厂Java面试题总结+各知识点学习思维导+一份300页pdf文档的Java核心知识点总结!

上一篇:多亏掌握了:多线程+Nginx+Spring全家桶+Redis+MySQL 成功升P7


下一篇:做Java开发7年,今年9个月时间圆梦饿了么P7