活动地址:CSDN21天学习挑战赛
此类实现 Set 接口,由哈希表(实际上是一个 HashMap 实例)支持。它不保证 set 的迭代顺序;特别是它不保证该顺序恒久不变。此类允许使用 null 元素。
HashSet hashSet=new HashSet();
展示源码
/**
* Constructs a new, empty set; the backing HashMap instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
add方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
本质上是将数据保存在HashMap中,key就是我们添加的内容,value就是我们定义的一个Obj对象
底层数据结构是 哈希表,HashSet的本质是一个"没有重复元素"的集合,它是通过HashMap实现的。HashSet中含有一个HashMap类型的成员变量map,在HashSet中操作函数,实际上都是通过map实现的。所以了解了HashMap就了解了HashSet。
基于TreeMap的 NavigableSet实现。使用元素的自然顺序对元素进行排序,或者根据创建 set 时提供的 Comparator进行排序,具体取决于使用的构造方法。
TreeSet ts=new TreeSet();
展示源码
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a set backed by the specified navigable map.
*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
* Constructs a new, empty tree set, sorted according to the
* natural ordering of its elements. All elements inserted into
* the set must implement the {@link Comparable} interface.
* Furthermore, all such elements must be mutually
* comparable: {@code e1.compareTo(e2)} must not throw a
* {@code ClassCastException} for any elements {@code e1} and
* {@code e2} in the set. If the user attempts to add an element
* to the set that violates this constraint (for example, the user
* attempts to add a string element to a set whose elements are
* integers), the {@code add} call will throw a
* {@code ClassCastException}.
*/
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
本质是将数据保存在TreeMap中,key是我们添加的内容,value是定义的一个Object对象。
因此,HashSet和TreeSet的学习重点在于HashMap和TreeMap。
LinkedList是通过双向链表去实现的,他的数据结构具有双向链表结构的优缺点
既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。
它包含一个非常重要的私有的静态内部类:Node。
private static class Node<E> {
E item; // 存储的元素
Node<E> next; // 下一个Node节点
Node<E> prev; // 前一个Node节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
transient int size = 0; // 链表的长度
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first; // 链表的首节点
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last; // 链表的尾节点
LinkedList linkedlist = new LinkedList();
/**
* Constructs an empty list.
* 默认为空
*/
public LinkedList() {
}
从头部添加
linkedlist.push(1);
源码
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
public void push(E e) {
addFirst(e);
}
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Links e as first element.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
从尾部添加
linkedlist.add(2);
源码
/**
* Appends the specified element to the end of this list.
*
* This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
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++;
}
由于LinkedList实现了List的接口,所有必然具备List的特性.接下来看List接口中定义的一个方法get(int index)和set(int index,E e);
public E get(int index) {
checkElementIndex(index); // 检查下标是否合法
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 判断index是否小于size的一半
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;
}
}
本质还是遍历链表中的数据
public E set(int index, E element) {
checkElementIndex(index); // 检查下标是否越界
Node<E> x = node(index); // 根据下标获取对应的Node节点
E oldVal = x.item; // 记录原来的值
x.item = element; // 修改
return oldVal; // 返回原来的值
}
Map集合的特点
一个不包含重复元素的 collection。更确切地讲,set 不包含满足 e1.equals(e2)
的元素对
e1
和 e2
,并且最多包含一个 null 元素
TreeMap底层的实现原理是红黑树,所以要搞清楚TreeMap的底层原理,前提条件就必须要搞清楚红黑树的原理
类图结构
定义TreeMap 无参构造
TreeMap map = new TreeMap();
源码
public TreeMap() {
comparator = null;
}
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
/**
* The comparator used to maintain order in this tree map, or
* null if it uses the natural ordering of its keys.
*
* @serial
*/
private final Comparator<? super K> comparator;// 比较器
private transient Entry<K,V> root;// 根节点
/**
* The number of entries in the tree
*/
private transient int size = 0;// map中元素的个数
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;// 记录修改的次数
进入Entry内部类
static final class Entry<K,V> implements Map.Entry<K,V> {
K key; // key
V value; // value
Entry<K,V> left; // 左子树
Entry<K,V> right; // 右子树
Entry<K,V> parent; // 父节点
boolean color = BLACK; // 颜色标志
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
// 重写了equals方法 必须是key和value都相等
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash; // 异或
}
public String toString() {
return key + "=" + value;
}
}
以put方法为例来介绍TreeMap中红黑树的操作
TreeMap map = new TreeMap();
map.put("wm","666");
map.put("wmm","777");
第一次添加
public V put(K key, V value) {
// 获取根节点 将root赋值给局部变量 初始为Null
Entry<K,V> t = root;
if (t == null) {
// 初始操作
// 检查key是否为null
compare(key, key); // type (and possibly null) check
// 将要添加的key、value封装为一个Entry对象 并赋值给root
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null; //返回null
}
第二次添加 root不为空
public V put(K key, V value) {
// 获取根节点 将root赋值给局部变量 初始为Null
Entry<K,V> t = root;
if (t == null) {
// 初始操作
// 检查key是否为null
compare(key, key); // type (and possibly null) check
// 对根节点初始化
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null; //返回null
}
int cmp;
Entry<K,V> parent;//父节点
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;//获取比较器
if (cpr != null) { // 如果比较器不为null
do { // 循环 将root赋值给parent
parent = t;
// 比较父节点和插入节点的值得大小
cmp = cpr.compare(key, t.key);
if (cmp < 0) // 插入节点比父节点小
t = t.left; // 把父节点左节点赋给t
else if (cmp > 0) // 插入的值比父节点大
t = t.right; // 把父节点右侧的节点赋给t
else // 如果相等,直接替换,并返回原来的值
return t.setValue(value);
} while (t != null);// 一直循环直到找到合适的插入位置
}
else {
if (key == null)
throw new NullPointerException();
// 比较器为空 就创建一个 通过ASCII码值进行比较
@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);
}
// 将要添加的 key value 封装为一个Entry 对象
// t 就是我们要插入节点的父节点 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;
}
红黑树平衡 fixAfterInsertion(e);
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
// 设置创建的初始节点为红色节点
x.color = RED;
// 循环的条件 添加的节点不为空 不是root节点 父节点是红色
while (x != null && x != root && x.parent.color == RED) {
// 判断父节点是否是祖父节点的左节点
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// 获取父节点的兄弟节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 父节点的兄弟节点是红色
if (colorOf(y) == RED) {
// 设置父节点为黑色
setColor(parentOf(x), BLACK);
setColor(y, BLACK); // 设置父节点的兄弟节点也为黑色
setColor(parentOf(parentOf(x)), RED); // 设置祖父节点为红色
// 把祖父节点赋给x 因为祖父节点是红色,当前新插入的节点 下一次循环向上再检查
x = parentOf(parentOf(x));
} else {
// 父节点的兄弟节点是黑色
// 如果插入节点是父节点的右侧节点
if (x == rightOf(parentOf(x))) {
// 插入节点指向父节点
x = parentOf(x);
// 以父节点为插入节点左旋
rotateLeft(x);
}
// 设置插入节点的父节点为黑色
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED); // 设置祖父节点为红色
rotateRight(parentOf(parentOf(x))); //以祖父节点为插入节点来做右旋
}
} else {// 判断父节点是否是 祖父节点的左节点 不是
// 获取父节点的兄弟节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) { // 兄弟节点为红色
// 变色即可
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
// 右左 先右旋
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK; // 根节点必须为黑色
}
左旋源码
/** From CLR */
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋源码
/** From CLR */
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
Jdk1.7及以前是采用数组+链表
Jdk1.8之后
采用数组+链表 或者 数组+红黑树方式进行元素的存储
存储在hashMap集合中的元素都将是一个Map.Entry的内部接口的实现
当数组的下标位是链表时,此时存储在该下标位置的内容将是Map.Entry的一个实现Node内部类对象
当数组的下标位是红黑树时,此时存储在该下标位置的内容将是Map.Entry的一个实现TreeNode内部类对象
比较重要的属性
/**
* The default initial capacity - MUST be a power of two.
* 默认HashMap数组的容量 初始是16 必须是2的幂次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30. HashMap数组的最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
* 默认扩容的平衡因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
* 链表转红黑树的 临界值(阈值) 当链表长度大于等于8时转换
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
* 红黑树转链表的临界值 删除红黑树节点 当节点小于等于6时
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
* 链表转红黑树的另一个条件是 数组长度要大于64
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
* HashMap中的数组结构
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
* HashMap中的元素个数
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* 对HashMap操作的次数
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* 扩容的临界值
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
/**
* The load factor for the hash table.
* @serial
* 实际扩容值
*/
final float loadFactor;
put方法分析
HashMap mapl = new HashMap();
mapl.put("wm","666");
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash(key) :获取key对应的hash值
static final int hash(Object key) {
int h;
// key.hashCode() 长度32
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要右移16位,大概是为了一下原因
首先,假设有一种情况,对象 A 的 hashCode 为 1000010001110001000001111000000,对象 B 的 hashCode 为 0111011100111000101000010100000。
如果数组长度是16,也就是 15 与运算这两个数, 你会发现结果都是0。这样的散列结果太让人失望了。很明显不是一个好的散列算法。
但是如果我们将 hashCode 值右移 16 位,也就是取 int 类型的一半,刚好将该二进制数对半切开。并且使用位异或运算(如果两个数对应的位置相反,则结果为1,反之为0),这样的话,就能避免我们上面的情况的发生。
总的来说,使用位移 16 位和 异或 就是防止这种极端情况。但是,该方法在一些极端情况下还是有问题,比如:10000000000000000000000000 和 1000000000100000000000000 这两个数,如果数组长度是16,那么即使右移16位,在异或,hash 值还是会重复。但是为了性能,对这种极端情况,JDK 的作者选择了性能。毕竟这是少数情况,为了这种情况去增加 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)
// 初始的情况下 进入resize方法查看
// resize() 初始数组 扩容 初始的时候 获取了一个容量为16的数组
n = (tab = resize()).length;//n 数组长度
// 确定新添加的key在数组中的位置[下标] n = 16
//例如 100001000111000
// 1111
// 1000 = 8
if ((p = tab[i = (n - 1) & hash]) == null)
//通过hash值找到的数组下标 里面没有内容就直接赋值
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&//p.hash == hash hash值相同
//key也相同
((k = p.key) == key || (key != null && key.equals(k))))
//插入的值key 和 数组当前位置的 key是同一个 那么直接修改里面的内容
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;
}
}
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;
}
resize方法 第一次执行时 创建了一个 Node[16] 扩容的临界值(12)
final Node<K,V>[] resize() {
// 记录table table=null
Node<K,V>[] oldTab = table;
// 记录原来 数组的长度 初始为0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容临界值 默认值为0
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)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始执行此处
newCap = DEFAULT_INITIAL_CAPACITY; // 16
// 16 * 0.75 = 12 扩容的临界值 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}//更新了 扩容的临界值12
threshold = newThr;
// 实例化了一个容量为16的数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;//更新了table
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;
}
确定put进来的key在数组中的位置
if ((p = tab[i = (n - 1) & hash]) == null)
HashMap的容量为什么是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)
// 初始的情况下 进入resize方法查看
n = (tab = resize()).length;
// 确定新添加的key在数组中的位置 n = 16
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果数组的这个位置是null的就直接插入进去
tab[i] = newNode(hash, key, value, null);
else {
// 如果这个数组的位置不为null
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 插入的信息和这个位置的数据是同一个key 那么久替换
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;
}
}
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;
}
treeifyBin(tab, hash);
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果数组的长度没有达到64 那么就尝试扩容 并不会转换为红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
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);
}
}
动态扩容
final Node<K,V>[] resize() {
// 记录table eg[1,2,3,4,5,6,7,8,9,10,11,,,,]
Node<K,V>[] oldTab = table;
// 记录原来 数组的长度 16
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 扩容临界值12
int oldThr = threshold;
// 新的数组容量 和扩容临界值
int newCap, newThr = 0;
if (oldCap > 0) { // 16
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 原来的容量扩大一倍 扩容临界值也扩大一倍24
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
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 初始执行此处
newCap = DEFAULT_INITIAL_CAPACITY; // 16
// 16 * 0.75 = 12 扩容的临界值 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
// 实例化了一个容量为16的数组
@SuppressWarnings({"rawtypes","unchecked"})
创建的数组长度是32
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和TreeSet的源码
HashSet
往Set中添加数据,本质上就是往Map集合中添加数据
TreeSet