本文主要以了解各个容器的存储结构为主，对一些具体源码不做过度分析。
一、Map的演变
Map是我们最常用的键值对数据类型，在jdk1.8中对HashMap的底层有了部分的优化，在数据结构层面引入了红黑树以及扩容机制的优化（jdk1.8的ConcurrentHashMap也引入的红黑树）。
1.1 Map有四个最常用的实现
1、HashMap
特点：根据键的hashcode去存储数据，速度快。最多允许有一个键为null，允许多个值为null。
HashMap
2、HashTable
特点：线程安全的，大部分功能与HashMap类似。
HashTable
3、LinkedHashMap
特点：LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，也可以在构造时带参数，按照访问次序排序。
LinkedHashMap
4、TreeMap
特点：TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。 在使用TreeMap时，key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator， 否则会在运行时抛出java.lang.ClassCastException类型的异常。
TreeMap
1.2 HashMap源码分析（jdk1.8）
1.2.1 HashMap的定义
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
继承AbstractMap；
实现Map：定义通用操作；
实现Cloneable：表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；
实现Serializable：实现了序列化。
1.2.2 数据结构
HashMap中有三个主要的数据结构：
1、Node
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;
}
////判断两个node是否相等,若key和value都相等，返回true
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;
}
}
2、TreeNode
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//父节点
TreeNode<K,V> parent;
//左子树
TreeNode<K,V> left;
//右子树
TreeNode<K,V> right;
//上一个同级节点
TreeNode<K,V> prev;
//颜色标记
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
3、Node<K,V>[] table 节点数组（存储位桶）
这个实际是map中的数组，上面存放不同哈希值的节点，当节点相同时，会在该节点向后形成链表。当长度大于临界值时，会转换成红黑树。
盗一幅图，https://blog.csdn.net/v123411739/article/details/78996181
jdk1.8 HashMap结构图
1.2.3 属性
/**
* 默认初始容量16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量1<<30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认的负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 当桶(bucket)上的结点数大于这个值时会转成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 当桶(bucket)上的结点数小于这个值时会转成链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 桶中结构转化为红黑树对应的table的最小大小
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 存储元素的数组，总是2的幂次倍
*/
transient Node<K,V>[] table;
/**
* 存放具体元素的集
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 存放元素的个数，注意这个不等于数组的长度。
*/
transient int size;
/**
* 每次扩容和更改map结构的计数器
*/
transient int modCount;
/**
* 临界值 当实际大小(容量*填充因子)超过临界值时，会进行扩容
*/
int threshold;
/**
* 负载因子
*/
final float loadFactor;
1.2.4 构造函数
1、HashMap(int initialCapacity, float loadFactor)
/**
* 指定大小和负载因子的构造
*
* @param initialCapacity 初始化容量
* @param loadFactor 负载因子
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
//初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
//大于最大容量，使用最大容量
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//负载因子小于等于0或者非整数，抛出异常
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//初始化threshold 大小
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 得到一个大于cap且最接近2的幂次方的数值
* >>>无符号右移，实际是左侧加0，右侧减去一位
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
2、HashMap(int initialCapacity)
/**
* 指定容量的构造，默认负载因子
*
* @param initialCapacity 容量
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3、HashMap()
/**
* 完全默认的构造
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
4、HashMap(Map<? extends K, ? extends V> m)
/**
* 将m中的所有元素添加到HashMap中
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//将m中的所有元素添加到HashMap中
putMapEntries(m, false);
}
/**
* 将m的所有元素存入本HashMap实例中
*
* @param m map
* @param evict false
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取m的大小
int s = m.size();
if (s > 0) {
// 判断table是否已经初始化
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//大于临界值，初始化临界值
if (t > threshold)
threshold = tableSizeFor(t);
}
//大于临界值，扩容
else if (s > threshold)
resize();
// 将m中的所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
1.2.5 主要概念
Hash概念 （引用：https://baike.baidu.com/item/Hash/390310?fr=aladdin）
Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
性质：
所有散列函数都有如下一个基本特性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但不绝对肯定二者一定相等（可能出现哈希碰撞）。输入一些数据计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。
典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。
Hash碰撞
根据hash的特性，两个甚至多个不同输入值，经过hash函数可能产生相同的hash值，这样就发生了冲突，通常称为哈希碰撞。
解决方案：
1）开放寻址法
2）再散列法
3）链地址法(拉链法)，HashMap使用的这种方式。
4）建立一个公共溢出区
二、Set
set集合中的对象不按特定的方式排序，并且没有重复对象，有且只允许一个值为null。
2.1 常用set
1、HashSet：最常用的set。
HashSet
2、TreeSet：支持两种排序方式，自然排序 和定制排序
TreeSet
2.1 HashSet源码解读
通过以下源码发现，HashSet底层实际使用的是map的结构，并且只用key存储数据，有一个常量填充value。
2.1.1 定义
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
继承AbstractSet；
实现Set：定义通用操作；
实现Cloneable：表示可以进行拷贝；
实现Serializable：实现了序列化。
2.1.2 属性
1、HashMap<E,Object> map
/**
* 底层使用了HashMap存储数据。
*/
private transient HashMap<E,Object> map;
2、Object PRESENT
/**
* 用来填充底层数据结构HashMap中的value，因为HashSet只用key存储数据。
*/
private static final Object PRESENT = new Object();
2.1.3 构造函数
1、HashSet()
/**
* 无参构造，底层使用无参map
*/
public HashSet() {
map = new HashMap<>();
}
2、HashSet(Collection<? extends E> c)
/**
* 将c添加到set中
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
3、HashSet(int initialCapacity, float loadFactor)
/**
* 指定容量和负载因子
*
* @param initialCapacity 容量
* @param loadFactor 负载因子
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
4、HashSet(int initialCapacity)
/**
* 指定容量
*
* @param initialCapacity 容量
*/
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
5、HashSet(int initialCapacity, float loadFactor, boolean dummy)
/**
* 特殊的构造，只用于linkedhashSet，指定容量和负载因子
*
* @param initialCapacity 容量
* @param loadFactor 负载因子
* @param dummy 区分是linked还是普通
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
网友评论