概念

1.集合主要是两组:单列集合(Collection) , 双列集合(Map)
2.Collection 接口有两个重要的子接口 List ,Set . 他们的实现子类都是单列集合

3.Map 接口的实现子类 是双列集合，存放的 K-V

Iterable

单列集合的顶级接口,含有Iterator()方法,主要用于遍历Collection集合中的元素
Collection的所有实现类都有Iterator()方法,返回值为调用该方法的实现类对象
1.常用方法:

Iterator iterator = collection.iterator();//获取集合的迭代器
iterator.hasNext();//是否存在下一个元素,仅判断
iterator.next();//返回集合中的当前元素,初始指向集合中第一个元素,调用一次,指针往下挪一位
iterator.remove();//移除集合中的当前元素,初始指向集合中第一个元素,调用一次,指针往下挪一位

2.常用一下方法遍历集合
idea快捷键: itit | itco

Iterator<Integer> iterator = collection.iterator();
while (iterator.hasNext()){System.out.println(iterator.next());
}

遍历完后,不可在调用iterator.next(),会抛出NoSuchElementException异常
如果还想使用,在使用collection.iterator()获取一个迭代器即可

3.增强for循环就是简单版本的iterator(),底层是迭代器,集合,数组都可以使用

for (Object object: collection) {System.out.println(object);
}

Collection接口

Collection 接口常用方法:

collection.add(1);//添加一个元素
collection.addAll();//添加一个集合中的所有元素
collection.remove();//删除指定元素
collection.removeAll();//删除传入集合中的所有元素
collection.clear();//清空集合
collection.contains();//判断集合是否含有传入元素
collection.containsAll();//判断集合是否包含传入集合的所以有元素
collection.size();//集合大小
collection.isEmpty();//判断集合是否为空

List接口

List中的元素是有序的,存入和取出顺序一致,且元素可重复
List中所有元素都有索引(从0开始),可以根据索引取元素
1.List中的常用方法

list.get(index);//获取指定索引的元素
list.indexOf(item);//获取指定元素首次出现的索引
list.lastIndexOf(item);//获取指定元素最后出现的索引
list.add(index,item);//在index 和 index-1 之间添加一个元素
list.remove(index);//根据指定索引删除元素
list.set(index,item);//替换指定索引元素
list.subList(l,r);//返回 l<= i < r之间的元素

2.遍历List的方法
1.简单for循环
2.增强for循环
3.iterator

ArrayList

可以存放一或多个null值,list.add(null);
有数组实现数据存储
线程不安全

		ArrayList list = new ArrayList();//使用 for 给 list 集合添加 1-10 数据for (int i = 1; i <= 10; i++) {list.add(i);}//使用 for 给 list 集合添加 11-15 数据for (int i = 11; i <= 15; i++) {list.add(i);}list.add(100);list.add(200);list.add(null);

执行流程 && 底层源码分析:
扩容机制:

transient Object[] elementData;//内部维护的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组
private static final int DEFAULT_CAPACITY = 10;
1.
//无参构造创建
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2.public boolean add(E e) {ensureCapacityInternal(size + 1);  //判断当前数组大小是否够用,不够进行扩容处理elementData[size++] = e;return true;}3.private void ensureCapacityInternal(int minCapacity) {//此时minCapacity为1 ,是size+1传递过来的size初始为0ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)//判断内部数组长度大于还是小于10);}
4.1private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//判断维护数组是否为空数组//DEFAULT_CAPACITY为10return Math.max(DEFAULT_CAPACITY, minCapacity);//返回10和原数组大小较大的一个}//首次长度初始化为10return minCapacity;}
4.2private void ensureExplicitCapacity(int minCapacity) {modCount++;//记录集合被修改的次数// overflow-conscious codeif (minCapacity - elementData.length > 0)//如果外部数组长度大于内部数组长度,则扩容grow(minCapacity);//扩容
}
5.private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//oldCapacity 为 1int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为1.5倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;//无参构造创建,首次扩容为10if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);	// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);//将旧数组拷贝到新，如果新数组的长度超过原数组的长度,其余用默认值填充}
6.一步一步返回,如此循环,满了就1.5本扩容,直到MAX_ARRAY_SIZE ,如果使用有参构造传入value,那么,就按照传入的值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);}}

Vector

1.Vector是线程同步的即线程安全的,所有的方法都带有synchronized
2.无参构造创建: 默认内部数组为10 ,之后2倍扩容,有参构造指定长度,按指定2倍长度扩容

