集合

集合继承图

Collection

继承图

常用方法

1. add:添加元素
2. remove:删除指定元素，或指定下标。重载；
3. contains：查找指定元素是否存在
4. size：获取元素的个数
5. isEmpty:判断集合是否为空；
6. clear：清空
7. addAll：添加多个元素；
8. containsAll：查找多个元素是否同时存在；
9. removeAll：删除多个元素；

注意：remove方法的重载；

// List 中有一个重载方法。remove()

public static void main(String[] args) {
    List list = new ArrayList();
    list.add(1);
    list.add(2);
    list.add(3);
    // 删除的是元素2；
    Object remove = list.remove(new Integer(2));
    // 删除的是下标2的元素。
    Object o = list.remove(2);
    System.out.println(remove);
    System.out.println(o);
}

List 集合

List可以存重复元素，包括null，并且是有序的【保证插入顺序】；

get(index)是List集合特有的方法。

遍历List集合的方法

【ArrayList，LinkedList，Vector】

• for-i循环
• 普通迭代器
• 增强for(底层迭代器)
• 双向迭代器
• list-forEach方法
• list的stream流-forEach

public static void main(String[] args) {
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    //		Object remove = list.remove(new Integer(2));
    //		Object o = list.remove(1);
    //		System.out.println(remove);
    //		System.out.println(o);
    System.out.println("===for迭代===");
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }
    System.out.println("===普通迭代器===");
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()){
        System.out.println(iterator.next());
    }
    System.out.println("===增强for===");
    // 增强for循环
    for (Integer integer : list) {
        System.out.println(integer);
    }
    System.out.println("===双向迭代器===");
    // 双向迭代器
    ListIterator<Integer> listIterator = list.listIterator();
    while (listIterator.hasNext()){
        System.out.println(listIterator.next());
    }
    //反向迭代
    System.out.println("====反向迭代===");
    while (listIterator.hasPrevious()){
        System.out.println(listIterator.previous());
    }
    //调用foreach
    System.out.println("====list.foreach()===");
    list.forEach(System.out::println);
    //stream流
    System.out.println("====stream流===");
    list.stream().forEach(System.out::println);
}

随机访问

ArrayList支持随机访问【RandomAccess】。

public class Ar	rayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

LinkedList不支持随机访问；

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

ArrayList 和LinkedList的访问速度比较；

public void test2() {
    List<Integer> arrayList = new ArrayList<>();
    for (int i = 0; i < 100000; i++) {
        arrayList.add(i);
    }

    List<Integer> linkedList = new LinkedList<>();
    for (int i = 0; i < 100000; i++) {
        linkedList.add(i);
    }
    // 使用普通for循环
    long start1 = System.currentTimeMillis();
    for (int i = 0; i < arrayList.size(); i++) {
        arrayList.get(i);
    }
    long end1 = System.currentTimeMillis();
    System.out.println("普通for循环遍历ArrayList:" + (end1 - start1)); 

    long start2 = System.currentTimeMillis();
    for (int i = 0; i < linkedList.size(); i++) {
        linkedList.get(i);
    }
    long end2 = System.currentTimeMillis();
    System.out.println("普通for循环遍历LinkedList:" + (end2 - start2));

    for (Integer integer : arrayList) {}
    System.out.println("迭代器遍历ArrayList:" + (end1 - start1));
    for (Integer integer : linkedList) {}
    System.out.println("迭代器遍历LinkedList:" + (end1 - start1));
}
// 遍历速度
普通for循环遍历ArrayList:3
普通for循环遍历LinkedList:4599
迭代器遍历ArrayList:3
迭代器遍历LinkedList:3

注意事项

• ArrayList允许存储所有元素，包括null元素，并且可以是多个null; 底层使用数组实现。
• ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高）。在多线程情况下，不建议使用ArrayList。

// ArrayList
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// Vector
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

ArrayList

• 0 -> 10 -> 15 -> 21 (默认扩容大小，未指定初始化容量的构造器)
• 8 -> 12 -> 18 -> 27 (默认指定初始化大小，即指定初始化容量的构造函数。)

ArrayList扩容：

• ArrayList中维护了一个Object类型的数组elementData。
  • 小点：transient 表示瞬间，短暂的，表示该属性不会被序列化。

transient Object[] elementData;

