集合体系图 Java 的集合可以分为两类：单列集合和双列集合。
单列集合：存储值（value）。
双列集合：存储键值对 （key-value）。
单列集合体系图（常用）

文章图片

双列集合体系图（常用）

文章图片

单列集合 Collection
Collection 接口特点

• 单列集合。
• 存储的元素可能是有序（List 的实现类），也可能是无序（Set 的实现类）。
• 存储的元素可能可以重复（List 的实现类），也可能不可以重复（Set 的实现类）。
  Collection 接口遍历方式实现 Collection 接口的类，有两种遍历方式：
  方式一：使用 Iterator 接口迭代器的执行原理：
  

文章图片

迭代器常用方法：

// 判断这次迭代是否还有下一个元素 boolean hasNext(); // 返回迭代的下一个元素（指针移动到下一个元素，返回上一个元素），如果没有下一个元素，会报异常 NoSuchElementException E next(); // 删除迭代器的这个元素，必须先调用 next()，才可以调用 remove()，否则会抛出异常 IllegalStateException remove()

迭代器使用示例：

Collection collection = new ArrayList<>(); for (int i = 0; i < 100; i++) { collection.add(i); }Iterator iterator = collection.iterator(); while (iterator.hasNext()) { Integer i = iterator.next(); System.out.println(i); }

方式二：增强 for 循环（使用 iterator 的简化版） 示例程序：

Collection collection = new ArrayList<>(); for (int i = 0; i < 100; i++) { collection.add(i); }// 增强 for 循环，底层也是迭代器 // 快捷方式，大写 I for(Integer i : collection) { System.out.println(i); }

底层原理：
增强 for 循环，其实底层也是 iterator。使用 idea 的 debug 功能打个断点测试下：
在循环入口打断点：

文章图片

在 ArrayList 的 iterator() 方法的实现打上断点：

文章图片

运行程序，发现程序会到 ArrayList 的 iterator 方法。
看下 ArrayList 的内部类 Itr 类，其实是 Iterator 接口的实现类：

private class Itr implements Iterator

所以增强 for 循环其实就是 Iterator 的简化版。
List 接口
接口特点 ? 有序
? 可重复
? 支持使用索引取出，索引从 0 开始。
List 的三种循环方式 List 的三种循环方式：
? 迭代器模式
? 增强 for 循环
? 普通 for 循环
Collection 的两种循环方式 List 实现 Collection 接口，间接实现 Iterable 接口，自然可以使用 Collection 的两种循环方式。
普通 for 循环 因为 List 的实现类内部都可以用索引，所以可以使用普通 for 循环。

List list = new ArrayList<>(); for (int i = 0; i < 10; i++) { list.add(i); }// 普通 for 循环 for (int i = 0; i < list.size(); i++) { // 通过索引取值 System.out.println(list.get(i)); }

ArrayList
ArrayList 的特点

• 可以存放 null 值。
• 可以存放重复值。
• 线程不安全，在多线程环境下不推荐使用。它和 Vector 类似，但 Vector 是线程安全的。

ArrayList 的扩容机制 ArrayList 内部存放数据的是一个 Object 数组。
从 ArrayList 的构造方法说起：

• 无参构造：默认容量是 0（一个定义好的空 Object 数组），使用 add 方法后，容量为 10，当容量不足时，扩大容量为原来的 1.5 倍。
• 指定容量的构造函数：容量为指定的容量，容量不足时，直接扩大为原来的 1.5 倍左右（偶数是 1.5 倍，奇数是 1.5 倍左右）。

源码分析（Java 11）

// 内部存储数据的是一个 Object 数组 transient Object[] elementData; // 无参构造 public ArrayList() { // DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组：private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = https://www.it610.com/article/{}; this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }// 有参构造 public ArrayList(int initialCapacity) { if (initialCapacity> 0) { // 创建指定容量的数组 this.elementData = https://www.it610.com/article/new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }// 扩容 private void add(E e, Object[] elementData, int s) { if (s == elementData.length) // 触发扩容，数组不够用时扩容 elementData = https://www.it610.com/article/grow(); elementData[s] = e; size = s + 1; }private static final int DEFAULT_CAPACITY = 10; // 真正拿到扩容后容量的方法 private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //>> 相当于 / 2，所以实际扩容时 1.5 倍左右。 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity <= 0) { if (elementData =https://www.it610.com/article/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // 第一次调用 add 实际上获得的新容量是 DEFAULT_CAPACITY = 10 return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); }

