Java集合源码探索
使用的JDK11版本
全文较长,建议选择性查看
图文较少,注释较多,建议在电脑上打开idea配套查看
写的比较详细,可以针对某一点(例如HashSet的Add方法)来查看.
Collection接口结构图
List接口
我们可以看到常用的List接口实现类有这三种
可以用一张表来描述它们之间的差异
| 实现类型 | 底层数据结构 | 线程安全性 | 执行效率 | 扩容规则 |
|---|---|---|---|---|
| ArrayList | 数组 | 不安全 | 查找快增删慢 | 首次默认10,后序1.5倍 |
| LinkedList | 双向链表 | 不安全 | 查找慢增删快 | 双向链表无需扩容 |
| Vector | 数组 | 安全 | 比ArrayList效率低 | 构造方法指定10元素,后序2倍扩容 |
ArrayList
一些属性
//数组大小默认值
private static final int DEFAULT_CAPACITY = 10;
//空Object数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//空Object数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList底层存储数据的数组
transient Object[] elementData;
//数组内元素的个数
private int size;
构造方法
//无参构造方法，创建的时候把空数组赋值给elementData
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//带参数（大小）的构造函数
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) { //构造一个固定长度的底层数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { //没人会传入一个0吧。。。。
this.elementData = EMPTY_ELEMENTDATA;
} else { //不能传入负数
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//带参数（集合）的构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //把构造函数中的集合赋值给当前List的数组
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
//把传入的数组copy到当前的底层数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果传入的集合是空的，还是赋值一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
add方法-扩容机制
1.
public boolean add(E e) {
//当前这个集合修改的次数;目前没看出来作用
modCount++;
add(e, elementData, size);
return true;
}
2.
private void add(E e, Object[] elementData, int s) {
//这个条件成立的时间是 第一次add 或者 当前的容量已经满了 不足以再add元素了
if (s == elementData.length)
//扩容方法
elementData = grow();
elementData[s] = e;
size = s + 1;
}
3.
private Object[] grow() {
//传入的参数是最小需要空间的个数，也就是说我要再放一个，你最低得给我再加一个位置
return grow(size + 1);
}
4.
private Object[] grow(int minCapacity) {
//把当前的数组copy到一个新的数组中，容量在newCapacity方法内
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
5.
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length;
//在这里计算要扩容的数量
//old右移一位就相当于/2 右移两位就相当于 /2/2 左移相反是*2
//相当于扩大了1.5倍，当然第一次进来的话 old是0 0位移还是0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//这个条件只有第一次Add的时候满足 可能还有其它情况 我还没想出来...
if (newCapacity - minCapacity <= 0) {
//如果是第一次 nameelementData肯定是空的 满足这个条件
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
//会返回默认大小 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
//看新扩容的值是否溢出了，溢出的话 就调用hugeCapacity方法根据情况 赋值int的最大值 或者 -8
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
6.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE)
? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;
}
最后返回到第四步 copy一个数组，扩容容量
然后返回第二步 添加数据，size+1
和jdk8还是有点不一样的。
add(int index, E element)-在指定位置插入数据
public void add(int index, E element) {
//校验数组是否越界
rangeCheckForAdd(index);
//修改次数+1
modCount++;
//临时变量 数组元素个数
final int s;
//临时变量 数组
Object[] elementData;
//判断是否扩容，看当前数组的元素数量是不是和当前数组的长度一样
if ((s = size) == (elementData = this.elementData).length)
//扩容机制和上边是一致的
elementData = grow();
//我们看下这个方法的官方参数解释
//Object src : 原数组
//int srcPos : 从元数据的起始位置开始
//Object dest : 目标数组
//int destPos : 目标数组的开始起始位置
//int length : 要copy的数组的长度
//这个方法是个本地方法，它可以根据要copy的长度 把原数组的某段元素拷贝到目标数组内
//在下边我会写一个demo验证一下
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
//替换掉原数组index位置的元素
elementData[index] = element;
//长度+1
size = s + 1;
}
//验证System.arraycopy方法
@Test
public void testArraycopy(){
String[] arr = new String[10];
arr[0] = "jack";
arr[1] = "tom";
arr[2] = "lucy";
System.out.println(Arrays.toString(arr));
System.arraycopy(arr,1,arr,2,2);
System.out.println(Arrays.toString(arr));
//[jack, tom, lucy, null, null, null, null, null, null, null]
//[jack, tom, tom, lucy, null, null, null, null, null, null]
//和我预想的结果是一样的。先把数组从index坐标 向后平移一位 然后替换掉index坐标的值
}
LinkedList
一些属性
//数组元素个数
transient int size = 0;
//头结点
transient Node<E> first;
//尾节点
transient Node<E> last;
//内部节点类
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;
}
}
构造方法
//空的..
public LinkedList() {
}
//调用无参构造方法 之后 调用addAll方法 后边看下这个方法
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
add(E e)
1.
public boolean add(E e) {
linkLast(e);
return true;
}
2.
//第一次add
void linkLast(E e) {
//把当前的尾节点指向l 因为last也是null 所以 l = last = null
final Node<E> l = last;
//新建一个节点，前节点指针指到l 后向指针指到 null 类似这样 null <- newNode -> null
final Node<E> newNode = new Node<>(l, e, null);
//然后让newNode又指向了last 类似这样 null <- last -> null
last = newNode;
//第一次的add的话 l肯定是空的 因为last是空的
if (l == null)
//这样的话 first也有值了
first = newNode;
else
l.next = newNode;
//元素+1
size++;
//修改次数+1
modCount++;
}
//第二次add
void linkLast(E e) {
//把当前的尾节点指向临时节点 l
final Node<E> l = last;
//新建一个节点，前节点指针指到l 后向指针指到 null 类似这样 l <- newNode -> null
final Node<E> newNode = new Node<>(l, e, null);
//新的节点就变成了尾节点
last = newNode;
//除了第一次add,其它时候这个l永不为null
if (l == null)
first = newNode;
else
//l后向指针指向了新节点 类似 l ->newNode
l.next = newNode;
//元素+1
size++;
//修改次数+1
modCount++;
}
简单来说，就是第一次添加的时候，当前元素即使头结点又是尾结点，后边继续添加的时候，总是丢到链表的尾部
根据索引来查找node节点
Node<E> node(int 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;
}
}
remove方法
public E remove(int index) {
checkElementIndex(index);
//获取对应索引的节点~
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果删除的是头结点 只需要让它的next节点指向头结点就ok
if (prev == null) {
first = next;
} else {
//让当前节点的pre节点的next节点直接指向自己的next节点。。有点绕，意思就是跳过当前的这个节点
prev.next = next;
//把当前的后节点指为null
x.prev = null;
}
//如果删除的是尾节点 只需要让它的pre节点指向尾节点就ok
if (next == null) {
last = prev;
} else {
//让自己的next节点的pre节点指向自己的pre节点
next.prev = prev;
//让自己的next节点指向空 供gc使用
x.next = null;
}
//情况当前的元素
x.item = null;
//元素数量减1
size--;
//集合修改次数加1
modCount++;
return element;
}
链表的方法其实还是比较简单的。
Vector
一些属性
//底层数组
protected Object[] elementData;
//元素个数
protected int elementCount;
//指定扩容数量
protected int capacityIncrement;
构造方法
//无参构造，看来它又调用自己的有参构造器了
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;
}
根据构造参数来看，无论调用的是哪个，都会初始化一个固定长度为10的底层数组
add方法-扩容机制
1.
//可以看到方法都是加锁的。证明是线程安全的
public synchronized boolean add(E e) {
//修改次数+1
modCount++;
add(e, elementData, elementCount);
return true;
}
2.
private void add(E e, Object[] elementData, int s) {
//如果当前数组的元素个数和数组大小一样，就需要扩容了
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
elementCount = s + 1;
}
3.
private Object[] grow() {
//元素当前数量+1代表最小需要空间个数
return grow(elementCount + 1);
}
4.
private Object[] grow(int minCapacity) {
//newCapacity方法计算要扩容的数量大小
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
5.
private int newCapacity(int minCapacity) {
//当前数组的长度
int oldCapacity = elementData.length;
//capacityIncrement这个参数如果没有设置就是0就默认扩容2倍否则根据设置的数量决定
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//除非在构造方法创建时指定初始化数量为0的元素 才会满足这个条件...
if (newCapacity - minCapacity <= 0) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
//返回扩容数量，如果溢出，则走hugeCapacity方法，这里就不看了~
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
然后返回第4步把原来的数组通过copy的方式扩容到新长度
之后回到第2步添加元素
ArrayList和Vector的扩容机制比较
1.默认情况下，ArrayList首次add必扩容，Vector默认add第11个元素才扩容
2.ArrayList扩容每次1.5倍，Vector可以指定扩容大小，或者默认2倍、
Set接口
HashSet
一些属性
//hashSet的底层是HashMap
private transient HashMap<E,Object> map;
//占位的对象....
private static final Object PRESENT = new Object();
构造函数
//new了一个hashMap
public HashSet() {
map = new HashMap<>();
}
//指定hashMap的大小
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//这个loadFactor在Hashmap的时候会具体说，主要是扩容时候的一个参数
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
//全都是调用HashMap的构造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
那在这里一起说下HashMap的构造方法吧
//空参构造方法
public HashMap() {
//赋值加载因子 loadFactor = 0.75
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定map底层数组大小构造方法
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指定map底层数组大小 和加载因子构造方法。
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;
//这个threshold要说一下，这个是扩容的阈值，这个参数后边有说到它的作用
this.threshold = tableSizeFor(initialCapacity);
}
//看一下这个方法
注释说是返回大于输入参数且最近的2的整数次幂的数。比如10，则返回16
static final int tableSizeFor(int cap) {
//里边就不看了。
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
大概就是这些方法了~
Hash底层是HashMap 让我们顺便看一下hashMap的源码吧~
看之前要先弄懂hashMap底层是什么样的数据结构 网上找了一张图~侵删
hashMap底层是一个数组链表，Node[] table, 通常叫它哈希表,
一个坑里有一条链表，当满足一定条件（后边会说到） 链表就会变成一颗树
add-hashMap(put方法)
1.
public boolean add(E e) {
调用的是hashMap的put方法，value是 占位的空Object对象
return map.put(e, PRESENT)==null;
}
2.
public V put(K key, V value) {
先对key进行了hash扰动~
return putVal(hash(key), key, value, false, true);
}
3.这个方法就是最大限度能保证key的hash值不一样。异或加无符号右移
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4.接下来就是核心方法了，我们这里分两种情况来看，第一种先看首次添加的时候出现的情况
### 首次add时
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//这些是一堆临时变量
Node<K,V>[] tab; Node<K,V> p; int n, i;
//第一次add时，可以知道table是null的
if ((tab = table) == null || (n = tab.length) == 0)
//在这里进行一次扩容 resize() 记录下n为扩容后的数组长度
n = (tab = resize()).length;
//这一行是判断经过上边扰动后的下标对应的数组元素 是否已经有值了 第一次肯定是没有值的
if ((p = tab[i = (n - 1) & hash]) == null)
//创建一个节点存储下来
tab[i] = newNode(hash, key, value, null);
else {
//由于第一次并不涉及此条件，所以我这里就没贴上来
...
}
//记录集合修改次数
++modCount;
//这个threshold在这里出现了，就是一个阈值，来决定是否要进行扩容
//一会看扩容方法的时候会知道，第一次初始化的时候数组大小是16，threshold = 16*0.75 = 12
//当你元素已经放了13个之后，虽然没有满（16）,但是满足这个条件了 就需要扩容了~
if (++size > threshold)
resize();
//方法是空的
afterNodeInsertion(evict);
return null;
}
//上边是首次add的时候，扩容的机制。其实很简单，一系列条件都不满足，创建一个node放数组里就很好了
//接下来看扩容方法，有点长，还是按照首次和其它情况来梳理，
final Node<K,V>[] resize() {
//table是null的
Node<K,V>[] oldTab = table;
//0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//0
int oldThr = threshold;
//0
int newCap, newThr = 0;
if (oldCap > 0) {
...不满足
}
else if (oldThr > 0) // initial capacity was placed in threshold
...不满足
else {
//在这里设置默认值，newCap = 16 newThr = 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
...不满足
}
//在这里给阈值赋为12
threshold = newThr;
//创建指定大小16的Node数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
...//这块首次不满足条件，先省略掉..
}
return newTab;
}
首次扩容是不是很简单,只是创建了一个默认值16的Node数组 .
### 非首次add，但是hash相等时
//接下来按照非首次add方法
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;
//这里其实还分两种情况,如果第二次add的时候 算出来的hash下标对应的元素还是空的那就直接创建元素放进去就好了，但是有种情况是，算出来的hash相等了~但是值确实是不同。这时候就会走下边的分支。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//当hash相等时 走这个分支
Node<K,V> e; K k;
//在这里，判断hash相等并且 key（我们要存储的对象）也是相等（== or equals）的时候，表示兄弟 你放的两个元素一模一样~ 把当前的变量指向到临时变量e上 下边的分支就不用看.
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 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//到这里，如果你存储的valu是 null, name直接返回就是null，
if (e != null) { // existing mapping for key
V oldValue = e.value;
//注意看这一句,前边这个条件永远为真, 所以,这个分支一直会进
if (!onlyIfAbsent || oldValue == null)
//这个作用就是替换掉当前节点的value
e.value = value;
afterNodeAccess(e);
//返回oladValue 下边的扩容 修改 都不走了,意思就是 我把你老的元素给你返回，把你心的元素给你放进去了。类似更新的方法。
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
上边就是，非首次add 但是hash相等，会直接set新的值，并返回旧的值
### 非首次add,hash不相等时
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;
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;
//我们继续走到这里,如果hash相等，但是对象却是不同,那么我们就要向里边放新的数据了
//这里有个分支，看你当前是链表还是树，这个后边再说，我们假设现在还是链表
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);
//这个时候就会判断当前这条链要不要变成树 在这里
//这个TREEIFY_THRESHOLD 是固定值8
//那么满足树化的条件就是当binCount=0,put的第2个元素,binCount 1对应put的第3个元素,1对以此类推,当binCount=7时此时put的是第9个元素,而上面的已经说了binCount >=7时调用treeifyBin方法,所以链表长度是要超过8 就会进行树化~
//但是树化的前提，当前数组大小要大于等于64个 在下边会讲到
//所以最终树化的条件就是,当前hash表的长度大于等于64并且当前链表有7个节点
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;
}
}
//这个时候e 是空的,因为最后一个循环 (e = p.next) == null
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//集合修改次数+1
++modCount;
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
return null;
}
//上边说到树化这个方法 可以看到 MIN_TREEIFY_CAPACITY 这个值是64 如果当前hash表小于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();
else if ((e = tab[index = (n - 1) & hash]) != null) {
...
}
}
### 非首次扩容
//我们最后看一下非首次扩容时候的逻辑
final Node<K,V>[] resize() {
//非首次扩容的时候 这个 oldTab 可就不是null了~
Node<K,V>[] oldTab = table;
//把老的hash表长度记录下来
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;
}
//进入这个分支，把老的hash表长度 和阈值都扩容两倍
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
...//不满足条件
else { // zero initial threshold signifies using defaults
...//不满足条件
}
if (newThr == 0) {
...//不满足条件
}
//新的扩容阈值赋值给成员变量
threshold = newThr;
//创建新的扩容后的hash表
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//在这里开始循环老的hash表 把内容都cp过去
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
//如果当前hash表中仅有一个节点并且没有树化，直接挪坑
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;
}
LinkedHashSet
一些属性
//linkedHashSet这个类是继承HashSet的，所以都是用的父类属性
public class LinkedHashSet<E>
extends HashSet<E>
构造方法
//无参构造
public LinkedHashSet() {
super(16, .75f, true);
}
//带初始化长度的构造方法
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
//带初始化长度和加载因子的构造方法
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
//我们可以看到，这三个构造方法，统一都是调用父类的一个构造方法
//就是HashSet的这个方法，可以看到 底层用的是LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//这个LinkedHashMap又是啥？ LinkedHashMap继承的是HashMap 绕了一圈下来，还是HashMap
我们具体看一下类图就明白了~
为什么LinkedHashSet（LinkedHashMap）是有序的？
在这之前，我们已经知道Map底层是如何put进去数据的,
那这个有序我们是如何理解的呢？有序是指 我们加进去元素的顺序 要和 我们取出来元素的顺序保持一致！
我们看一下LinkedHashMap内部的一个类
//这个类很重要,这个类继承了Node类，我们知道Node是链表类型的，它继承了链表的特性，可以指向前也可以指向后，Entry又扩充了两个属性 叫befor，after，什么意思呢 就是双向，有顺序，befor存储前边的节点、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);
}
}
这个Entry大概长这样
黄色的就是一个一个Entry，它们的befor可以指向任意一个Entry（Node） after也是这样。
Add方法
由于LinkedHashSet 底层用的是LinkedHashMap
LinkedHashMap又继承了HashMap
所以add方法用的是父类的add方法
前边我们分析过了HashMap的add方法,但是由于Java的多态机制,我们再重新看一下几个重要的方法
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;
if ((p = tab[i = (n - 1) & hash]) == null)
//注意这个newNode方法,这里走的是LinkedHashMap的nweNode方法
tab[i] = newNode(hash, key, value, null);
else {
...//不相关
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2.
//我们先看一下，LinkedHashMap在newNode的时候发生了什么
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//它先创建了一个Entry类,也就是双向链表类型的
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
//这个方法很重要
linkNodeLast(p);
return p;
}
3.
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
//因为要添加新的node 所以先把尾部赋予临时变量last
LinkedHashMap.Entry<K,V> last = tail;
//把要新增的p节点放到链表的尾部tail
tail = p;
//如果是第一次 name头部节点肯定是null的
if (last == null)
//让头部节点也指向这个新创建的节点
head = p;
else {
//如果非首次的话,就让当前创建的节点前向指到临时变量last
p.before = last;
//当然要互相指一下，
last.after = p;
}
}
上边这个方法就完成了新建节点的时候，双向指定的问题,那么无论后边有多少个node添加进来,都能够保证是有顺序的.
这样我们大概就知道LinkedList为什么是有序的了。其实扩容还是走的hashMap的方法,只不过在每次add的时候多了一步维护entrySet的操作,使得整个链表是有序的.
Map接口结构图
| 实现类型 | 底层数据结构 | 线程安全性 | 使用场景 | 扩容规则 |
|---|---|---|---|---|
| HashMap | 数组+单向链表+红黑树 | 不安全 | 无序 | 首次默认16,后序以2倍扩容 |
| HashTable | 数组+单向链表 | 安全 | 无序 | 首次默认11,后序以2倍+1扩容 |
| TreeMap | 二叉树 | 不安全 | 可以排序 | 树无需扩容 |
HashMap
HashMap在前边分析HashSet的时候其实已经看过了,因为HashSet底层用的就是HashMap.所以在这里就不过了~ 可以看前边分析HashSet的过程
HashTable
一些属性
table表,是个数组, 里边存放单向链表
private transient Entry<?,?>[] table;
//数组的实际元素个数
private transient int count;
//table扩容阈值
private int threshold;
//table扩容因子
private float loadFactor;
构造方法
//无参构造方法
public Hashtable() {
//调用指定大小和指定加载因子构造方法
this(11, 0.75f);
}
//指定数组大小构造方法
public Hashtable(int initialCapacity) {
//调用指定大小和指定加载因子构造方法
this(initialCapacity, 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);
//无论如何初始化的时候 数组最小大小为1
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry<?,?>[initialCapacity];
//计算扩容阈值, 初始化大小*加载因子
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
put方法
//可以看到hashtabl每个方法都有 synchronized关键词,表示线程安全
public synchronized V put(K key, V value) {
// 看来 hashtabl的value值不允许为null
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//计算hash值
int index = (hash & 0x7FFFFFFF) % tab.length;
//取出对应hash索引位置的元素
Entry<K,V> entry = (Entry<K,V>)tab[index];
//如果取出来不为null,那就遍历这个链表,看有没有相同的,如果有那就替换掉value返回oldValue,如果没有,后边再说
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
//开始add元素
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
//看是否到达了扩容的临界值
if (count >= threshold) {
//扩容方法
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
//这里需要注意一下,上个方法我们说过,循环到最后发现没有相同的元素怎么办,hashtable是把新添加的元素当成头结点,指向原来的元素...这里和hashmap是不一样的
Entry<K,V> e = (Entry<K,V>) tab[index];
//把新添加的元素指向原来的头结点
tab[index] = new Entry<>(hash, key, value, e);
count++;
modCount++;
}
扩容方法
protected void rehash() {
//取出当前table的长度
int oldCapacity = table.length;
//创建临时变量保存当前hash表
Entry<?,?>[] oldMap = table;
//计算新的table长度 2倍+1
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;
}
//创建新的hash表
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
//计算新的扩容阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
//把老的hash表指向新的hash表
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;
}
}
}
所以看起来HashTable和HashMap还是有些区别的. 最大的区别就是线程的安全性了.
TreeMap
TreeMap最大的特点就是可以对Key进行排序, TreeSet底层用的也是TreeMap,所以这里只对TreeMap源码进行一些研究
一些属性
//这个比较器就是treeMap可以进行排序的秘密,后边会讲
private final Comparator<? super K> comparator;
//树的根节点
private transient Entry<K,V> root;
构造方法
//无参构造
public TreeMap() {
//不指定排序方法
comparator = null;
}
//指定排序方法构造器
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
put方法
public V put(K key, V value) {
//获取根节点 首次肯定是null的
Entry<K,V> t = root;
if (t == null) {
//这个方法我刚开始没看懂.搜索了一下才理解,这个是判断当你put的键为"null"时,你有没有实现排序方法,如果没有实现 则就会抛出Null指针异常
//我觉得它的意思可能是,null是一个比较特殊的值,如果你要排序呢,那就要实现排序器的时候为"null"值定义好规则.
compare(key, key); // type (and possibly null) check
//初始化root节点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
//直接return掉.添加完成
return null;
}
//非首次put 才会走下边
//临时变量 存放比较结果
int cmp;
Entry<K,V> parent;
这个cpr 是 初始化时候赋值的比较器
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掉
return t.setValue(value);
} while (t != null);
}
else {
//在这里我们可以看到,如果没有实现比较器对"null"做处理,那么就会抛出空指针异常
if (key == null)
throw new NullPointerException();
//这里会使用key的数据类型默认实现的比较器来比较
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);
}
//比较完毕之后,这个parent就是树底的某个节点
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;
}
treeMap的排序如何实现
前边我们看treeMap的构造方法 和put方法的时候 可以看到是有一个比较器来决定排序的规则,那么这个排序器是什么东西呢?
//我们可以在创建TreeMap的时候创建一个匿名内部类来决定排序的规则
TreeMap treeMap = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return 0;
}
});
//例如我们要根据Dog类的age属性来排序 那么我们可以这么写
TreeMap treeMap = new TreeMap((o1, o2) -> {
Dog dog1 = (Dog)o1;
Dog dog2 = (Dog)o2;
if(dog1.getAge() > dog2.getAge()){
return 1;
}
if(dog1.getAge() < dog2.getAge()){
return -1;
}
return 0;
});
treeMap.put(new Dog("a",11),1);
treeMap.put(new Dog("b",22),1);
treeMap.put(new Dog("c",14),1);
treeMap.put(new Dog("d",55),1);
treeMap.put(new Dog("e",113),1);
treeMap.put(new Dog("f",14),1);
System.out.println(treeMap);
{
Dog{name='a', age=11}=1,
Dog{name='c', age=14}=1,
Dog{name='b', age=22}=1,
Dog{name='d', age=55}=1,
Dog{name='e', age=113}=1}
可以看到我们输出确实是按照age属性的.
总结
到这里为止,我把常用的一些集合实现类的底层数据结构和扩容方法,以及最重要的add\put方法给看了一遍~
感觉难倒不是那么难,关键是,理解底层数据结构之后 在业务场景使用的情况下,可以正确的选择到底要使用哪个集合类.
一步一步写的.可能有错误可能有些东西我也不知道该如何解释毕竟我还是个小白.
里边还有好些东西我不懂,像红黑树这块我还没仔细去了解过~下一步可能就要去深耕一下数据结构这块,如果数据结构不熟悉,看源码应该还是挺困难的…