Java 汇合类实现原理
1.Iterable 接口
- 定义了迭代汇合的迭代办法
iterator()
forEach() 对 1.8 的 Lambda 表达式提供了反对2. Collection 接口
- 定义了汇合增加的通用办法
int size();
boolean isEmpty();
boolean contains();
boolean add()
boolean addAll()
boolean remove()
removeAll()
Object[] toArray()3.List 接口
- 元素被增加到汇合中当前，取出的时候是依照放入程序。
List能够反复。- 存在下标，能够间接依附下标取值
E get()
E set()
E indexOf()
int lastIndexOf()
ListIterator listIterator()3.1 ArrayList 类
- 底层是一个
Object数组。
transient Object[] elementData; // non-private to simplify nested class access- 初始容量为 10
private static final int DEFAULT_CAPACITY = 10;- 当数组容量不够是主动扩容为以前的 1.5 倍
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);- 数组最大容量为
Integer.MAX_VALUE-8
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;- 线程不平安
3.2.Vector 类（不罕用）
- 底层是一个
Object数组
protected Object[] elementData;- 初始容量为 10
public Vector() {this(10);
}- 数组容量不够的时候主动扩容为原来的一倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);- 数组最大容量为
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;- 线程平安
3.3 LinkedList
- 底层是一个列表
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;- 寄存节点个数
transient int size = 0;- 默认构造方法减少元素实现原理
// 当默认结构的时候, 创立汇合的时候
public LinkedList() {}
// 应用增加办法, 间接将元素增加到开端
public boolean add(E e) {linkLast(e);
return true;
}
// 给尾部增加元素
void linkLast(E e) {
// 获取最初一个元素
final Node<E> l = last;
// 新创建一个界面，其尾结点为 null
final Node<E> newNode = new Node<>(l, e, null);
// 将数组中存储最初一个界面的元素复制
last = newNode;
// 如果此时汇合为 null，则另第一个节点也为该元素，否则就将这个元素的下一个节点设置为该元素节点
if (l == null)
first = newNode;
else
l.next = newNode;
// 节点数量减少
size++;
modCount++;
}
- 指定下标减少元素实现原理
//LinkedList 反对指定的索引出减少节点
public void add(int index, E element) {
// 查看传入的索引是否符合要求
checkPositionIndex(index);
// 如果这个索引是最初一个节点，则间接增加
if (index == size)
linkLast(element);
else
// 否则
linkBefore(element, node(index));
}
// 返回了指定下标的 Node
Node<E> node(int index) {// assert isElementIndex(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;
}
// 将须要插入的元素进行插入
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}实现的思维能够归结为：每一次的插入或者移除，都是通过
node()办法获取指定的Node节点，而后通过linkBefore或者linkLast这些办法来具体进行链表的操作。
4.Set 接口
- 插入无序
- 元素不能反复
- 底层均为
Map汇合实现
4.1 TreeSet 类
先来瞅一眼这个类的继承关系吧
- 实现了
AbstractSet领有了Set的属性和办法 - 实现了
NavigableSet，反对一系列导航办法，能够进行准确查找
分析一下这个类的源码
- 底层实现
TreeMap构造
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* 寄存生成的 TreeMap 汇合
*/
private transient NavigableMap<E,Object> m;
// 作为值增加到 TreeMap 中，即每一个 Entry 的键不同但值雷同，都是一个对象的地址
private static final Object PRESENT = new Object();
public TreeSet() {this(new TreeMap<>());
}
TreeSet(NavigableMap<E,Object> m) {this.m = m;}
// 增加办法
public boolean add(E e) {return m.put(e, PRESENT)==null;
}
- 进行了排序。(在 HashMap 原理进行剖析)
4.2 HashSet 类
- 底层基于
HashMap
// 键
private transient HashMap<E,Object> map;
// 值
private static final Object PRESENT = new Object();
// 结构
public HashSet() {map = new HashMap<>();
}- 无序
- 不可反复
4.3 LinkedHashSet 类
- 底层基于
LinkedHashMap实现，通过 LinkedHashMap 中的办法实现了程序存值。具体实现可看上面的 LinkedHashMap
public LinkedHashSet() {super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}5. Map 类
- 键值对的模式存放数据
- 定义了通用的办法
- 不可反复
int size()
isEmpty();
containsKey()
containsValue()
get()
put()
remove()
keyset()
values()
entrySet()5.1Entry 类
- Map 类的外部类，用来获取所有的键值
5.2HashMap 类
put 的时候，会通过 hash 算法，计算一个 index，这个 index 就是节点数组的下标，此时这个实体就被存储到这个数组中。然而因为这个 hash 算法不能保障任何一个 key 值计算出来的 hash 值均雷同，所以采纳链表的形式，挂载雷同的 index 的实体。在 1.8 当前，当链表的节点数量大于或者等于 8 的时候且数组的容量大于 64 的时候，就会将链表转换为红黑树
- 底层实现：数组 + 链表或者红黑树
// 保留的数组，初始化 16 个
transient Node<K,V>[] table;
// 为 entrySet 和 value 提供一个缓存
transient Set<Map.Entry<K,V>> entrySet;
// 元素的数量
transient int size;
// 初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 数组递增的策略 当 size > capacity*loadFacotor 的时候递增
final float loadFactor;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;
}- 初始容量为 16 的起因
//hash 算法，保障哈希值均匀散布，只有当为 16 的时候才能够最大水平的保障均匀散布
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}put办法
// 创立一个 HashMap 对象，并且设定它的递增策略为 0.75 倍
public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 执行 put 办法
public V put(K key, V value) {
//key 通过 hash 算法计算一个 index
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次进入为 null, 所以执行初始化容器大小
if ((tab = table) == null || (n = tab.length) == 0)
// 此时返回的就是初始化容器当前的大小即 16
n = (tab = resize()).length;
// 计算下标，如果等于 null，间接赋值
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;
// 判断以后节点是否属于红黑树节点
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);
// 如果此时的节点容量为 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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 批改次数
++modCount;
// 查看以后容器的容量是否大于 threshold , 如果大于减少数组容量为原来的一倍
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// 初始化容器大小
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
// 旧容量为 0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 设置以后容器的递增为 0
int newCap, newThr = 0;
// 此时的 oldCap=0 , newThr = 0 间接 else 执行
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
// 初始化容器为默认 16
newCap = DEFAULT_INITIAL_CAPACITY;
// 初始化阙值
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;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 初始化存储容器数组
table = newTab;5.2.1 Hash 数据结构
在 java 中所有的数据结构都能够应用数组和指针即援用来实现。而 Hash 也成散列，就是一个链表加数组实现。
Hash 数据结构具备无序的特色。这里的无序指的是存入程序于取出程序不一样。
什么是 Hash 表的负载因子？负载因子代表了 Hash 表的空间填充度，即负载因子越大其对空间的使用率越高，但这也造成了查问速度慢，而负载因子越小，其查问速度越快，空间填充度越低。所以在应用的过程个别会通过放弃一个均衡。如 HashMap 的负载因子初始化为 0.75. 保障了两者之间的衡量。
Hash 表如何存储数据？Hash 表的每一次存储都会先调用一个 Hash 函数，而这个 Hash 函数最初运算的值就是所存储数据的下标。即当须要查问数据的时候，仅仅只须要调用 Hash 函数进行一次计算就能够得出该数据所在的下标。
5.2.2 HashMap 中的数据结构实现
上面具体解析一下 HashMap 中的 Hash 表的实现
在 HashMap 初始化的时候，首先会给外部的负载因子赋值为 0.75，而后创建对象，留神此时的 HashMap 外部的 Node 数组并没有实例化。
开始 put 数据，此时 put 办法会调用 putVal()办法，但在调用这个 putVal 办法之前，他首先通过 hash 算法计算了一次这个 key 所对应的哈希值，而在 putVal()办法中，又将这个哈希值通过和数组的容量 - 1 进行 & 运算，得出了在这个数组的容量范畴内的一个 index。此时这个 key 所须要存储的 index 正式确定。
确定 key 当前，须要判断该 index 下有没有值，如果有，判断新增的这个元素与现有这个元素是否雷同，如果雷同，替换该值；如果不雷同，遍历这个链表，判断这个链表中是否存在和新增元素雷同的值，如果不存在则间接增加到链表尾部，如果存在，替换该值；当然如果此时链表中节点的个数大于或者等于 8 且数组的容量大于 64 的时候当前就将链表转化为红黑树。
containKey 办法的实现，就是间接通过 hash 办法计算出哈希值，而后通过 & 运算，获取数组下标，判断这个下标是否为该值，如果不是，则进行遍历链表或者红黑树。
containeValue 办法实现，一级一级遍历工夫复杂度仿佛蛮高的
5.3 LinkedHashMap 类
咱们所晓得的 LinkedHashMap 类能够程序的输入用户所输出的数据。上面谈一下他的实现形式
LinkedHashMap 中定义了一个 Entry 类，继承了 HashMap.Node 节点类，额定定义了两个属性，before 和 after，还有最重要的一个办法 newNode，这个办法被 LinkedHashMap 重写，确定了程序性。看到这也就晓得这是双向链表的两个值了。LinkedHashMap 在每一次 put 元素之后都要将该元素的上一个节点设置为之前的那个节点。代码阐明！！！
- 成员属性
// 链表的第一个节点，LinkedHashMap 会保留链表的最初一个节点的属性，以不便进行节点增加
transient LinkedHashMap.Entry<K,V> head;
// 链表的最初一个节点
transient LinkedHashMap.Entry<K,V> tail;- 创建对象了
// 老办法，new 个对象再说（独身狗的呐喊）public LinkedHashMap() {super();
accessOrder = false;
}
// 间接调用 HashMap 的 put 办法
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 在 putVal 中调用了
afterNodeAccess(e);
afterNodeInsertion(evict);
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;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 获取最初一个节点
LinkedHashMap.Entry<K,V> last = tail;
// 将最初一个节点定义为新增的节点
tail = p;
// 如果等于 null 那么阐明之前没有元素
if (last == null)
head = p;
else {
// 如果有，将这个元素的上一个节点定义为之前的最初一个元素
p.before = last;
// 最初一个节点的下一个元素定义为新元素
last.after = p;
}
}// 判断这个新的节点是否为最初一个节点，如果不是挪动该节点到最初
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 查看以后最初一个节点是否为以后新增的元素
if (accessOrder && (last = tail) != e) {
// p 为以后元素，a 为下一个元素，b 为上一个元素
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将 p 的下一个元素定义为 null，切断和之前元素的分割
p.after = null;
// 如果上一个元素为 null，则阐明将该节点的下一个节点赋值为头结点
if (b == null)
head = a;
else
// 否则，将上一个节点的下一个节点定义为 a，到此，这个新的节点曾经被独立进去了
b.after = a;
// 如果此时 a 不为 null
if (a != null)
// 则间接赋值
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
// 永远不起作用 removeEldestEntry 办法永远返回 false
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}5.4 TreeMap 类
- 底层实现：红黑树
- 继承了 NavigableMap 接口，NavigableMap 接口继承了 SortedMap 接口，可反对一系列导航办法即导航操作
- 实现了 Cloneable 接口，可被克隆
- 天然排序
5.4.1TreeMap 创立源码剖析
- TreeMap 定义的字段
// 比拟器
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 节点数量
private transient int size = 0;
// 批改次数
private transient int modCount = 0;
// 红黑色彩判断
private static final boolean RED = false;
private static final boolean BLACK = true;
// 节点实体
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
// 默认色彩为彩色
boolean color = BLACK;
}- 创建对象
public TreeMap() {
// 默认结构器
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
// 传入自定义的结构器
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}- Put 对象
public V put(K key, V value) {
// 赋值
Entry<K,V> t = root;
// 如果此时的 root 为 null
if (t == null) {
// 查看这个 key 是否为 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
// 形同替换 value 值
return t.setValue(value);
} while (t != null);
}
else {
// 应用默认的比拟器，查找办法一样
if (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;
}5.4.2 TreeMap 对象减少的过程
创立一个 TreeMap，此时能够传入一个比拟器，如果不传入依照默认的天然程序进行比拟。
put 对象，首先，查看该 root 节点是否为 null，如果为 null，查看以后传入 key 是否为 null，不为 null，则间接创立一个 root 节点。如果以后 root 节点有值，则通过二分查找，寻找以后能够进行增加的父节点，找到当前依照比拟器规定进行增加。
增加当前，红黑树进行主动均衡实现。
5.5 HashTable 类
HashTable 也是基于哈希表实现，和 HashMap 不同的是 HashTable 是线程平安的。
- 底层实现：哈希表 + 链表
private transient Entry<?,?>[] table;// 存储数组
private transient int count;// 容器中数据多少
private int threshold;// 容器容量达到次数当前进行批改
private transient int modCount = 0;// 批改次数- Hash 函数
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;- 初始化。在构造方法中初始化。初始化指为 11
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);
}- put 办法
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;
//hash 函数计算一个 index
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;
}
// 减少实体
private void addEntry(int hash, K key, V value, int index) {Entry<?,?> tab[] = table;
if (count >= threshold) {
// 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++;
}5.5.1 HashTable 和 HashMap 的区别
| HashTable | HashMap | |
|---|---|---|
| 底层工夫 | 哈希表 + 链表 | 哈希表 + 链表 + 红黑树 |
| 初始化工夫及大小 | 构造方法初始化，大小为 11 | put 办法初始化，大小为 16 |
| 线程平安 | 平安 | 不平安 |
| Hash 值 | 间接应用了 hashcode | 从新计算 |
| 扩容 | 二倍 +1 | 二倍 |
5.6 Properties 类
- Java 配置文件中用的居多
- 能够间接通过 load 办法加载配置文件，通过 store 办法存储配置文件
- 泛型锁定，为两个 String 类型
文章首发于公众号 @MakerStack