1.Vector底层也是一个对象数组
protected Object[] elementData;扩容源码分析:无参
1.    
public Vector() {this(10);//默认内部数组初始大小
}
2.public Vector(int initialCapacity) {this(initialCapacity, 0);}
3.public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);this.elementData = new Object[initialCapacity];//创建初始值为10的内部数组this.capacityIncrement = capacityIncrement;}
4.第一次add
protected int elementCount;//数组中有效元素个数public synchronized boolean add(E e) {modCount++;//记录修改次数ensureCapacityHelper(elementCount + 1);//elementData[elementCount++] = e;return true;}
4.1	private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)//数组有效元素长度 - 数组总长度grow(minCapacity);}
4.2由于数组初始长度为10,add 10次后进入grow方法
protected int capacityIncrement;//容器自增量,可以在创建集合是设置,为构造器第二个参数private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);//默认自增量为0,所以默认扩容两倍if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}其他:
有参:
指定初始长度public Vector(int initialCapacity) {this(initialCapacity, 0);}
指定初始长度和每次扩容量public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;}

LinkedList

1.LinkedList底层维护一个双向链表,更具索引获取值时,索引从0开始
2.内部维护了一个静态内部类

    private static class Node<E> {E item;//当前节点的值Node<E> next;//指向下一个节点Node<E> prev;//指向前一个节点Node(Node<E> prev, E element, Node<E> next) {this.item = element;//this.next = next;this.prev = prev;}}

简单操作:

        LinkedList<Integer> linkedList = new LinkedList<>();linkedList.add(1);

LinkedList初始化及CURD源码分析:

几个重要参数:
transient int size = 0;//链表长度
transient Node<E> first;//第一个结点位置
transient Node<E> last;//最后一个结点位置
protected transient int modCount = 0;//此列表在结构上被修改的次数,防止线程安全问题,如果该字段的值意外变化，迭代器(或列表迭代器)将抛出ConcurrentModificationException异常来响应next、remove、previous、set或add操作。这提供了快速失败的行为，//无参构造初始化public LinkedList() {}
增加:
1.  public boolean add(E e) {linkLast(e);return true;}
2.void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}
调用静态节点类的构造方法Node(Node<E> prev, E element, Node<E> next) {this.item = element;//给当前节点赋值this.next = next;//增加节点的next指向下一个节点this.prev = prev;//prev指向上一个结点}  
删除:1.linkedList.removeFirst();//删除头节点调用核心方法:private E unlinkFirst(Node<E> f)2.linkedList.removeLast();//删除尾节点调用核心方法:private E unlinkLast(Node<E> l) 上述2个3.linkedList.remove();//底层调用的是removeFirst4.linkedList.remove(new Integer(4));//删除指定对象节点5.linkedList.remove(3);//更具索引删
上述3个方法的核心都是在E unlink(Node<E> x)上进行修改或加以限制,
E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;//重新指定删除结点的下一个节点的prev指向if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}//重新指定删除结点的上一个节点的next指向if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;}
查找:1.linkedList.get(1);//返回指定索引节点保存的数据值2.linkedList.getLast();3.linkedList.getFirst();
更改:
linkedList.set(index,value);更具指定索引,修改对应的节点数据

ArrayList 和 LinkedList 比较

查找多,用ArrayList
修改多,用LinkedList

Set

无序(添加和取出元素顺序,但取出顺序固定不变),没索引.
不允许有重复元素

遍历方法:
迭代器
增强for循环
不能用索引方式

HashSet

1.HashSet底层实际上时HashMap
2.第一次添加是内部的table数组扩容到16,再次扩容临界值是16 * 加载因子(默认0.75) 为12,下次扩容临界值是 2 乘以16 乘以0.75 为24
3.在Java8中如果一条链表的元素个数 达到 8 也就是>=7 且table数组大小大于64,就会进行树化(红黑树).否则仍采用数组扩容机制

1.HashSet底层是HashMap
2.添加元素时，先计算得到hash值会转成索引值,找到存储数据表table,若果索引位置没有元素则直接加入,若已经存放有元素则调用equals比较,为true,就放弃添加,不相同，再判断 p 是不是一颗红黑树, 如果是一颗红黑树，就调用 putTreeVal , 来进行添加.不是红黑树,依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后.

        HashSet hashSet = new HashSet();hashSet.add("java");hashSet.add("java");hashSet.add("php");

源码分析:无参构造初始化public HashSet() {map = new HashMap<>();}
1.添加 "java"public boolean add(E e) {return map.put(e, PRESENT)==null;}
2.public V put(K key, V value) {return putVal(hash(key)//计算哈希值, key, value, false, true);}
2.1static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
3.进入putVall方法
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 语句表示如果当前 table 是 null, 或者 大小=0//table 就是 HashMap 的一个数组，类型是 Node[]//if 语句表示如果当前 table 是 null, 或者 大小=0//就是第一次扩容，到 16 个空间.if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//刚开始tab为空,进入resize()方法进行第一次扩容
//(1)根据 key，得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置
//并把这个位置的对象，赋给 p
//(2)判断 p 是否为 null
//(2.1) 如果 p 为 null, 表示还没有存放元素, 就创建一个 Node (key="java",value=PRESENT)
//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//如果当前索引位置对应的链表的第一个元素和准备添加的 key 的 hash 值一样//并且满足 下面两个条件之一://(1) 准备加入的 key 和 p 指向的 Node 结点的 key 是同一个对象//(2) p 指向的 Node 结点的 key 的 equals() 和准备加入的 key 比较后相同//就不能加入Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//再判断 p 是不是一颗红黑树, //如果是一颗红黑树，就调用 putTreeVal , 来进行添加else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {
//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后
// 注意在把元素添加到链表后，立即判断 该链表是否已经达到 8 个结点
// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)
// 注意，在转成红黑树时，要进行判断, 判断条件
// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
// resize();
// 如果上面条件成立，先 table 扩容. // 只有上面条件不成立时，才进行转成红黑树
//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接 breakfor (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(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 keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);//留给子类重写return null;//返回null代表添加成功}3.1 第一次扩容
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; static final float DEFAULT_LOAD_FACTOR = 0.75f;
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {//falseif (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in threshold//falsenewCap = oldThr;else {               // zero initial threshold signifies using defaults//初始化newCap = DEFAULT_INITIAL_CAPACITY;//第一次扩容大小: 16,默认初始大小newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//当数据大小为0.75 * 16时再次扩容}if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//赋值,正真扩容!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[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 orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;//返回}

LinkedHashSet

1.LinkedHashSet使用hashcode值来决定元素的存储位置,使用双向链表维护元素的次序,元素以插入顺序保存.(加入和取出元素顺序一致)
2.LinkedHashSet底层是一个LinkedHashMap(是HashMap的子类),底层维护一个数组加双向链表
3.LinkedHashSet不能插入重复元素
4.第一次添加时将数组 table(table的类型是HashMap$Node[])扩容到16,存放的结点类型是LinkedHashmap$Entry
LinkedHashmap$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);}}

常用方法:

Map

Set 中 k-v k是添加值,v是present常量,只用了k
Map 中 k - v 都由用户添加
1.Map与Collection并列存在。用于保存具有映射关系的数据:Key-Value(双列元素)
2.Hap中的 key 和 value 可以是任何引用类型的数据，会封装到HashMap$Node对象中
3. Map中的key不允许重复，原因和HashSet一样，前面分析过源码。
4. Map中的value可以重复,如果key相同,则覆盖之前的value
5. Map 的 key 可以为 null, value 也可以为 null ，注意 key 为 null,
6. 常用 String 类作为 Map 的 key
7. key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value

常用方法:

Map map = new HashMap();
map.put(key, value);//替换-> 一会分析源码
map.remove(key)根据键删除映射关系
map.get(key)根据键获取值
map.size();获取元素个数
map.containsKey(key)是否包含指定key
map.isEmpty();判断个数是否为空 
map.clear();清空集合

遍历:

//第一组: 先取出 所有的 Key , 通过 Key 取出对应的 Value
Set keyset = map.keySet();
//(1) 增强 for
System.out.println("-----第一种方式-------");
for (Object key : keyset) {
System.out.println(key + "-" + map.get(key));
}
//(2) 迭代器
System.out.println("----第二种方式--------");
Iterator iterator = keyset.iterator();
while (iterator.hasNext()) {
Object key = iterator.next();
System.out.println(key + "-" + map.get(key));
}//第二组: 把所有的 values 取出
Collection values = map.values();
//这里可以使用所有的 Collections 使用的遍历方法
//(1) 增强 for
System.out.println("---取出所有的 value 增强 for----");
for (Object value : values) {
System.out.println(value);
}
//(2) 迭代器
System.out.println("---取出所有的 value 迭代器----");
Iterator iterator2 = values.iterator();
while (iterator2.hasNext()) {
Object value = iterator2.next()
System.out.println(value);
}//第三组: 通过 EntrySet 来获取 k-v
Set entrySet = map.entrySet();// EntrySet<Map.Entry<K,V>>
//(1) 增强 for
System.out.println("----使用 EntrySet 的 for 增强(第 3 种)----");
for (Object entry : entrySet) {
//将 entry 转成 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
//(2) 迭代器
System.out.println("----使用 EntrySet 的 迭代器(第 4 种)----");
Iterator iterator3 = entrySet.iterator();
while (iterator3.hasNext()) {
Object entry = iterator3.next();
//System.out.println(next.getClass());//HashMap$Node -实现-> Map.Entry (getKey,getValue)
//向下转型 Map.Entry
Map.Entry m = (Map.Entry) entry;
System.out.println(m.getKey() + "-" + m.getValue());
}
}

HashMap

jdk8: 底层是数组+链表+红黑树
数组长度大于64 且 链表长度大于8 该节点的链表树化

1. HashMap底层维护了Node类型的数组table，默认为null
   2)当创建对象时，将加载因子(loadfactor)初始化为0.75.
   3)当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素,
   如果没有元素直接添加。如果该索引处有元素,继续判断该元素的key是否和准备加入的key相等，如果相等，则直接替换val;如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
   4)第1次添加，则需要扩容table容量为16，临界值(threshold)为12.,以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍,即24,依次类推.
   6)在Java8中,如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，粗table的大小>= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树)

