Java 集合面试笔记

// LinkedHashMap.Entry 继承 HashMap.Node，并扩展双向指针
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);
    }
}

// 哈希表的桶结构（冲突处理）
Node<K,V>[] table;  // 数组 + 链表/红黑树

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private transient volatile Object[] array;

    //写操作
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        // 写时加锁，保证复制不出问题
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            // 通过copyof方法复制
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
    //读操作，无锁机制
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
}

//在add方法中，会先使用ensureCapacityInternal()判定增加元素+1是否会超过容量
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
//判定是否超过数组容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code    if最小容量-当前数组长度>0，则启动grow方法，即扩容方法
    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);
    // 容错机制
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    // 容错机制，防止扩容超过数组最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win: 使用copyOf方法复制值到新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
// 防溢出方法，
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? //若超过，则控制下大小
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

// HashSet构造方法，本质是使用HashMap
public HashSet(){ map = new HashMap<>();}
// HashSet的add方法，v值就是PRESENT
public boolean add(E e){return map.put(e,PRESENT)==nuLl;}
//Dummy value to associate with an 0bject in the backing Map
//Dummy value 是虚值的意思，PRESENT仅仅是一个对象
private static final Object PRESENT = new Object();

HashMap 结构:
[数组] -> [链表/红黑树]

LinkedHashMap 额外结构:
head ↔ 节点1 ↔ 节点2 ↔ ... ↔ 节点N ↔ tail
//1、Entry数据结构
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);
    }
}
//2、然后内部构造函数设置 accessOrder=true，维护元素访问顺序维护
new LinkedHashMap<>(16, 0.75f, true) {
//3、重写put方法
///3.1、插入新节点后调用
void afterNodeInsertion(boolean evict) {
    // 可能移除最老的节点（用于实现固定大小的缓存）
}

// 创建新节点时调用
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 创建特殊链表节点并链接到链表尾部
}
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)  // 如果按访问顺序排序
        afterNodeAccess(e);  // 将被访问节点移到链表尾部
    return e.value;
}
    // 实现 LRU 缓存、最大容量为100的LRU缓存
Map<String, Object> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > 100;
    }
};

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // 使用自然顺序
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        System.out.println("TreeMap: " + treeMap);

        // 使用自定义比较器
        TreeMap<Integer, String> reverseTreeMap = new TreeMap<>(Comparator.reverseOrder());
        reverseTreeMap.put(3, "Three");
        reverseTreeMap.put(1, "One");
        reverseTreeMap.put(2, "Two");
        System.out.println("Reverse TreeMap: " + reverseTreeMap);

        // 获取子映射
        System.out.println("SubMap (1, 3): " + treeMap.subMap(1, 3));

        // 获取前缀映射
        System.out.println("HeadMap (2): " + treeMap.headMap(2));

        // 获取后缀映射
        System.out.println("TailMap (2): " + treeMap.tailMap(2));
    }
}

//hash算法：1、使用 System.identityHashCode() 而非对象的 hashCode()
// 2、计算出的哈希码会经过二次处理
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // 乘以一个魔数确保低位有足够的随机性
    return ((h << 1) - (h << 8)) & (length - 1);
}
//put方法，重点在使用==判断，而不是equals()
public V put(K key, V value) {
    final Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    
    // 线性探测
    while (true) {
        Object item = tab[i];
        if (item == null) {
            // 找到空槽
            modCount++;
            tab[i] = k;
            tab[i + 1] = value;
            if (++size >= threshold)
                resize(len); // 扩容
            return null;
        }
        if (item == k) {  // 引用相等判断
            V oldValue = (V) tab[i + 1];
            tab[i + 1] = value;
            return oldValue;
        }
        i = nextKeyIndex(i, len); // 下一个位置
    }
}
// 同put方法
public V get(Object key) {
    Object k = maskNull(key);
    Object[] tab = table;
    int len = tab.length;
    int i = hash(k, len);
    
    while (true) {
        Object item = tab[i];
        if (item == k)  // 引用相等判断
            return (V) tab[i + 1];
        if (item == null)
            return null;
        i = nextKeyIndex(i, len); // 线性探测
    }
}

// 以ArrayList为例
protected transient int modCount = 0;

public Iterator<E> iterator() {
    return new Itr(); // 内部类Itr会记录expectedModCount
}

private class Itr implements Iterator<E> {
    int expectedModCount = modCount;

    public E next() {
        checkForComodification(); // 检查修改
        // ...
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

// AtomicStampedReference的实现
public class AtomicStampedReference<V> {
    private static class Pair<T> {
        final T reference;
        final int stamp; // 版本号
        // ...
    }

    public boolean compareAndSet(
        V expectedReference,
        V newReference,
        int expectedStamp,
        int newStamp) {
        // 同时比较引用和版本号
    }
}