总结 ArrayList 特点：

• ArrayList 底层数据结构是数组。
• 可以存储 null 值。
• 是线程不安全的。

ArrayList 的扩容机制：

• 使用无参构造，默认容量为 0，第一次 add，会将容量扩为 10。当容量再不足时，会扩容为原来的 1.5 倍左右。
• 使用指定容量的构造方法，容量为指定容量，当容量不足时，会扩容为原来的 1.5 倍左右。
  （为什么是 1.5 倍左右：因为数组容量是整数，在右移时，如果是奇数，就不是 1.5 倍，而是 1.5 倍左右了。）
  Vector
  Vector 特点
• 可以存储 null
• 线程同步 synchronized （是线程安全的）,每个方法都同步，效率低于 ArrayList

Vector 源码分析（Java 11） Vector 底层数据结构是一个 Object 数组。

protected Object[] elementData;

还是来看构造方法：

• 无参构造方法：默认容量是 10。扩容增加为原来的 2 倍。
• 指定容量的构造方法：容量为指定容量。扩容增加为原来的 2 倍。

public Vector() { this(10); }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 = https://www.it610.com/article/new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; }

扩容机制：
最核心的代码如下：

int oldCapacity = elementData.length; int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

capacityIncrement 是Vector 的属性，不指定值时为 0。所以上面的代码可以被理解为：

int oldCapacity = elementData.length; // 扩容为原来的 2 倍 int newCapacity = oldCapacity + oldCapacity;

总结 Vector 特点：

• 底层结构是 Object 数组。
• 可以存储 null。
• 是线程同步的，线程安全。

扩容机制：在使用无参构造后，容量为 10。当容量不足时，会扩容为原来的 2 倍。
LinkedList
LinkedList 特点

• 底层是双向链接，添加和删除操作快。查询会效率低些（源码中做了优化，索引<长度一半 从头开始遍历，索引>=长度一半 从末尾开始遍历）
• 非线程安全

LinkedList 源码分析（Java 11） 它的底层是双向链接，有一个头节点 first 指向链表第一个节点，有一个尾节点 last 指向链表最后一个节点。size 变量用来维护链表的长度

transient int size = 0; transient Node first; transient Node last;

构造方法 无参构造：

public LinkedList() { }

是一个空方法体，实际上就是将 first、last 设为 null，size = 0。
增加 增加的逻辑实际是在 linkLast 这个方法中：

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; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }

新增的图解示意：

文章图片

删除 remove 实际上是删除链表第一个元素，实际的删除逻辑在方法 unlinkFirst 中

public E remove() { return removeFirst(); }public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; }

删除的图解示意：

文章图片

修改和查询 修改和查询放到一起是因为，修改其实就是先查询后修改，所以实际上主要的逻辑都在查询。查询实际上调用的方法是 node：

Node node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // index 小于长度的一半时，使用头节点向后遍历查找数据 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // index 大于等于长度的一半时，使用尾节点向前遍历查找数据 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

ArrayList 和 LinkedList 的对比与使用场景 在单线程的前提下：

• ArrayList 适合查询多、增删少的情景。（业务场景大部分都是查询，所以使用 ArrayList 场景非常多）
• LinkedList 适合增删多、查询少的情况。
  总结LinkedList 底层数据结构是双向链表。
  新增和删除效率高，随机访问效率低于 ArrayList。
  Set
  Set 接口的特点
• 无序
• 可以存放 null 值
• 不会存放重复元素

Set set = new HashSet(); set.add(null); set.add("tom"); set.add("amy"); set.add("jerry"); set.add("amy"); // [null, tom, jerry, amy] System.out.println(set);