• 当创建ArrayList对象时，如果使用的是无参构造器，则初始化elementData的容量为0，第一次添加，则扩容为10，如需要再次扩容，则扩容到原来的1.5倍。newCap = oldCap + oldCap>>1;

• 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容到elementData的1.5倍。

指定初始容量的构造方法。

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        /**创建一个指定容量的数组*/
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

扩容方法：

add -> ensureCapacityInternal -> ensureExplicitCapacity -> grow

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

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

我们用IDEA来看看扩容过程：

如果我们想要在IDEA中看到elementData数组，需要修改一下IDEA的设置。

如图设置之后，我们就可以进行DEBUG。

上图是添加2个元素时，下面我们看添加了第11个元素时。

由此可见，是按照1.5倍进行扩容处理的。

当我们使用指定初始化大小的构造器创建集合时，会按照指定大小的1.5倍来扩容。

指定初始化容量为8，第一次扩容为8+8>>1 == 12;

Vector

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

初始化容量为10，如果在构造器指定了扩容参数，则按照指定扩容参数来扩容。如果没有，则使用2倍容量进行扩容。

// 指定初始化容量，以及扩容参数
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    /**如果指定了初始化大小，则按指定初始化大小创建数组*/
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
// 无参和一个参数
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

public Vector() {
    this(10);
}

添加元素及扩容过程

/**使用了同步机制，synchronized，保证了线程安全，但是效率低*/
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    /**判断需要的最小容量是否大于数组的长度，如果大于，则不扩容，否则，则指定grow扩容*/
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

 private void grow(int minCapacity) {
     // overflow-conscious code
     int oldCapacity = elementData.length;
     /**判断容量参数，是否大于0，不指定时，默认为0，如果是0，则使用原容量扩容，否则就使用
		 * 自定义扩容参数扩容。*/
     int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                      capacityIncrement : oldCapacity);
     if (newCapacity - minCapacity < 0)
         newCapacity = minCapacity;
     if (newCapacity - MAX_ARRAY_SIZE > 0)
         /**判断是否超过最大容量*/
         newCapacity = hugeCapacity(minCapacity);
     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;
}

LinkedList

学习链表，可以看看LinkedList的源码。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

• LinkedList底层实现了双向链表和双端队列特点。
• 可以添加任何元素（元素可以重复），包括null。
• 线程不安全，没有实现同步。

设置LinkedList第N个位置上的值，即修改元素值。

通过下列修改元素的源码，也可以看出两点

• 在查找元素的时候，由于LinkedList不支持随机访问，所以需要顺序或倒序查找，但是由于

  LinkedList是双向链表，所以这里进行了二分判断优化。

• LinkedList底层是双向链表。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}
// 第一步，检查下标是否合法
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 第二步，查找指定位置上的节点
/**在查找链表时，使用了一个二分判断，
* 即，如果下标在中间位置前，则使用，顺序查找。
* 如果下边在中间位置后，则使用，倒序查找。
* 由于LinkedList底层是双向链表。所以可以顺序和倒序遍历。
* */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

自己实现一个ArrayList和LinkedList；

Set

基本介绍

• 无序，即添加和取出的顺序【取出顺序会固定，不会一直变】不一致，没有索引，即不能通过下标访问。
• 不允许重复元素，可以存储null，所以最多包含一个null。

Set接口的遍历方式

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口。

• 可以使用迭代器
• 增强for
• 不能使用索引的方式获取。即【get(index)】，普通for循环遍历不了。

HashSet

https://blog.csdn.net/cooltripmaker/article/details/28131001 hashcode生成规则

1. HashSet 实现了Set接口。
2. HashSet底层使用了HashMap；
3. 可以存放null值，但是只能有一个null。
4. HashSet不保证元素是有序的，取决于hash后，再确定索引的结果。
5. 不能有重复元素/对象。

1. HashSet的底层是HashMap
2. 添加一个元素时，先得到hash值，会转成->索引值
3. 找到存储数据表的table，看这个索引位置是否已经存放有元素
4. 如果没有，则直接加入
5. 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则添加到最后
6. 在Java8中，如果一条链表的元素个数超过8，并且table的大小>=64就会进行树化。（红黑树）

private static final Object PRESENT = new Object();

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