1.k-v最后是 HashMap.Node node = newNode(hash,key,value,null)
2.k-v为了方便程序员的遍历，创建了EntrySet集合，该集合存放的元素的类型Entry，而一个Entry对象就有k ,v EntrySet<Entry<K,V>>即: transient Set<Map. Entry<K, V>> entrySet;
3. entrySet中，定义的类型是Map.Entry ，但是实际上存放的还是 HashMap.Node,这是因为 HashMap.Node implements Map.Entry
4.当把 HashMap.Node 对象存放到entrySet 就方便我们的遍历，因为 Map.Entry 提供了重要方法K getKey V getValue();
5.实际上就是把所有HashMap$Node转成Entry,然后把所有Entry放到EntrySet中(存放的是地址,不是实际数据),方便程序员遍历,EntrySet中的数据实际指向的是类型为HashMap Node[] 的table表中的数据(存放的是地址,不是实际数据)

内部节点
//实现implements Map.Entry<K,V>接口
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; }//getKeypublic final V getValue()      { return value; }//getValuepublic 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;}}
EntrySet 中包含所有Entry,但是不能直接获取Entry对象,可以使用增强for循环遍历
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {......}所以还提供了直接获取所有key的内部类
final class KeySet extends AbstractSet<K> {.......}
以及直接获取所有Value的内部类
final class Values extends AbstractCollection<V> {......}