Set 遍历 Set 继承 Collection，自然可以使用 Collection 的两种遍历方式：

// 遍历方式 // Collection 的两种方式Iterator iterator = set.iterator(); while (iterator.hasNext()) { Object o =iterator.next(); System.out.println("o = " + o); }System.out.println(); for (Object o : set) { System.out.println("o = " + o); }

总结 Set 接口的特点：无序、不重复、可以存放 null（因为不重复所以只能放一个 null）
Set 遍历的两种方式：就是 Collection 的两种遍历方式（由于继承 Collection 接口），不能使用索引遍历（List 独有特点）
HashSet
HashSet 特点 HashSet 底层是使用 hashMap，是数组加链表的形式。
在新增时，会先用 key 的 hash 值来找到数组的索引。如果已经有元素，那么需要判断是否相等，如果相等就不添加。如果相等，就在原来的元素后面追加新的元素。形成链表。当链表长度 >= 8 并且数组长度大于 64（默认值） 时，会树化。
HashSet 源码分析（Java 8） 构造方法

public HashSet() { map = new HashMap<>(); }

可以看到构造方法其实是初始化一个 HashMap。
新增

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

可以看到实际是 map（HashMap 对象） 调用 put 方法，value 是 PRESENT，而 PRESENT 是一个静态的、final Object 对象：

private static final Object PRESENT = new Object();

所以实际上我们需要看的是 HashMap 的 put 方法的实现：

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

首先会先对 key 进行 hash 计算，看一下 hash 计算是如何计算：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

hash 计算方式：key 的 hashCode ^ key 的 hashCode 向右移位 16 位。（向右移位不容易让各个位为 0，更方便）
接下来就会调用 putVal：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; // table 是一个 Node 数组， n 也就是 数组长度 if ((tab = table) == null || (n = tab.length) == 0) // 第一次会进入 resize() 方法，tab = 长度为 16 的数组 n = (tab = resize()).length; // i = (n - 1) & hash，找到 key 对应的数组索引，赋值给 i, p 指向 table[i] 数组元素 if ((p = tab[i = (n - 1) & hash]) == null) // 索引对应的元素为 null，说明没节点，直接添加 tab[i] = newNode(hash, key, value, null); else { Node e; K k; // 虽然没有 if 中的内容，但是在判断时就执行 if 的条件，所以 p 在这处 指向 table[i] 数组元素 // p.hash == hash && ((k = p.key) == key，判断 key 和目前在这里的 key 否是同一个 key // key != null && key.equals(k), 判断 key 和目前这里的 key 是否相同 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) // 满足两者中其一的条件， e = p = table[i] e = p; else if (p instanceof TreeNode) // 如果 p 是树节点，则采用树的添加方法 putTreeVal e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { // p 不和数组key完全相同，并且是链表，通过遍历这个链表确认，新加入的元素(HashMap$Node)和链表中原来的元素不相同,如果有相同项会提前退出循环，没有则加新加入的追加到链表末尾，并且追加后立即判断链表长度是否 >= 8, 满足条件时会调用 treeifyBin 方法确认是否需要树化。当 table 长度 >= 64 时，会将链表转为树。 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD 8 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 = https://www.it610.com/article/e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 当 table 数组长度大于 threshold（容量 * 负载因子（0.75），就会触发扩容） if (++size> threshold) resize(); afterNodeInsertion(evict); return null; }

其中在第一次添加元素时，会调用 resize() 方法，将 table 初始化为长度 16 的数组：