// HashMap的hash值计算方法（hash值并不简单的就是hashcode值）
static final int hash(Object key) {
    int h;
    /**可以看到，当key为null时，默认返回0.则表示null会存放在下标为0的地方
        	可以看到这里使用hash值然后跟自身向右移动16的数进行异或运算，让hash值更加散列。
		 */
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 添加元素的实际方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /**table是HashMap的一个数组属性，Node[]*/
    if ((tab = table) == null || (n = tab.length) == 0)
        //resize 扩容 [无参，第一次put，初始化为16]
        n = (tab = resize()).length;
    //判断当前key应该存放在哪一个桶中，使用与运算来实现取模运算*/
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果数组上的节点为null，则表示当前桶位没有存放数据，直接创建一个节点，放置在tab的第i个位置上。
        tab[i] = newNode(hash, key, value, null);
    else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
        Node<K,V> e; K k;
        //p就是冲突的第一个位置[链表的第一个元素]。hash值相同，key相同，或者equals。表示key相同。
        //注意：相同的hash可能对应不同的key
        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 {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
                    p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
                    if (binCount >= TREEIFY_THRESHOLD - 1) //  TREEIFY_THRESHOLD - 1 = 7 如果
                        //当链表添加第9个时，就会触发树型化操作，即将链表转为红黑树。
                        // 那这里其实可以知道，链表存在的最长的串就是8个。
                        // 8个节点是一个临界值。（树化的另一个条件是，table的容量要大于等于64.否则进行数组扩容）
                        treeifyBin(tab, hash);
                    break;
                }
                //如果存在一样的key，则跳过，表示当前待插入元素和链表的某一个节点重复。所以加入，并跳出循环，不再比较
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//相当于p=p.next
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
            //如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//值覆盖
            afterNodeAccess(e);
            return oldValue;//返回oldValue
        }
    }
    ++modCount;//并发操作，fast-fail
    if (++size > threshold)//size+1
        resize();
    afterNodeInsertion(evict);
    return null;
}

注意：下面有一个值替换的过程，如果onlyIfAbsent为true，则不会进行值替换。

参考HashMap的putIfAbsent方法。

if (!onlyIfAbsent || oldValue == null)
    e.value = value;//值覆盖

1. HashSet 底层是HashMap，第一次添加时，table数据扩容到16，临界值（threshold）是16*加载因子（loadFactor)0.75=12

   https://www.zhihu.com/question/276736347?sort=created

2. 如果table数据使用到了临界值12，就会扩容到16*2=32，新的临界值就是32 * 0.75 = 24； 以此类推；

3. 在Java8中，如果一条链表的元素个数超过8，并且table的大小>=64就会进行树化。（红黑树）

https://www.zhihu.com/question/276736347?sort=created

public static void test1(){
    HashSet hashSet = new HashSet();
    for (int i = 0; i < 9; i++) {//加入第八个时，并不会触发扩容。
        hashSet.add(new A(i));
    }
    System.out.println(hashSet);
}


class A{
	private int num;

	public A(int num) {
		this.num = num;
	}

	@Override
	public int hashCode() {
		return 100;
	}
}

LinkedHashSet

• LinkedHashSet是HashSet的子类，
• LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表。
• LinkedHashSet根据元素的hashcode值来决定元素的存储位置，同样是用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
• LinkedHashSet不允许添加重复元素。

LinkedHashMap的底层数据结构。

https://blog.csdn.net/liuyueyi25/article/details/78511278

TreeSet

TreeSet底层使用了TreeMap。会把Comparator传递给TreeMap。

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;
        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;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                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++;
    modCount++;
    return null;
}

Map

• Map与Collection并列存在。用于保存具有映射关系的数据：key-value

• Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中。

• Map中的key不允许重复，原因和HashSet一样。

• Map的value可以重复。

• Map的key可以为null，value也可为null，注意key为null，只能有一个，value为null，可以有多个。

• 常用String类作为Map的key

• key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value。

继承图

HashMap的put方法；存在值替换和不替换

Map<String,Integer> map1 = new HashMap<>();
map1.put("aa",12);
map1.put("aa",14);
System.out.println(map1);
// {aa=14}

Map<String,Integer> map2 = new HashMap<>();
map2.putIfAbsent("aa",12);
map2.putIfAbsent("aa",14);
System.out.println(map2);
// {aa=12}

HashMap底层是单向链表

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

EntrySet后续可以研究。

