汇合体系图
Java 的汇合能够分为两类：单列汇合和双列汇合。
单列汇合：存储值（value）。
双列汇合：存储键值对（key-value）。
单列汇合体系图（罕用）
双列汇合体系图（罕用）
单列汇合
Collection
Collection 接口特点
- 单列汇合。
- 存储的元素可能是有序（List 的实现类），也可能是无序（Set 的实现类）。
-
存储的元素可能能够反复（List 的实现类），也可能不能够反复（Set 的实现类）。
Collection 接口遍历形式
实现 Collection 接口的类，有两种遍历形式：
形式一：应用 Iterator 接口
迭代器的执行原理：
迭代器罕用办法：
// 判断这次迭代是否还有下一个元素
boolean hasNext();
// 返回迭代的下一个元素（指针挪动到下一个元素，返回上一个元素），如果没有下一个元素，会报异样 NoSuchElementException
E next();
// 删除迭代器的这个元素，必须先调用 next()，才能够调用 remove()，否则会抛出异样 IllegalStateException
remove()迭代器应用示例：
Collection<Integer> collection = new ArrayList<>();
for (int i = 0; i < 100; i++) {collection.add(i);
}
Iterator<Integer> iterator = collection.iterator();
while (iterator.hasNext()) {Integer i = iterator.next();
System.out.println(i);
}形式二：加强 for 循环（应用 iterator 的简化版）
示例程序：
Collection<Integer> 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<E> 所以加强 for 循环其实就是 Iterator 的简化版。
List 接口
接口特点
• 有序
• 可反复
• 反对应用索引取出，索引从 0 开始。
List 的三种循环形式
List 的三种循环形式：
• 迭代器模式
• 加强 for 循环
• 一般 for 循环
Collection 的两种循环形式
List 实现 Collection 接口，间接实现 Iterable 接口，天然能够应用 Collection 的两种循环形式。
一般 for 循环
因为 List 的实现类外部都能够用索引，所以能够应用一般 for 循环。
List<Integer> 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 = {};
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 有参结构
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);
}
}
// 扩容
private void add(E e, Object[] elementData, int s) {if (s == elementData.length)
// 触发扩容，数组不够用时扩容
elementData = 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 == 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 = 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<E> first;
transient Node<E> last;构造方法
无参结构：
public LinkedList() {}
是一个空办法体，实际上就是将 first、last 设为 null，size = 0。
减少
减少的逻辑理论是在 linkLast 这个办法中：
public boolean add(E e) {linkLast(e);
return true;
}
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;
else
l.next = newNode;
size++;
modCount++;
}新增的图解示意：
删除
remove 实际上是删除链表第一个元素，理论的删除逻辑在办法 unlinkFirst 中
public E remove() {return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> 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<E> node(int index) {// assert isElementIndex(index);
if (index < (size >> 1)) {
// index 小于长度的一半时，应用头节点向后遍历查找数据
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// index 大于等于长度的一半时，应用尾节点向前遍历查找数据
Node<E> 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<K,V>[] tab; Node<K,V> p; int n, i;
// table 是一个 Node<K,V> 数组，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<K,V> 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<K,V>)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 = 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<K,V>[] resize() {Node<K,V>[] 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 原来数组内容拷贝到新数组
if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {// 不便查看，省略代码}
}
return newTab;
}treeifyBin 办法，要进行树化前会先判断 table 长度：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> 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<K,V> hd = null, tl = null;
do {TreeNode<K,V> 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<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)
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<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 order
Node<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;
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 = 定义好的动态不变对象。
在新增元素时，会先依据 key 的 hash 值来找到数组索引，找到数组索引对应的那条链表，如果为 null 间接增加元素，如果不为 null 须要判断新增元素 key 和以前的是否是同一个对象或者完全相同。如果雷同，则不增加，否则将元素追加到这条链表的开端。
当一条链表长度 >=8 并且数组长度大于 64 时，会将这个链表转为红黑树。
触发扩容：第一次新增元素，会初始化 table 数组，容量会变为 16，临界值变为 12（16 * 0.75）。在整个 hashMap 中元素个数大于临界值时会进行扩容，每次扩容为原来的 2 倍。
LinkedHashSet
特点
继承 HashSet，有序不反复。
源码剖析 (Java 11)
底层应用的 LinkedHashMap，他的底层数据结构是 哈希表 + 双向链表。
每次创立新节点时，会保护这个双向链表：
// 创立新节点的办法
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}LinkedHashMap.Entry 是这里的节点类，它继承于 HashMap 的外部类 Node，然而每个节点领有前后指针（before、after）。
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);
}
}
在 newNode 中调用 linkNodeLast 来保护每个节点组成的双向链表：
// 双向链表头节点
transient LinkedHashMap.Entry<K,V> head;
// 双向链表尾节点
transient LinkedHashMap.Entry<K,V> tail;
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> 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<K,V> t = root;
if (t == null) {
// 第一个节点时,compare 的作用只是为了检测 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
// key 在对应的比拟规定下，如果雷同，会被批改。return t.setValue(value);
} while (t != null);
}
else {
// 应用 key 类型的结构器比拟
if (key == null)
// 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;
}总结
- 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<String, String> hashMap = new HashMap<>();
hashMap.put("zhangsan", "aaa");
hashMap.put("lisi", "bbb");
// 遍历 key-value
// 加强 for 循环
System.out.println("加强 for 循环");
Set<String> keySet = hashMap.keySet();
for (String key : keySet) {System.out.println(key + "-" + hashMap.get(key));
}
// 迭代器
System.out.println("迭代器");
Iterator<String> iterator = keySet.iterator();
while (iterator.hasNext()) {String key = iterator.next();
System.out.println(key + "-" + hashMap.get(key));
}
// entry
System.out.println("entry 加强 for 循环");
Set<Map.Entry<String, String>> entrySet = hashMap.entrySet();
for (Map.Entry<String, String> entry : entrySet) {System.out.println(entry.getKey() + "-" + entry.getValue());
}
System.out.println("entry 迭代器");
Iterator<Map.Entry<String, String>> entryIterator = entrySet.iterator();
while (entryIterator.hasNext()) {Map.Entry<String, String> entry = entryIterator.next();
System.out.println(entry.getKey() + "-" + entry.getValue());
}
// 遍历 value
// 加强 for 循环
Collection<String> values = hashMap.values();
for (String value : values) {System.out.println(value);
}
Iterator<String> valueIterators = values.iterator();
while (valueIterators.hasNext()) {String value = 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 == 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<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = 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<K,V> e = (Entry<K,V>) 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）。