final Node[] resize() { Node[] oldTab = table; // oldCap 原来容量 = 0 int oldCap = (oldTab == null) ? 0 : oldTab.length; // 方便查看，省略代码 else {// zero initial threshold signifies using defaults // 会进入这个 if-else 分支，DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16 // newThr = 16 newCap = DEFAULT_INITIAL_CAPACITY; // DEFAULT_LOAD_FACTOR = 0.75，newThr = 12 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //threshold = newThr = 12 threshold = newThr; // 初始化 table 数组，长度为 16 @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; // 原来数组内容拷贝到新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { // 方便查看，省略代码 } } return newTab; }

treeifyBin 方法，要进行树化前会先判断 table 长度：

final void treeifyBin(Node[] tab, int hash) { int n, index; Node e; // MIN_TREEIFY_CAPACITY = 64 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // table 不足 64 时会先扩容 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode hd = null, tl = null; do { TreeNode p = replacementTreeNode(e, null); if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) hd.treeify(tab); } }

重新看下 resize()：

final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; 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 为原来两倍 // newThr 也为原来两倍 newThr = oldThr << 1; // double threshold } // 省略代码 .... threshold = newThr; // 创建新数组，并将旧数组内容拷贝到新数组，完成扩容 @SuppressWarnings({"rawtypes","unchecked"}) Node[] newTab = (Node[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node 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)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.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; }

总结 hashSet，底层实现是 hashMap，每次新增对象，就是往 hashMap 中放 key = 新增对象，value = https://www.it610.com/article/定义好的静态不变对象。
在新增元素时，会先根据 key 的 hash 值来找到数组索引，找到数组索引对应的那条链表，如果为 null 直接添加元素，如果不为 null 需要判断新增元素 key 和以前的是否是同一个对象或者完全相同。如果相同，则不添加，否则将元素追加到这条链表的末尾。
【Java集合知识点总结和重点源码分析】当一条链表长度 >=8 并且数组长度大于 64 时，会将这个链表转为红黑树。
触发扩容：第一次新增元素，会初始化 table 数组，容量会变为 16，临界值变为 12（16 * 0.75）。在整个 hashMap 中元素个数大于临界值时会进行扩容，每次扩容为原来的 2 倍。
LinkedHashSet
特点 继承 HashSet，有序不重复。
源码分析 (Java 11) 底层使用的 LinkedHashMap，他的底层数据结构是 哈希表 + 双向链表。
每次创建新节点时，会维护这个双向链表：

// 创建新节点的方法 Node newNode(int hash, K key, V value, Node e) { LinkedHashMap.Entry p = new LinkedHashMap.Entry<>(hash, key, value, e); linkNodeLast(p); return p; }

LinkedHashMap.Entry 是这里的节点类，它继承于 HashMap 的内部类 Node，但是每个节点拥有前后指针（before、after）。

static class Entry extends HashMap.Node { Entry before, after; Entry(int hash, K key, V value, Node next) { super(hash, key, value, next); } }

在 newNode 中调用 linkNodeLast 来维护每个节点组成的双向链表：

// 双向链表头节点 transient LinkedHashMap.Entry head; // 双向链表尾节点 transient LinkedHashMap.Entry tail; private void linkNodeLast(LinkedHashMap.Entry p) { LinkedHashMap.Entry last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }

head 和 tail 分别指向头节点和尾节点，看代码可以看出这就是将节点添加到链表的操作。
总结 LinkedHashSet 继承 HashSet 实现 Set。它和 HashSet 的区别是它是有序不重复集合。
底层使用的 LinkedHashMap，它的实现是哈希表 + 双向链表。通过双向链表来维持顺序。
TreeSet
特点

• 不能存 null。
• 默认是按照 key 的类型的升序排序，如果需要其他排序规则，可以通过构造器传入 Comparator。
• 传入 Comparator 时，只要他的方法 compareTo 返回 0，则新的值会被旧的值替代。

源码分析（Java 11） TreeSet 的底层实际上是使用的 TreeMap。它和 HashSet 的区别就在于，在修改集合（增删）时，会根据 key 值排序。可以通过构造器传入 Comparator，传入 Comparator 时，只要compareTo 返回 0，新的值会被旧的值替代。

public boolean add(E e) { return m.put(e, PRESENT)==null; }public V put(K key, V value) { Entry t = root; if (t == null) { // 第一个节点时,compare 的作用只是为了检测 null 值 compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry parent; // split comparator and comparable paths Comparator 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 // key 在对应的比较规则下，如果相同，会被修改。 return t.setValue(value); } while (t != null); } else { // 使用 key 类型的构造器比较 if (key == null) // key 不能为 null，会报错 throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable k = (Comparable) 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 e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }

总结

• TreeSet 底层使用的是 TreeMap。
• TreeSet 不能存 null。
• 在修改集合（增删）时，会根据 key 值排序。可以通过构造器传入 Comparator，传入 Comparator 时，只要compareTo 返回 0，新的值会被旧的值替代。

双列集合 Map
特点

• 双列集合
• 存储 k-v 键值对
• key 不能重复

Map 遍历的 2 类 6 种方式 遍历 key-value：

• 用 keySet 方法遍历（迭代器 + 增强 for 循环）
• 用 entrySet 方法遍历（迭代器 + 增强 for 循环）

遍历 value：

• 用 values 方法遍历（数组）

import java.util.*; public class MapFor { public static void main(String[] args) { Map hashMap = new HashMap<>(); hashMap.put("zhangsan", "aaa"); hashMap.put("lisi", "bbb"); // 遍历 key-value// 增强 for 循环 System.out.println("增强 for 循环"); Set keySet = hashMap.keySet(); for (String key : keySet) { System.out.println(key + "-" + hashMap.get(key)); }// 迭代器 System.out.println("迭代器"); Iterator iterator = keySet.iterator(); while (iterator.hasNext()) { String key = iterator.next(); System.out.println(key + "-" + hashMap.get(key)); }// entry System.out.println("entry 增强 for 循环"); Set entrySet = hashMap.entrySet(); for (Map.Entry entry : entrySet) { System.out.println(entry.getKey() + "-" + entry.getValue()); }System.out.println("entry 迭代器"); Iterator entryIterator = entrySet.iterator(); while (entryIterator.hasNext()) { Map.Entry entry = entryIterator.next(); System.out.println(entry.getKey() + "-" + entry.getValue()); }// 遍历 value // 增强 for 循环 Collection values = hashMap.values(); for (String value : values) { System.out.println(value); }Iterator valueIterators = values.iterator(); while (valueIterators.hasNext()) { String value = https://www.it610.com/article/valueIterators.next(); System.out.println(value); } } }

HashMap
HashMap 特点

• 存放 key-value，key 是唯一的，相同的 key 值，value 会覆盖上一次存放的 value。
• key 和 value 都可以为 null，但是一个 HashMap 只能有一个 null。不同的 key 可以有多个 null。
• HashMap 设计者为了方便程序员遍历，将每个 k-v （HashMap$Node）放入 entrySet，里面存放的类型是 Map$Entry 类型。Map$Entry 有 getKey、getValue 方法，方便遍历。
• 非线程安全

源码分析 可以看 HashSet 的源码分析，HashSet 的源码分析实际上就是再将 HashMap。
HashTable
特点

• 存储 k-v
• key 和 value 都不可以为 null
• 线程安全
  HashTable 源码分析底层是数组加链表。数组是：HashTable$Entry 数组。链表节点是 HashTable$Entry。
  

构造方法

public Hashtable() { this(11, 0.75f); }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); }

默认容量是 11，加载因子为 0.75。阈值 = 11 * 0.75 约等于 8
增加

public synchronized V put(K key, V value) { // Make sure the value is not null if (value =https://www.it610.com/article/= null) { throw new NullPointerException(); }// Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); // 找到索引 int index = (hash & 0x7FFFFFFF) % tab.length; @SuppressWarnings("unchecked") Entry entry = (Entry)tab[index]; for(; entry != null ; entry = entry.next) { if ((entry.hash == hash) && entry.key.equals(key)) { V old = entry.value; entry.value = https://www.it610.com/article/value; return old; } }addEntry(hash, key, value, index); return null; }

通过 (整数最大值 & key 的 hash) % 数组长度 获取下标
主要的增加逻辑在这个方法 addEntry 上：

private void addEntry(int hash, K key, V value, int index) { Entry tab[] = table; if (count >= threshold) { // 元素数量大于阈值，会使用 rehash() 扩容 // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; }// Creates the new entry. @SuppressWarnings("unchecked") Entry e = (Entry) tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; modCount++; }

扩容机制 ?rehash 方法

int newCapacity = (oldCapacity << 1) + 1;

可以看到扩容为 2n + 1 倍。
总结 HashTable 和 HashMap 的区别：

?	HashMap	HashTable
k-v 可以为 null	是	否
底层数据结构	jdk7：数组+链表 jdk8：数组+链表+红黑树	数组+链表
默认容量	16	11
加载因子	0.75	0.75
扩容机制	2n	2n + 1
线程安全	否	是
找索引方式	hash & (n - 1)	(hash & 0x7FFFFFFF) % tab.length
阈值（触发扩容）	>=12	>=8
树化	jdk8，table长度>=64，链表长度>=8	无树化操作

LinkedHashMap
特点

• 存储 k-v
• 底层为 hash表 和双向链表
• key 可以为 null
  源码分析（Java 11）LinkedHashSet 底层就是用的 LinkedHashMap,直接看 LinkedHashSet 源码分析就可以。
  

TreeMap
特点

• 存 k-v
• key 不能为 null，值可以为 null。
• 默认是按照 key 的类型的升序排序，如果需要其他排序规则，可以通过构造器传入 Comparator。
• 传入 Comparator 时，只要他的方法 compareTo 返回 0，则新的值会被旧的值替代

源码分析（Java 11） TreeSet 底层使用的就是 TreeMap，可以直接看 TreeSet 的源码分析。
总结 集合分为单列集合和双列集合。
单列集合父接口：Collection。
双列集合父接口：Map。
按照集合体系图从上往下特点是会继承过来的，同级的可以对比记忆（比如 HashMap 和 HashTable）。

推荐阅读

• 

  云顶之弈s3肉盾流阵容怎么玩 重装坦克阵容搭配推荐
• 

  从金平去看汕头烟花怎么去？ 汕头市金平区哪里有卖烟花
• 

  大金中央空调L5错误代码解决方法步骤有哪些,看师傅怎么说的
• 

  盲目的婚姻得不到爱情的回应
• 

  45和6的最小公倍数 45和6的最小公倍数是多少
• 

  男人肾阳不足如何调理,吃这些补回来
• 

  晚上做梦梦见蛇什么意思 晚上做梦梦见蛇好不好
• 

  减肥|晚上坚持这4件小事，有助于身体燃脂，你能做到几件？
• 

  描写桑葚的有名诗句 关于桑葚的诗句有哪些
• 

  芙蓉楼送辛渐意思 芙蓉楼送辛渐全诗的意思
• 

  宁波养老金组成及养老金怎么计算出来的？
• 

  室内适宜养的花有哪些 室内宜养的花有哪些
• 

  茅台女总工落选院士增选有效候选人名单！ 茅台总工落选中国工程院院士候选人
• 

  唏嘘不已啥意思 词语唏嘘不已啥意思
• 

  结婚日和属相相冲怎么办
• 

  写小说有多累？
• 

  佳能kiss用什么镜头 佳能kissx5怎么拍人物
• 

  老阿姨哔哩哔哩b站肉片入口 美国proumb站官网入口网址是多少
• 

  核酸检测报告纸质版和电子版同步吗
• 

  宝宝|宝宝还太小？到底要不要带出门？对于这些你的想法也许是错误的

• 数据库|Mysql高级篇
• 同事写了一个责任链模式，bug 无数...
• java实战开发|阿里巴巴《Java开发手册(黄山版)》阅读笔记
• 剑指offer|剑指 Offer II 049. 从根节点到叶节点的路径数字之和
• 大数据|计算机科学领域 直接 间接_为什么计算机科学领域的女性很少（）
• 软件测试|接口测试项目（非常值得练手）
• https|https加密的基本原理
• 分布式|SpringCloud Netflix-Hystix使用
• 笔记|高中毕业，经过半年培训后成功拿到了美团的offer