遍历Map的几种方式

public static void test2() {
    Map<String, String> map = new HashMap<>();
    map.put("邓超", "孙俪");
    map.put("王宝强", "马蓉");
    map.put("宋喆", "马蓉");
    map.put("刘令博", null);
    map.put(null, "刘亦菲");
    map.put("鹿晗", "关晓彤");

    System.out.println("===遍历方式1.keySet-增强for===");
    for (String key : map.keySet()) {
        System.out.println(key + "-" + map.get(key));
    }
    System.out.println("===遍历方式2.keySet-iterator===");
    Iterator<String> iterator = map.keySet().iterator();
    while (iterator.hasNext()) {
        String next = iterator.next();
        System.out.println(next + "-" + map.get(next));
    }

    System.out.println("===遍历方式3.values-增强for===");
    for (String value : map.values()) {
        System.out.println(value);
    }
    System.out.println("===遍历方式4.values-iterator===");
    Iterator<String> valIte = map.values().iterator();
    while (valIte.hasNext()) {
        System.out.println(valIte.next());
    }

    System.out.println("===遍历方式5.entrySet-增强for===");
    for (Map.Entry<String, String> entry : map.entrySet()) {
        System.out.println(entry.getKey() + "-" + entry.getValue());
    }
    System.out.println("===遍历方式6.entrySet-iterator===");
    Iterator<Map.Entry<String, String>> entryIterator = map.entrySet().iterator();
    while (entryIterator.hasNext()) {
        Map.Entry<String, String> entry = entryIterator.next();
        System.out.println(entry.getKey() + "-" + entry.getValue());
    }
}

获取员工工资大于18000的员工信息

Employee employee1 = new Employee("张三",1, 19000D);
Employee employee2 = new Employee("李四",2, 17000D);
Employee employee3 = new Employee("王五",3, 18000D);
HashMap<Integer, Employee> employeeHashMap = new HashMap<>();
employeeHashMap.put(employee1.getId(), employee1);
employeeHashMap.put(employee2.getId(), employee2);
employeeHashMap.put(employee3.getId(), employee3);


for (Map.Entry<Integer, Employee> entry : employeeHashMap.entrySet()) {
    if (entry.getValue().getSal() > 18000)
        System.out.println(entry.getValue());
}

for (Employee value : employeeHashMap.values()) {
    if (value.getSal() > 18000)
        System.out.println(value);
}

Iterator<Map.Entry<Integer, Employee>> iterator = employeeHashMap.entrySet().iterator();
while (iterator.hasNext()){
    Map.Entry<Integer, Employee> employeeEntry = iterator.next();
    if (employeeEntry.getValue().getSal() > 18000)
        System.out.println(employeeEntry.getValue());
}

// 使用StreamAPI
employeeHashMap.values().stream().filter(e -> e.getSal() > 18000).forEach(System.out::println);

HashMap

1. Map接口的常用实现类：HashMap、Hashtable和Properties。

2. HashMap是Map接口使用频率最高的实现类。

3. HashMap是以key-value对的方式来存储数据。

4. key不能重复，但是值可以重复，允许null键和null值。

5. 如果添加相同的key，则会覆盖原来的key-val。等同于修改。（key不会替换，value会替换）

6. 与HashSet一样，不保证映射的顺序，因为底层是以hash表的方式来存储的。

7. HashMap没有实现同步，因此是线程不安全的

构造方法源码如下：

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        //如果初始化容量大于最大容量，则仅初始化为最大容量。
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

/**
  *  指定初始化容量，使用默认的负载因子0.75来实例化HashMap
  */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
  * 无参构造方法，使用默认的初始化容量16 和 默认的负载因子0.75 实例化HashMap
  */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
  * 通过传入一个Map来创建HashMap. 比如：将TreeMap转为HashMap就可以使用此构造函数
  */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

put方法：

第一步，进行hash计算，将前16位也加入到计算中，可以降低Hash冲突的概率。

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