解析 hashMap.put(key,value)
扩容等机制和HashSet基本一样

1.public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
2.
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;//hash值对应的数组索引为空,直接放入if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {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 1sttreeifyBin(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)e.value = value;//新值覆盖旧值afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;}细致分析
// 1. 执行构造器 new HashMap()//初始化加载因子 loadfactor = 0.75//HashMap$Node[] table = null//2. 执行 put 调用 hash 方法，计算 key 的 hash 值 (h = key.hashCode()) ^ (h >>> 16)public V put(K key, V value) {//K = "java" value = 10return putVal(hash(key), key, value, false, true);}3. 执行 putValfinal V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//辅助变量
//如果底层的 table 数组为 null, 或者 length =0 , 就扩容到 16if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;
//取出 hash 值对应的 table 的索引位置的 Node, 如果为 null, 就直接把加入的 k-v
//, 创建成一个 Node ,加入该位置即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//辅助变量
// 如果 table 的索引位置的 key 的 hash 相同和新的 key 的 hash 值相同，
// 并 满足(table 现有的结点的 key 和准备添加的 key 是同一个对象 || equals 返回真)
// 就认为不能加入新的 k-vif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)//如果当前的 table 的已有的 Node 是红黑树，就按照红黑树的方式处理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);
//加入后，判断当前链表的个数，是否已经到 8 个，到 8 个，后
//就调用 treeifyBin 方法进行红黑树的转换if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash && //如果在循环比较过程中，发现有相同,就 break,就只是替换 value((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value; //替换，key 对应 valueafterNodeAccess(e);return oldValue;}}++modCount;//每增加一个 Node ,就 size++if (++size > threshold[12-24-48])//如 size > 临界值，就扩容resize();afterNodeInsertion(evict);return null;}5. 关于树化(转成红黑树)
//如果 table 为 null ,或者大小还没有到 64，暂时不树化，而是进行扩容. //否则才会真正的树化 -> 剪枝final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();}
*/}
}