集合

List、Set、Map

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

LIst

Queue

Set

Map

HashMap

存储数据的流程

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

hashMap不安全原因

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

HashMap和Hashtable

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加锁

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

Vetor和CopyOnWriteList

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

    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

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

快速失败和安全失败

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 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和遍历转换

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