static final int hash(Object key) {
    int h;
   /**可以看到，当key为null时，默认返回0.则表示null会存放在下标为0的地方
     *可以看到这里使用hash值然后跟自身向右移动16的数进行异或运算，让hash值更加散列。
	 */
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

第二步，putVal

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /**table是HashMap的一个数组属性，Node[]*/
    if ((tab = table) == null || (n = tab.length) == 0)
        //resize 扩容 [无参，第一次put，初始化为16]
        n = (tab = resize()).length;
    //判断当前key应该存放在哪一个桶中，使用与运算来实现取模运算*/
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果数组上的节点为null，则表示当前桶位没有存放数据，直接创建一个节点，放置在tab的第i个位置上。
        tab[i] = newNode(hash, key, value, null);
    else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
        Node<K,V> e; K k;
        //p就是冲突的第一个位置[链表的第一个元素]。hash值相同，key相同，或者equals。表示key相同。
        //注意：相同的hash可能对应不同的key
        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 {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
                    p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
                    if (binCount >= TREEIFY_THRESHOLD - 1) //  TREEIFY_THRESHOLD - 1 = 7 如果
                        //当链表添加第9个时，就会触发树型化操作，即将链表转为红黑树。
                        // 那这里其实可以知道，链表存在的最长的串就是8个。
                        // 8个节点是一个临界值。（树化的另一个条件是，table的容量要大于等于64.否则进行数组扩容）
                        treeifyBin(tab, hash);
                    break;
                }
                //如果存在一样的key，则跳过，表示当前待插入元素和链表的某一个节点重复。所以加入，并跳出循环，不再比较
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;//相当于p=p.next
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            //onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
            //如果指定了onlyIfAbsent为true，则需要oldValue为null，
            // 才会进行值的覆盖，即才会存储。(putIfAbsent())
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;//值覆盖
            afterNodeAccess(e);
            return oldValue;//返回oldValue
        }
    }
    ++modCount;//并发操作，fast-fail
    if (++size > threshold)//size+1
        resize();
    afterNodeInsertion(evict);
    return null;
}

第三步：resize

final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table;//null
     int oldCap = (oldTab == null) ? 0 : oldTab.length;//0
     int oldThr = threshold;//0
     int newCap, newThr = 0;
     if (oldCap > 0) {
         if (oldCap >= MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
             return oldTab;
         } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){
             // newCap = oldCap << 1 扩容机制，新的容量是旧容量的2倍，新的阈值也是旧的阈值的两倍
             newThr = oldThr << 1;
         }
     } else if (oldThr > 0){
         newCap = oldThr;//8
     } else {               // zero initial threshold signifies using defaults
         newCap = DEFAULT_INITIAL_CAPACITY;//16
         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
     }
     if (newThr == 0) {
         float ft = (float)newCap * loadFactor;//16 * 0.75 = 12
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//12
     }
     threshold = newThr;//24
     @SuppressWarnings({"rawtypes","unchecked"})
     Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个Node类型的数组。
     table = newTab;//复制给HashMap的table属性
     if (oldTab != null) {
         for (int j = 0; j < oldCap; ++j) {//遍历数组
             Node<K,V> e;
             if ((e = oldTab[j]) != null) {//数组的第j个位置不为null
                 oldTab[j] = null;
                 if (e.next == null)
                     newTab[e.hash & (newCap - 1)] = e;//重新分布位置
                 else if (e instanceof TreeNode)//已经是树型，重新分布，即断树
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 else { // preserve order 保护顺序 [链表]
                     Node<K,V> loHead = null, loTail = null;//low
                     Node<K,V> hiHead = null, hiTail = null;//high
                     Node<K,V> next;
                     do {
                         next = e.next;
                         if ((e.hash & oldCap) == 0) {//如果hash%oldCap = 0，则表示在低位上
                             if (loTail == null)
                                 loHead = e;
                             else
                                 loTail.next = e;
                             loTail = e;
                         } else {// 否则将节点移动到新增的高位上
                             if (hiTail == null)
                                 hiHead = e;
                             else
                                 hiTail.next = e;
                             hiTail = e;
                         }
                     } while ((e = next) != null);//将原来仅分布在低位的节点，拆分到对应的高位和低位
                     if (loTail != null) {
                         loTail.next = null;
                         newTab[j] = loHead;
                     }
                     if (hiTail != null) {
                         hiTail.next = null;
                         newTab[j + oldCap] = hiHead;
                     }
                 }
             }
         }
     }
     return newTab;
 }

Hashtable

1. 存放的元素是键值对：即K-V
2. Hashtable的键和值都不能为null，否则会抛出NullPointerException；
3. Hashtable使用方法基本上和HashMap一样。
4. Hashtable是线程安全的，HashMap是线程不安全的。

