算法：列表List、映射Map、集合Set-理论

package java.util.ArrayList;
    transient Object[] elementData;             // non-private to simplify nested class access
    public ArrayList() {                        //构造函数
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    private int size;
    public boolean add(E e) {                                                    //添加方法        
        ensureCapacityInternal(size + 1);                                         //必要检查步骤，如下 下标、数组大小
        elementData[size++] = e;                                                 //实际存入数组中
        return true;        
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static int calculateCapacity(Object[] elementData, int minCapacity) {//检查数组下标
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {                  //首次返回1
            return Math.max(DEFAULT_CAPACITY, minCapacity);                      //int DEFAULT_CAPACITY=10
        }
        return minCapacity;                                                      //后续返回当前值
    }

    private void ensureExplicitCapacity(int minCapacity) {                       //检查是否需要扩容数组
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)                                //当前下标是否大于数组已有长度
            grow(minCapacity);                                                  //自动扩容
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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:
        elementData = Arrays.copyOf(elementData, newCapacity);            //拷贝数组，增加长度
    }

     package java.util.HashMap;  
     static final float DEFAULT_LOAD_FACTOR = 0.75f;                    //在构造函数中未指定时使用的加载因子

     static class Node<K,V> implements Map.Entry<K,V> {                //感觉是一个具有键值的链表
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    ......  //里面有一些方法getKey、getValue、toString、setValue
    }
     public HashMap() {                                                //构造函数
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {                               //获取Key的哈希值
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //调用key的对象哈希值，>>>为无符号右移运算符
    }

//第一个参数：Key的哈希值。第二个参数：key。第三个参数：值。
//第四：默认为true，改变key所映射的值。第五个参数：默认为false，哈希表已经创建。
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)          //transient Node<K,V>[] table;
            n = (tab = resize()).length;                                //resize()是初始化或加倍表格大小
        if ((p = tab[i = (n - 1) & hash]) == null)                 //链表数组是否为空
            tab[i] = newNode(hash, key, value, null); //创建具有保存键值的链表并保存数据进去，但是最后一个为null也就不是链表了
        else {                                                      //发生哈希冲突
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;                                             //让e非空
            else if (p instanceof TreeNode)                    //红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {                                                
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key                //e非空，更改Node对象的值
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)                                        //Node数组不够了
            resize();                                                  //扩容
        afterNodeInsertion(evict);                                     //默认true
        return null;
    }

    package java.util.HashSet;
    public HashSet() {                //构造方法
        map = new HashMap<>();        //创建一个hashMap保存元素
    }

    private static final Object PRESENT = new Object();//与后面Map中的对象值关联的虚拟值
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;              //只传递Key，不传递值
    }

    //后面map.put(e,obj)的实现，可以看前面map的详细介绍