在java中主要有单列集合Collection和双列集合Map。接下来介绍下这两大集合的技术体系。

1. Collection（接口）

Collection是单列集合的顶层接口，定义了基本的添加、删除、查找、遍历等接口方法。

1.1 List（接口）

List表示有序的集合，用户可以通过使用索引来查找元素。接下来了解下List集合的子类或者子接口，如下：

ArrayList（类）：ArrayList是一个数组实现的集合，其继承链为List（接口）-> AbstractCollection（类）-> AbstractList（类）-> ArrayList（类）;ArrayList内部支持动态扩容、查询效率高、增删效率低。接下来介绍下ArrayList源码中动态扩容机制，默认容量10，如下所示：
```
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判断集合是否为空
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);//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);//(oldCapacity >> 1)是大于或等于0的整数（等于oldCapacity除以2的一次方） if (newCapacity - minCapacity < 0) //比较大小 newCapacity = minCapacity;//如果minCapacity大于newCapacity ，即进行赋值操作 if (newCapacity - MAX_ARRAY_SIZE > 0)//newCapacity 和MAX_ARRAY_SIZE 比较，其中MAX_ARRAY_SIZE =Integer.MAX_VALUE - 8 newCapacity = hugeCapacity(minCapacity);//如果newCapacity大于MAX_ARRAY_SIZE，就交换大小 // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity);//按新的容量大小newCapacity重新生成数组 }

- **LinkedList（类）**：LinkedList是一个双链表实现的集合，同时也是一个双端队列。LinkedList具有增删效率高、查询效率低的特性（链表结构决定）；是线程不安全的集合。（继承链：List（接口）-> AbstractCollection（类）-> AbstractList（类）-> AbstractSequentialList（类）-> LinkedList（类））

接下来介绍下LinkedList源码中链表操作的机制,如下所示：

//双链表的节点 private static class Node { E item; //存储元素本身 Node next; //下一个节点的引用 Node prev;//上一个节点的引用

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

//以添加元素add方法为例 public boolean add(E e) { linkLast(e); return true; }

void linkLast(E e) { final Node l = last; //最后一个节点 final Node newNode = new Node<>(l, e, null);//创建新节点 last = newNode; //新创建的节点赋值给全局变量last if (l == null) first = newNode; //如果最后一个节点为空，说明是第一次添加元素，把newNode当做第一个节点，赋值给全局变量first else l.next = newNode;//如果最后一个节点不为空，把newNode当做最后一个节点next变量的指针。 size++; //集合长度加1 modCount++; //修改数加1 }

- **AttributeList（类）**：AttributeList是属性列表，由于兼容性问题，JDK不推荐使用，平时开发也用的少，是ArrayList的子类。

- **RoleList（类）**：RoleList是角色列表，是用于管理角色对象相关，是ArrayList的子类。示例代码如下：

public static void test() { try { RoleList roleList = new RoleList(); List roleValues = new ArrayList<>(); roleValues.add(new ObjectName("ADD")); roleValues.add(new ObjectName("DELETE")); Role role = new Role("admin", roleValues); roleList.add(role); } catch (MalformedObjectNameException e) { e.printStackTrace(); } catch (Exception e) { e.printStackTrace(); } }

- **Vector（类）**：Vector是数组实现的集合，内部支持动态扩容、通过synchronized关键字保证线程安全；Vector具有查询效率高、增删效率低的特性。
- **Stack（类）**：Stack是一个栈模型的类，继承自Vector；提供了基本的入栈（push）、出栈（pop）、查找栈顶元素（peek）、查找元素在栈中位置（search）等方法；是一个线程安全的集合。
- **CopyOnWriteArrayList（类）**：CopyOnWriteArrayList是线程安全的ArrayList，其内部是数组实现，支持动态扩容（通过数组拷贝方式），通过独占锁ReentrantLock实现线程安全。在源码中，只要是写操作的方法都会通过Copy+ReentrantLock来实现动态扩容和线程安全，以源码中add方法为例，如下图所示：

public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock();//加锁 try { Object[] elements = getArray();//获取原始数组 int len = elements.length;//获取原始数组长度 Object[] newElements = Arrays.copyOf(elements, len + 1);//通过拷贝的方式创建新数组，新数组长度+1 newElements[len] = e;//给新数组最后一个元素赋值 setArray(newElements);//设置回全局的数组变量 return true; } finally { lock.unlock();//释放锁 } }


## 1.2 Set（接口）
**Set**表示无序的、无重复的集合。接下来了解下Set集合的子类或者子接口，如下：
- **HashSet（类）**：HashSet是一个哈希算法实现的无序集合，内部是通过HashMap实现，非线程安全的类。（继承链：Set -> AbstractSet -> HashSet）如下图所示（部分源码）：

private transient HashMap<E,Object> map; //HashSet中的HashMap全局变量map，用于HashSet的增、删、查等操作

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

说明：如果重复添加相同的元素，后面的元素会覆盖前面的元素。

- **JobStateReasons（类）**：JobStateReasons是一个保存作业状态的集合类，继承自HashSet，非线程安全类。使用示例代码如下：

    JobStateReasons jobStateReasons=new JobStateReasons();
    JobStateReason jobStateReason=JobStateReason.JOB_COMPLETED_WITH_ERRORS;
    JobStateReason jobStateReason2=JobStateReason.JOB_CANCELED_BY_USER;
    jobStateReasons.add(jobStateReason);
    jobStateReasons.add(jobStateReason2);

- **LinkedHashSet（类）**：LinkedHashSet是一个双链表加哈希表实现的有序的集合，线程不安全的类。（继承链：Set ->AbstractSet -> HashSet -> LinkedHashSet）部分源码分析如下：

//LinkedHashSet.java public LinkedHashSet() { super(16, .75f, true); }

//HashSet.java HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); //从调用来看源码中使用的是LinkedHashMap类来实现的集合操作 }

- **ConcurrentSkipListSet（类）**：ConcurrentSkipListSet是线程安全的类，内部通过ConcurrentSkipListMap来实现集合的增删查操作，是一个有序的集合，不允许添加null元素；默认是自然顺序（升序），同时可以通过实现接口Comparator进行自定义排序。（ConcurrentSkipListMap内部通过CAS保证线程安全，继承链：Set -> AbstractSet -> ConcurrentSkipListSet）
接下来简单写下示例代码，如下所示：

   //默认排序
    ConcurrentSkipListSet concurrentSkipListSet=new ConcurrentSkipListSet();
    concurrentSkipListSet.add(1);
    concurrentSkipListSet.add(13);
    concurrentSkipListSet.add(5);
    Iterator iterator= concurrentSkipListSet.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());//依次输出1,5,13
    }

//自定义排序 public class ConcurrentSkipListSetTest {

public static void test() {
    ConcurrentSkipListSet concurrentSkipListSet = new ConcurrentSkipListSet(new Person());
    concurrentSkipListSet.add(new Person(32));
    concurrentSkipListSet.add(new Person(15));
    concurrentSkipListSet.add(new Person(22));
    Iterator<Person> iterator = concurrentSkipListSet.iterator();
    while (iterator.hasNext()) {
        Person person = iterator.next();
        System.out.println(person.getAge());//依次输出32,22,15
    }
}

static final class Person implements Comparator {

    public Person() {
    }

    public Person(int age) {
        this.age = age;
    }

    private int age;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compare(Object o1, Object o2) {
        Person p1 = (Person) o1;
        Person p2 = (Person) o2;
        return p2.getAge() - p1.getAge();//降序
    }
}

}

- **CopyOnWriteArraySet(类)**：CopyOnWriteArraySet是数组实现的Set集合，准确的说是通过类CopyOnWriteArrayList来实现集合中的增删查操作；因此，CopyOnWriteArraySet是一个线程安全的集合，适合有大量查询操作和少量写操作的应用场景，因为CopyOnWriteArrayList内部写操作是通过数组拷贝和ReentrantLock控制，而读操作就不加锁。（继承链：Set -> AbstractSet -> CopyOnWriteArraySet）

- **EnumSet（类）**：EnumSet是一个用于管理枚举类型的集合，是一个抽象类；其内部定义大量的静态工厂方法来操作枚举类型元素，是一个非线程安全的抽象类。（继承链：Set -> AbstractSet -> EnumSet）
示例代码如下：

package collection.set;

import java.util.EnumSet; import java.util.Iterator;

public class EnumSetTest {

public static void test() {
    EnumSet<Color> enumSet = EnumSet.allOf(Color.class);
    Iterator<Color> iterator = enumSet.iterator();
    while (iterator.hasNext()) {
        Color color = iterator.next();
        System.out.println(color);//依次输出RED、GREEN、YELLOW
    }
}

static enum Color {
    RED, GREEN, YELLOW;
}

}

说明：所有的枚举类都是继承java.lang.Enum。

- **TreeSet（类）**：TreeSet是一个通过TreeMap来实现的一个有序的集合Set，默认是自然顺序，即升序，同时可以通过实现接口Comparator进行自定义排序。TreeSet是一个非线程安全的类。（继承链：Set -> AbstractSet -> TreeSet）
示例代码如下：

   //默认排序
    TreeSet treeSet=new TreeSet();
    treeSet.add(1);
    treeSet.add(21);
    treeSet.add(15);
    Iterator iterator= treeSet.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());//依次输出1,15,21
    }

//通过实现接口Comparator自定义排序 package collection.set;

import java.util.Comparator; import java.util.Iterator; import java.util.TreeSet;

public class TreeSetTest { public static void test() { TreeSet treeSet = new TreeSet(new Person()); treeSet.add(new Person(12)); treeSet.add(new Person(20)); treeSet.add(new Person(50)); Iterator iterator = treeSet.iterator(); while (iterator.hasNext()) { Person person = iterator.next(); System.out.println(person.getAge());//依次输出50、20、12 } }

static final class Person implements Comparator {

    public Person() {
    }

    public Person(int age) {
        this.age = age;
    }

    private int age;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compare(Object o1, Object o2) {
        Person p1 = (Person) o1;
        Person p2 = (Person) o2;
        return p2.getAge() - p1.getAge();//降序
    }
}

}

# 2. Map（接口）
Map是一个双列集合，保存键值对类型的元素，键是不容许有重复的值。接下来了解其子接口和子类，如下所示：
- **HashMap（类）：** HashMap是一个通过哈希表实现的集合（数组方式实现），通过键值对的形式来存取数据，键和值都允许传null；HashMap是非线程安全的类。接下来分析HashMap源码是怎样工作的，如下：

**哈希表中用于存储数据的实体Node解析**

transient Node<K,V>[] table; //全局表对象 static class Node<K,V> implements Map.Entry<K,V> { final int hash; //哈希值 final K key; //键 V value; //值 Node<K,V> next; //下一个节点引用

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

** HashMap中put方法解析**

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

//根据key生成hash值 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

//根据hash、key、value进行的实质的写操作 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) //判断table是否为空 n = (tab = resize()).length; //初始化table或者调整table大小 if ((p = tab[i = (n - 1) & hash]) == null) //根据索引判断数组中元素是否为null tab[i] = newNode(hash, key, value, null); //创建表节点，并给table中的元素赋值 else { //这个分支处理hash值重复问题 Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; 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 V oldValue = e.value; //获取旧的值 if (!onlyIfAbsent || oldValue == null) //判断是否为覆盖模式，由onlyIfAbsent控制 e.value = value; //将新的值覆盖旧的值 afterNodeAccess(e); return oldValue; } } ++modCount; //记录修改记录 if (++size > threshold) //判断表大小是否超过阀值，threshold是一个阀值 resize(); //调整表大小 afterNodeInsertion(evict); return null; }

**HashMap中get方法解析**

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value; //这里hash(key)和以上put中使用的是同一个哈希函数（散列函数）
    }

    //根据根据哈希值hash和键key获取表中的元素
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {//根据(n - 1) & hash获取表中元素，使用的规则和put写入的规则保持一致
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first; //如果满足条件，则返回表中查找到的元素
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
**HashMap中哈希表存储模型**
![image](https://user-images.githubusercontent.com/17380142/74604670-24a49280-50fb-11ea-8369-8d1e43eadf1a.png)

- **LinkedHashMap（类）：** LinkedHashMap是一个由哈希表和双链表实现的Map集合，具有迭代的有序性，允许键和值传null；它是一个非线程安全的类。（继承链：HashMap -> LinkedHashMap）

接下来分析下LinkedHashMap的内部机制，如下：

**LinkedHashMap源码中的存储数据实体**

static class Entry<K,V> extends HashMap.Node<K,V> { //继承HashMap.Node Entry<K,V> before, after; //双链表结构每个元素保存上一个和下一个元素的引用 Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

**LinkedHashMap中添加元素put方法解析**

//这个方法是HashMap中的方法 public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

//这个方法是HashMap中的方法 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) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);//newNode()是调用LinkedHashMap中的方法 else { Node<K,V> e; K k; ........省略部分代码 }

//LinkedHashMap中重写父类HashMap中的方法 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; }

//添加节点到链表最后 private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; //tail表示链表尾巴节点 tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }

**LinkedHashMap中查找元素get方法解析**

public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) //这里调用父类HashMap中的getNode方法 return null; if (accessOrder) //accessOrder表示访问顺序，true表示集合按访问的顺序迭代，true表示按元素添加的顺序迭代 afterNodeAccess(e); return e.value; }


**LinkedHashMap中accessOrder机制解析**

//LinkedHashMap构造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {//accessOrder表示访问顺序，true表示集合按访问的顺序迭代，true表示按元素添加的顺序迭代 super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }

//将访问的元素移到链表最后 void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last;//最后的元素 if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //p表示当前操作的元素，b表示p的前一个元素节点，a表示p的后一个元素节点 p.after = null; //移到链表最后，after指针置为null if (b == null) head = a; //表示当前访问的元素是第一个元素，交换指针，把a变成链表第一个元素 else b.after = a;//不是第一个元素，交换位置 if (a != null) a.before = b;//不是最后一个元素，交换位置 else last = b;//这个分支不会执行 if (last == null) head = p;//当前元素就是第一个元素 else { p.before = last; //和最后一个元素交换位置 last.after = p; } tail = p; //当前元素变成链表最后 ++modCount; //修改记录数+1 }

**说明：将accessOrder设置为true，便可以实现类似LRU caches的业务场景。越后面访问过的元素就越在链表的后面，最后访问的元素，会出现在链表的末尾。**

**LinkedHashMap中双链表结构**
![image](https://user-images.githubusercontent.com/17380142/74658293-eaa3c100-51cc-11ea-8685-ef7826359df4.png)

- **PrinterStateReasons（类）：** PrinterStateReasons是一个管理打印状态的Map集合，是一个非线程安全的类，继承自HashMap，日常工作中也很少使用。
示例代码：

    PrinterStateReasons printerStateReasons = new PrinterStateReasons();
    printerStateReasons.put(PrinterStateReason.MEDIA_NEEDED, Severity.ERROR);
    printerStateReasons.put(PrinterStateReason.MEDIA_JAM, Severity.REPORT);
    printerStateReasons.put(PrinterStateReason.MOVING_TO_PAUSED, Severity.WARNING);

- **EnumMap（类）：** EnumMap是一个专门管理键（key）是枚举类型的Map，不允许键为null，允许值（value）为空；内部通过数组实现，是一个线程不安全的类；迭代器输出的顺序由枚举常量的先后顺序决定。（继承链：Map -> AbstractMap -> EnumMap）

**构造方法解析**

public EnumMap(Class keyType) { this.keyType = keyType; //keyType是枚举类型，K extends Enum keyUniverse = getKeyUniverse(keyType);//获取枚举类 vals = new Object[keyUniverse.length]; //根据枚举类的元素个数创建数组 }

**添加元素put方法解析**

public V put(K key, V value) { typeCheck(key); //检查key类型是否为枚举类型

    int index = key.ordinal(); //获取key的序列
    Object oldValue = vals[index];//根据索引index获取数组中元素
    vals[index] = maskNull(value); //赋值
    if (oldValue == null) 
        size++; //如果oldValue==null，表示之前该索引位置没有添加过元素
    return unmaskNull(oldValue); //如果oldValue不为空返回旧元素
}

private void typeCheck(K key) { Class<?> keyClass = key.getClass(); if (keyClass != keyType && keyClass.getSuperclass() != keyType) throw new ClassCastException(keyClass + " != " + keyType); }

private V unmaskNull(Object value) { return (V)(value == NULL ? null : value); }


**获取元素get方法解析**

public V get(Object key) { return (isValidKey(key) ? unmaskNull(vals[((Enum<?>)key).ordinal()]) : null); //先判断key的合法性，再根据数组索引取值 }

private boolean isValidKey(Object key) { if (key == null) return false;

    // Cheaper than instanceof Enum followed by getDeclaringClass
    Class<?> keyClass = key.getClass();
    return keyClass == keyType || keyClass.getSuperclass() == keyType;
}

private V unmaskNull(Object value) { return (V)(value == NULL ? null : value); }

**使用示例代码**

 public static void test() {
    EnumMap enumMap = new EnumMap(Color.class);
    enumMap.put(Color.BLUE, "blue");
    enumMap.put(Color.RED, "red");

    Set<Map.Entry> set = enumMap.entrySet();
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        Map.Entry entry=(Map.Entry) iterator.next();
        System.out.println(entry.getKey()+" "+entry.getValue());
        /** 依次输出（按枚举类Color中元素的顺序输出，并不是按put的顺序）
         * RED red
         * BLUE blue
         */
    }

}

enum Color {
    RED, GREEN, BLUE
}


- **ConcurrentHashMap（类）：** ConcurrentHashMap是通过哈希表实现的线程安全的Map集合，键（key）和值(value)不允许为null。（继承链：Map -> AbstractMap -> ConcurrentHashMap）

**ConcurrentHashMap中put方法解析**

public V put(K key, V value) { return putVal(key, value, false); }

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); //计算key的哈希值 int binCount = 0; for (Node<K,V>[] tab = table;;) {//table存储数据的表 Node<K,V> f; int n, i, fh; if (tab == null || (n = tab.length) == 0) tab = initTable();//初始化表 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //获取指定偏移量对象的引用 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))//添加新元素 break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { //处理键相同的问题，即重复给相同key赋值 V oldVal = null; synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }

//取值 static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); } //写入 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); }

//存取的偏移量都是 ((long)i << ASHIFT) + ABASE，这个偏移量用于从内存中取值。

**ConcurrentHashMap中get方法解析**

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); //计算key对应的哈希值 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //根据相同的偏移量调用tabAt方法取值 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }

- **ConcurrentSkipListMap（类）：** ConcurrentSkipListMap是一个支持排序的Map集合，默认按键（key）升序，支持自定义排序，不允许空键和空值；内部通过CAS机制实现线程安全。（继承链：Map -> AbstractMap -> ConcurrentSkipListMap）
**示例代码（升序）**

ConcurrentSkipListMap concurrentSkipListMap = new ConcurrentSkipListMap(); concurrentSkipListMap.put(2, "gg"); concurrentSkipListMap.put(3, "55"); concurrentSkipListMap.put(1, 1);

    Iterator iterator = concurrentSkipListMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry entry = (Map.Entry) iterator.next();
        System.out.println(entry.getKey() + " " + entry.getValue());
        /**依次输出，按key进行排序
         1 1
         2 gg
         3 55
         */
    }


**自定义排序**

public static void test() { ConcurrentSkipListMap concurrentSkipListMap = new ConcurrentSkipListMap(new Person()); concurrentSkipListMap.put(new Person(12), "gg"); concurrentSkipListMap.put(new Person(33), "55"); concurrentSkipListMap.put(new Person(1), 1);

    Iterator iterator = concurrentSkipListMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry entry = (Map.Entry) iterator.next();
        Person person=(Person) entry.getKey();
        System.out.println(person.getAge()+"  "+entry.getValue());
       /**依次输出，按Person中的排序规则进行排序
         33  55
         12  gg
         1  1
         */
    }

}

static final class Person implements Comparator {
    public Person() {
    }

    public Person(int age) {
        this.age = age;
    }

    private int age;

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public int compare(Object o1, Object o2) {
        Person p1 = (Person) o1;
        Person p2 = (Person) o2;
        return p2.getAge() - p1.getAge();//降序
    }
}

**put方法解析**

public V put(K key, V value) { if (value == null) throw new NullPointerException(); return doPut(key, value, false); }

private V doPut(K key, V value, boolean onlyIfAbsent) { ...省略 z = new Node<K,V>(key, value, n); if (!b.casNext(n, z)) //写入 break; // restart if lost race to append to b break outer; ...省略 }

**get方法解析**

public V get(Object key) { return doGet(key); }

private V doGet(Object key) { if (key == null) throw new NullPointerException(); Comparator<? super K> cmp = comparator; outer: for (;;) { for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) { //取值 Object v; int c; if (n == null) break outer; Node<K,V> f = n.next; if (n != b.next) // inconsistent read break; if ((v = n.value) == null) { // n is deleted n.helpDelete(b, f); break; } if (b.value == null || v == n) // b is deleted break; if ((c = cpr(cmp, key, n.key)) == 0) { @SuppressWarnings("unchecked") V vv = (V)v; //赋值 return vv; } if (c < 0) break outer; b = n; n = f; } } return null; }

- **IdentityHashMap（类）：** IdentityHashMap是一个用于身份识别的Map集合，内部是哈希表实现的数据存储，是一个非线程安全类；支持键（key）和值(value)传null，内部是通过内存地址的比较来判断键key是否相同。

**IdentityHashMap中put方法分析**

public V put(K key, V value) { final Object k = maskNull(key);//处理null的情况，如果key为null，创建一个Object对象

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        int i = hash(k, len); //根据key和表的长度计算哈希值

        for (Object item; (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) { //根据计算出来的哈希值i作为索引去表tab中查找元素
            if (item == k) {//如果根据哈希值i在表中找到了元素，则通过**内存地址**的比较，元素是否是本身
                @SuppressWarnings("unchecked")
                    V oldValue = (V) tab[i + 1]; //获取旧值
                tab[i + 1] = value; //重新赋值
                return oldValue; //返回旧的值
            }
        }

        final int s = size + 1; //大小+1
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        if (s + (s << 1) > len && resize(len))  //判断是否需要调整大小
            continue retryAfterResize;

        modCount++;  //操作记录+1
        tab[i] = k; //存储键到表中
        tab[i + 1] = value; 存储值到表中
        size = s; //集合大小赋值到全局变量size
        return null;
    }
}

//哈希函数 private static int hash(Object x, int length) { int h = System.identityHashCode(x);//这个方法是原生方法，返回对象的hashCode，而不管对象是否重写了hashCode方法。（物理内存地址产生的哈希值） // Multiply by -127, and left-shift to use least bit as part of hash return ((h << 1) - (h << 8)) & (length - 1); }

**IdentityHashMap中get方法分析**

public V get(Object key) { Object k = maskNull(key);//处理null情况 Object[] tab = table; int len = tab.length; int i = hash(k, len); //根据哈希函数获取哈希值，和put方法调用的哈希函数一致 while (true) { Object item = tab[i]; //根据哈希值i获取表中元素(该位置存的是键) if (item == k) //内存地址比较 return (V) tab[i + 1]; //如果相等则从表中取出元素并返回 if (item == null) //未找到元素 return null; i = nextKeyIndex(i, len); //处理哈希冲突问题 } }

**关于Object.hashCode()和System.identityHashCode()的解析**
hashCode是取决于子类重写的父类hashCode方法里面实现的逻辑；而identityHashCode是内存地址的哈希值比较。看个简单的例子：

    Integer key1=new Integer(22);
    Integer key2=new Integer(22);
    System.out.println(System.identityHashCode(key1)); //输出：21685669
    System.out.println(System.identityHashCode(key2)); //输出：2133927002
    System.out.println(key1.hashCode());//输出：22
    System.out.println(key2.hashCode());//输出：22

 //Integer中hashCode函数
@Override
public int hashCode() {
    return Integer.hashCode(value);
}

public static int hashCode(int value) {
    return value;
}

**说明：从输出结果来看，hashCode取决于类本身重写的父类hashCode方法的逻辑；而identityHashCode取决于虚拟机实际分配的物理内存地址，因此，不同的对象，identityHashCode值不同。**

- **TreeMap（类）：** TreeMap是一个二叉树实现的有序的Map集合，默认是根据键的自然顺序排序（即升序），同时支持自定义排序，不允许键为null，允许值为null。TreeMap是一个非线程安全的类。（继承链：Map -> AbstractMap ->TreeMap）

**红黑树的分析（以默认升序为例）**
![image](https://user-images.githubusercontent.com/17380142/75090043-db8c8c80-5599-11ea-85ea-e0fdf60dc40e.png)
红黑树的特征：
1. 每个节点都会做一个标识，不是红色就是黑色。
2. 根节点永远是黑色。
3. 针对直属父子节点的颜色不一致，如果父节点是黑色，则子节点一定是红色；反之，如果父节点是红色，则子节点一定是黑色。
4. 左子树的值小于父节点，右子树的值大于父节点。

**树节点类分析**

static final class Entry<K,V> implements Map.Entry<K,V> { K key; //键 V value; //值 Entry<K,V> left; //左子树 Entry<K,V> right; //右子树 Entry<K,V> parent; //父节点 boolean color = BLACK; //颜色标识 //省略其他代码 }

**TreeMap中put方法分析**

public V put(K key, V value) { Entry<K,V> t = root; //根节点 if (t == null) { //第一个添加元素 compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null); //创建根节点
        size = 1;//集合大小设为1
        modCount++; //操作记录自增
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator; //获取自定义比较器对象
    if (cpr != null) { //使用自定义比较器，比较逻辑和下面分支一致，将在下面介绍
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key; //使用默认比较器Comparable
        do {
            parent = t; //赋值父节点变量
            cmp = k.compareTo(t.key); //比较key大小
            if (cmp < 0) //表示k<t.key
                t = t.left;
            else if (cmp > 0) //表示k>t.key
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null); //遍历整棵树比较大小
    }
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) //表示当前节点小于父节点
        parent.left = e; //给父节点添加左子树
    else
        parent.right = e; //给父节点添加右子树
    fixAfterInsertion(e); //修改节点插入的位置
    size++; //大小+1
    modCount++; //修改记录+1
    return null;
}

//修改节点插入的位置 private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; //BLACK表示true，RED表示false；这里给节点设置初始值

    while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //比较x父亲节点是否等于x爷爷节点的左子树，处理树整体偏左的情形，比如依次添加key为3，1，2的情况
            Entry<K,V> y = rightOf(parentOf(parentOf(x))); //获取x爷爷的右子树
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {//如果x节点大于父节点情况
                    x = parentOf(x); //获取父节点
                    rotateLeft(x); //传入父节点
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else { //处理树整体偏右的情形
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    root.color = BLACK; //根节点永远是黑色
}

//向左偏转
 private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
        Entry<K,V> r = p.right; //获取右子树
        p.right = r.left; //交换位置
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent; //交换位置
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r; //p的右子树r和p交换位置
        else
            p.parent.right = r;
        r.left = p; //交换位置，p变为r的左子树
        p.parent = r;
    }
}

//向右偏转（处理思路和rotateLeft方法类似） private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } }

**以1，2，3作为key添加为例，不同的顺序有不同的处理逻辑，如下：**
![image](https://user-images.githubusercontent.com/17380142/75095726-fdeecc00-55d2-11ea-9737-563a994aeb29.png)

**TreeMap中get方法分析**

public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }

final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; //获取树根节点 while (p != null) { //通过大小比较，不断遍历树 int cmp = k.compareTo(p.key); //比较大小 if (cmp < 0) //k<p.key p = p.left; //继续比较左子树 else if (cmp > 0) //k>p.key p = p.right;//继续比较右子树 else return p; //找到节点返回 } return null; }

**TreeMap中remove方法分析**

public V remove(Object key) { Entry<K,V> p = getEntry(key); //查找树节点，和get方法一致的逻辑 if (p == null) return null;

    V oldValue = p.value; //获取元素的值
    deleteEntry(p);
    return oldValue; //返回被移除元素的值
}

//删除节点并重新调整树节点 private void deleteEntry(Entry<K,V> p) { modCount++;//修改记录+1 size--;//集合大小-1

    // If strictly internal, copy successor's element to p and then make p
    // point to successor.
    if (p.left != null && p.right != null) {//当前节点存在左子树和右子树的情况
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } // p has 2 children

    // Start fixup at replacement node, if it exists.
    Entry<K,V> replacement = (p.left != null ? p.left : p.right); //查找替换节点，p的左子树或者右子树

    if (replacement != null) {
        // Link replacement to parent
        replacement.parent = p.parent; //交换父亲
        if (p.parent == null) //p为根节点情形
            root = replacement;
        else if (p == p.parent.left)//当前节点向左倾斜，即当前节点是其父亲的左子树
            p.parent.left  = replacement; //交换位置
        else//当前节点向右倾斜，即当前节点是其父亲的右子树
            p.parent.right = replacement; //交换位置

        // Null out links so they are OK to use by fixAfterDeletion.
        p.left = p.right = p.parent = null; //置空节点元素

        // Fix replacement
        if (p.color == BLACK)
            fixAfterDeletion(replacement); //调整树节点颜色
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink. //没有子节点情形
        if (p.color == BLACK) //判断节点颜色
            fixAfterDeletion(p);

        if (p.parent != null) {
            if (p == p.parent.left) //当前节点向左倾斜，即当前节点是其父亲的左子树
                p.parent.left = null;//直接置空删除
            else if (p == p.parent.right) //当前节点向右倾斜，即当前节点是其父亲的右子树
                p.parent.right = null; //直接置空删除
            p.parent = null; //直接置空
        }
    }
}

- **WeakHashMap（类）：** WeakHashMap是一个弱引用实现的Map集合，允许键和值传入空值null，WeakHashMap实现方式和HashMap类似；WeakHashMap是一个非线程安全类，非常适合实现一些内存缓存的场景。（继承链：Map -> AbstractMap -> WeakHashMap）

**看一段弱引用的实例**

    WeakHashMap weakHashMap = new WeakHashMap();
    Integer key=new Integer(1);
    Integer key2=new Integer(2);
    weakHashMap.put(key, 22);
    weakHashMap.put(key2,222);
    key=null;
    System.gc();//手动模拟GC
    Iterator  iterator =weakHashMap.entrySet().iterator();
    while (iterator.hasNext()){
        Map.Entry entry=(Map.Entry) iterator.next();
        System.out.println(entry.getKey()+" "+entry.getValue()); //只输出222一个元素，因为key对象不存在被引用的情况
    }

说明：从输出的结果来看因为key是弱引用，当key不存在引用链时，WeakHashMap中的条目将自动从映射中删除。换句话说，就是垃圾回收。

**WeakHashMap中数据存储实体**

private static class Entry<K,V> extends WeakReference

zgq105 / blog

数据结构--集合 #85

1. Collection（接口）

1.1 List（接口）