初始化大小为11.负载因子是0.75；

public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: "+loadFactor);

    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

public Hashtable(int initialCapacity) {
    this(initialCapacity, 0.75f);
}

public Hashtable() {
    this(11, 0.75f);
}

public Hashtable(Map<? extends K, ? extends V> t) {
    this(Math.max(2*t.size(), 11), 0.75f);
    putAll(t);
}

扩容机制：oldCapacity * 2+1；

protected void rehash() {
    int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 扩容算法
    int newCapacity = (oldCapacity << 1) + 1;
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        if (oldCapacity == MAX_ARRAY_SIZE)
            // Keep running with MAX_ARRAY_SIZE buckets
            return;
        newCapacity = MAX_ARRAY_SIZE;
    }
    Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];

    modCount++;
    threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
    table = newMap;

    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
            Entry<K,V> e = old;
            old = old.next;

            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
            e.next = (Entry<K,V>)newMap[index];
            newMap[index] = e;
        }
    }
}

HashMap和Hashtable的对比：

	版本	线程安全（同步）	效率	允许null键null值
HashMap	1.2	不安全	高	可以
Hashtable	1.0	安全	较低	不可以

Properties

public class Properties extends Hashtable<Object,Object> {}

• Properties类继承自Hashtable类并且实现了Map接口。也是使用一种键值对的形式来保存数据。
• 它的使用特点和Hashtable类似
• Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改。

Properties不允许存放null键和null值，都会抛出NullPointerException；put方法继承自Hashtable.

从流中读取键值对存放到Properties中

public synchronized void load(Reader reader) throws IOException {
    load0(new LineReader(reader));
}
public synchronized void load(InputStream inStream) throws IOException {
    load0(new LineReader(inStream));
}

设置值, 可以使用setProperty和put方法。

public synchronized Object setProperty(String key, String value) {
    return put(key, value);
}

获取值，可以使用getProperty和get方法。

public String getProperty(String key) {
    Object oval = super.get(key);
    String sval = (oval instanceof String) ? (String)oval : null;
    return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval;
}
public String getProperty(String key, String defaultValue) {
    String val = getProperty(key);
    return (val == null) ? defaultValue : val;
}

TreeMap

底层是红黑树结构。

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;
        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;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);//遇到相同的key，会替换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++;
    modCount++;
    return null;
}

通过上述代码可以看到，要么提供了比较器【comparator】，要么key本身就是可比较的【(Comparable<? super K>) key;】即实现了Comparable接口，否则会抛出异常

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

如下代码，就会抛出异常：

public class TreeMapTest {
	public static void main(String[] args) {
		TreeMap<Student,Student> treeMap = new TreeMap<>();
		Student student = new Student();
		treeMap.put(student,new Student("A"));
		treeMap.put(student,new Student("B"));
		System.out.println(treeMap);
	}
}

class Student{
	private String name;

	public Student() {
	}

	public Student(String name) {
		this.name = name;
	}

	@Override
	public String toString() {
		return "Student{" +
				"name='" + name + '\'' +
				'}';
	}
}

代码执行是结果

Exception in thread "main" java.lang.ClassCastException: test.map.Student cannot be cast to java.lang.Comparable
	at java.util.TreeMap.compare(TreeMap.java:1290)
	at java.util.TreeMap.put(TreeMap.java:538)
	at test.map.TreeMapTest.main(TreeMapTest.java:10

集合选型

• 先判断存储的类型（一组对象【单列】或一组键值对【双列】）
• 一组对象【单列】：Collection接口
  • 允许重复：List
    • 增删多：LinkedList【底层维护了一个双向链表】
    • 查改多：ArrayList【底层维护Object类型的数组】
  • 不允许重复：Set
    • 无序：HashSet【底层是HashMap，维护了一个哈希表，即（数组+链表+红黑树）】
    • 排序：TreeSet
    • 插入和取出顺序一致：LinkedHashSet，维护数组和双向链表。
• 一组键值对【双列】：Map
  • 键无序：HashMap【底层是：哈希表 jdk7:数组+链表。jdk8：数组+链表+红黑树】
  • 键排序：TreeMap
  • 键插入的顺序和取出顺序一致：LinkedHashMap
  • 读取文件：Properties