集合
8/23/26JavaJava基础About 29 min
集合分两大家族：
- Collection
存放单一对象- List接口
存放的元素有序且重复 - Set接口
存放的元素无序且唯一
- List接口
- Map(接口)家族
存放键值对(key,value)
HashMap
HashMap是一个键值对的集合。
- 无序。
- 非线程安全。
- Key不允许重复，Value允许重复。
- Key允许NULL。
Hash
Hash，一般翻译为“散列”，也有直接音译为“哈希”的，就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值（哈希值）。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
所有散列函数都有如下一个基本特性：根据同一散列函数计算出的散列值如果不同，那么输入值肯定也不同。但是，根据同一散列函数计算出的散列值如果相同，输入值不一定相同。
哈希冲突？
当两个不同的输入值，根据同一散列函数计算出相同的散列值的现象，就把它叫做碰撞（哈希碰撞）。
JDK1.7
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}JDK1.8
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}内部结构
底层采用数组+(链表或红黑树)。
- 进行键值对存储时，先通过hashCode()计算出键(K)的哈希值，然后再数组中查询，如果没有则保存。
- 但若找到相同的哈希值，那么接着调用equals方法判断它们的值是否相同。只有满足以上两种条件才能认定为相同的数据，因此重写了hashCode()和equals()方法。如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式。
- JDK1.8引入红黑树大程度优化了HashMap的性能，根据对象的hashCode和equals方法来决定的。
- JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
- JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值时，将链表转换为红黑树，这样大大减少了查找时间。
构造方法
// hashMap数组的初始容量 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
// 负载因子0.75f;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树形化阈值 8
static final int TREEIFY_THRESHOLD = 8;
// 解除树形化阈值6
static final int UNTREEIFY_THRESHOLD = 6;
// 树形化的另一条件Map数组的长度阈值 64
static final int MIN_TREEIFY_CAPACITY = 64;
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
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;
this.threshold = tableSizeFor(initialCapacity);
}可以将任意一个整数转换成2的次方。数组容量必须是2的次方。
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;
}hash
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}存储
- 检查数组是否为空，执行resize()扩充。
- 通过hash值计算数组索引，获取该索引位的首节点。
- 如果首节点为null(没发生碰撞)，直接添加节点到该索引位(bucket)。
- 如果首节点不为null(发生碰撞)，那么有3种情况：
- key和首节点的key相同，覆盖old value(保证key的唯一性)。
- 如果首节点是红黑树节点(TreeNode)，将键值对添加到红黑树。
- 如果首节点是链表，将键值对添加到链表。添加之后会判断链表长度是否到达
TREEIFY_THRESHOLD - 1这个阈值，尝试将链表转换成红黑树。
- 最后判断当前元素个数是否大于threshold，扩充数组。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
//计算数组索引，获取该索引位置的首节点，如果为null，添加一个新的节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果首节点的key和要存入的key相同，那么直接覆盖value的值。
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 {
//此时首节点为链表，如果链表中存在该键值对，直接覆盖value。
//如果不存在，则在末端插入键值对。然后判断链表是否大于等于7，尝试转换成红黑树。
//注意此处使用“尝试”，因为在treeifyBin方法中还会判断当前数组容量是否到达64
//否则会放弃次此转换，优先扩充数组容量。
//hash碰撞了。检查链表中是否包含key，或将键值对添加到链表末尾
for (int binCount = 0; ; ++binCount) {
// p.next == null，到达链表末尾，添加新节点，如果长度足够，转换成红黑树
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //转换成红黑树
break;
}
//检查链表中是否已经包含key
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); //LinkHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold)//如果元素个数大于阈值，扩充数组。
resize();
afterNodeInsertion(evict);
return null;
}查找
- 检查数组是否为null和索引位首节点(bucket的第一个节点)是否为null。
- 如果索引节点的hash==key的hash或者key和索引节点的k相同则直接返回(bucket的第一个节点)。
- 如果是红黑色则到红黑树查找。
- 如果有冲突，则通过key.equals(k)查找。
- 都没找到就返回null。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}删除
- 根据hash定位到桶位置。
- 遍历链表或调用红黑树相关的删除方法。
- afterNodeRemoval(LinkedHashMap维护的双链表中移除要删除的节点)
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {//遍历单向链表，寻找要删除的节点赋值给node
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); //LinkHashMap
return node;
}
}
return null;
}扩容
先计算新数组的长度和新的阈值(threshold)，然后将旧数组的内容迁移到新数组中，和1.7相比不需要执行rehash操作。因为以2次幂扩展的数组可以简单通过新增的bit判断索引位。
- 如果数组已经是最大长度，不进行扩充。
- 否则数组容量扩充一倍。(2的N次方)。
- 遍历原数组，取出首节点：
- 若只有一个节点，那么直接重新计算索引存入新数组。
- 节点是红黑树，执行split方法，和链表类似的处理。
- 节点是链表，遍历链表。原链表存回原索引位。新链表存到原索引位+原数组长度。
扩充数组不单单只是让数组长度翻倍，将原数组中的元素直接存入新数组中这么简单。因为元素的索引是通过hash&(n - 1)得到的，那么数组的长度由n变为2n，重新计算的索引就可能和原来的不一样了。
在jdk1.7中，是通过遍历每一个元素，每一个节点，重新计算他们的索引值，存入新的数组中，称为rehash操作。而java1.8对此进行了一些优化，没有了rehash操作。因为当数组长度是通过2的次方扩充的，那么会发现以下规律：
元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。因此，在扩充HashMap的时候，不需要像JDK1.7重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
16扩充为32的resize示意图：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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)
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;
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;
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 链表
// loHead，loTail为原链表的节点，索引不变。
Node<K,V> loHead = null, loTail = null;
// hiHeadm, hiTail为新链表节点，原索引 + 原数组长度。
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {//遍历链表
next = e.next;
//新增bit为0的节点，存入原链表。
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;
}Node节点
Node是单向链表，实现了Map.Entry接口并且实现数组及链表的数据结构。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 保存元素的哈希值
final K key; // 保存节点的key
V value; // 保存节点的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;
}
// 重写equals
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;
}
}红黑树
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}尝试把链表转换为红黑树
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
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) {
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);
}
}ConcurrentHashMap
ConcurrentHashMap和HashMap设计思路差不多，但是为支持并发操作，做了一定的改进。
- get方法不加锁。
- put、remove方法要使用锁。
jdk7使用锁分离机制(Segment分段加锁)。
jdk8使用cas + synchronized 实现锁操作。 - Iterator对象的使用，运行一边更新，一遍遍历(可以根据原理自己拓展)。
- 复合操作，无法保证线程安全，需要额外加锁保证。
- 并发环境下，ConcurrentHashMap 效率较Collections.synchronizedMap()更高。
JDK1.7
引入Segment的概念，目的是将map拆分成多个Segment(默认16个)。操作ConcurrentHashMap细化到操作某一个Segment。在多线程环境下，不同线程操作不同的Segment，他们互不影响，这便可实现并发操作。
当对ConcurrentHashMap并发操作时，只要锁住一个segment，其他剩余的Segment依然可以操作。这样只要保证每个Segment是线程安全的，就实现了全局的线程安全。
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
}
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
}JDK1.8
抛弃了Segment的设计，采用了较为轻捷的Node + CAS + Synchronized设计，保证线程安全。
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
//一个死循环，目的，并发情况下，也可以保障安全添加成功
//原理：cas算法的循环比较，直至成功
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //第一次添加，先初始化node数组
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//这里没有ReentrantLock，因为jdk1.8对synchronized做了优化，其执行性能已经跟ReentrantLock不相上下。
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {//节点数大于临界值，转换成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}Hashtable
- 无序。
- 线程安全。
- 存储的内容是键值对(key-value)映射，其底层实现是一个Entry数组+链表。
- key和value都不能为null。
LinkedHashMap
LinkedHashMap继承自HashMap，在HashMap的基础上，通过一条双向链表使插入顺序和访问顺序保持一致。
构造函数
transient LinkedHashMap.Entry<K,V> head; //首节点
transient LinkedHashMap.Entry<K,V> tail; //尾节点
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}内部结构
双向链表，继承至HashMap.Node类，并在此基础上扩展了两个属性：前节点和后节点。
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);
}
}HashMap中为LinkedHashMap预留了3个方法：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }存储
LinkedHashMap没有重写put()。而是对创建节点newNode()的方法进行了重写。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)//如果链表是空的，将p放在链表头部
head = p;
else { //如果链表不为空，将p放到链表的尾部
p.before = last;
last.after = p;
}
}
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);
}
}查找
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null) //HashMap.getNode()
return null;
if (accessOrder)
afterNodeAccess(e); //若设置了accessOrder字段为true，那么get()方法在获得数据之后，会将该数据节点放置链表的最后。
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}删除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null; // 将p节点的前节点、后节点引用设置为NULL
if (b == null) //b为null,p是首节点
head = a;
else
b.after = a;
if (a == null) //a为null,p是尾节点
tail = b;
else
a.before = b;
}TreeMap
- 非线程安全。
- Key不允许重复，Value允许重复。
- Key不允许NULL。
- 有序，默认是按键值的升序排序，也可以指定排序的比较器。
TreeMap底层基于红黑树实现。而红黑树是一种自平衡二叉查找树，所以TreeMap的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的，先将目标值和根节点的值进行比较，如果目标值小于根节点的值，则再和根节点的左孩子进行比较。如果目标值大于根节点的值，则继续和根节点的右孩子比较。在查找过程中，如果目标值和二叉树中的某个节点值相等，则返回true，否则返回false。TreeMap查找和此类似，只不过在TreeMap中，节点(Entry)存储的是键值对<k,v>。在查找过程中，比较的是键的大小，返回的是值，如果没找到，则返回null。
插入
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { //如果根节点为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
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;
}查找
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}HashSet
HashSet是一个无序的集合。底层基于HashMap实现。将HashSet的数据作为HashMap的Key值保存，利用HashMap的key不可重复从而实现HashSet不含重复元素。所以：
- 元素不可重复。
- 元素存储无序，而且HashSet允许使用null元素(仅一个)。
- 线程不安全，Collections.synchronizedSet(new HashSet(…))确保安全。
构造函数
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
// 提供给LinkedHashSet使用 实现有序
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}存储
所有放入HashSet中的集合元素实际上由HashMap的key来保存，而HashMap的value则存储了一个 PRESENT，它是一个静态的Object对象。
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}HashSet的其他操作都是基于HashMap的。
public boolean contains(Object o) {
return map.containsKey(o);
}
public void clear() {
map.clear();
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}LinkedHashSet
LinkedHashSet是一个有序的集合。继承自HashSet。通过父类(HashSet)构造LinkedHashMap实现有序。所以：
- 元素不可重复。
- 元素存储有序，而且HashSet允许使用null元素(仅一个)。
- 线程不安全，Collections.synchronizedSet(new HashSet(…))确保安全。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}TreeSet
TreeSet是Set的实现类之一，基于Treemap(红黑树)实现。TreeSet是SortedSet的唯一实现类，实现了元素的自动排序，排序不是以插入的顺序排序，而是默认以元素的大小进行自动排序，也可以指定排序方式来按照定制排序。
- 有序
- 不可重复。
- 非线程安全的。
构造函数
private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}存储
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
return super.addAll(c);
}删除
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
public void clear() {
m.clear();
}ArrayList
- 有序。
- 允许重复。
- 非线程安全。
- 是一个动态数组，容量可以自动扩容，不适合频繁增加元素的场景。线性存储结构，需要调整、压缩、移动底层数组元素，因此对于增删的时间复杂度较高。
底层是基于数组来实现容量大小动态变化的。
构造函数
private static final long serialVersionUID = 8683452581122892189L;
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = new Object[0];
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = 2147483639;
public ArrayList(int var1) {
if (var1 > 0) {
this.elementData = new Object[var1];
} else {
if (var1 != 0) {
throw new IllegalArgumentException("Illegal Capacity: " + var1);
}
this.elementData = EMPTY_ELEMENTDATA;
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> var1) {
this.elementData = var1.toArray();
if ((this.size = this.elementData.length) != 0) {
if (this.elementData.getClass() != Object[].class) {
this.elementData = Arrays.copyOf(this.elementData, this.size, Object[].class);
}
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}存储
- add(E var1)将新元素放到了原来的元素的后面，因为不用移动原来的元素，所以比较快。
- add(int var1, E var2)将原来index后面的所有元素往后面移动一个位置，将新元素放到index位置，每次插入都需要移动index后面的元素，所以效率很低。
public void add(int var1, E var2) {
this.rangeCheckForAdd(var1);
this.ensureCapacityInternal(this.size + 1);
System.arraycopy(this.elementData, var1, this.elementData, var1 + 1, this.size - var1);
this.elementData[var1] = var2;
++this.size;
}
public boolean add(E var1) {
this.ensureCapacityInternal(this.size + 1);
this.elementData[this.size++] = var1;
return true;
}
private void ensureCapacityInternal(int var1) {
this.ensureExplicitCapacity(calculateCapacity(this.elementData, var1));
}
private static int calculateCapacity(Object[] var0, int var1) {
return var0 == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ? Math.max(10, var1) : var1;
}
private void ensureExplicitCapacity(int var1) {
++this.modCount;
if (var1 - this.elementData.length > 0) {
this.grow(var1); //调用grow方法进行扩容，调用此方法代表已经开始扩容了
}
}
private void grow(int var1) {
int var2 = this.elementData.length;
int var3 = var2 + (var2 >> 1); //容量变成原来的1.5倍
if (var3 - var1 < 0) {
var3 = var1;
}
if (var3 - 2147483639 > 0) {
var3 = hugeCapacity(var1);
}
this.elementData = Arrays.copyOf(this.elementData, var3);
}
private static int hugeCapacity(int var0) {
if (var0 < 0) {
throw new OutOfMemoryError();
} else {
return var0 > 2147483639 ? 2147483647 : 2147483639;
}
}删除
public E remove(int var1) {
this.rangeCheck(var1);
++this.modCount;
Object var2 = this.elementData(var1);
int var3 = this.size - var1 - 1;
if (var3 > 0) {
System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var3);
}
this.elementData[--this.size] = null;
return var2;
}
public boolean remove(Object var1) {
int var2;
if (var1 == null) {
for(var2 = 0; var2 < this.size; ++var2) {
if (this.elementData[var2] == null) {
this.fastRemove(var2);
return true;
}
}
} else {
for(var2 = 0; var2 < this.size; ++var2) {
if (var1.equals(this.elementData[var2])) {
this.fastRemove(var2);
return true;
}
}
}
return false;
}
private void fastRemove(int var1) {
++this.modCount;
int var2 = this.size - var1 - 1;
if (var2 > 0) {
System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var2);
}
this.elementData[--this.size] = null;
}更新
public E set(int var1, E var2) {
this.rangeCheck(var1);
Object var3 = this.elementData(var1);
this.elementData[var1] = var2;
return var3;
}
private void rangeCheck(int var1) {
if (var1 >= this.size) {
throw new IndexOutOfBoundsException(this.outOfBoundsMsg(var1));
}
}查找
public E get(int var1) {
this.rangeCheck(var1);
return this.elementData(var1);
}
public int indexOf(Object var1) {
int var2;
if (var1 == null) {
for(var2 = 0; var2 < this.size; ++var2) {
if (this.elementData[var2] == null) {
return var2;
}
}
} else {
for(var2 = 0; var2 < this.size; ++var2) {
if (var1.equals(this.elementData[var2])) {
return var2;
}
}
}
return -1;
}
public int lastIndexOf(Object var1) {
int var2;
if (var1 == null) {
for(var2 = this.size - 1; var2 >= 0; --var2) {
if (this.elementData[var2] == null) {
return var2;
}
}
} else {
for(var2 = this.size - 1; var2 >= 0; --var2) {
if (var1.equals(this.elementData[var2])) {
return var2;
}
}
}
return -1;
}LinkedList
- 有序。
- 允许重复。
- 非线程安全。
- 基于双向链表实现，容量可以自动扩容。
内部类Node
一个节点除了保持自身的数据外，还持有前，后两个节点的引用。所以就数据存储上来说，它相比使用数组作为底层数据结构的ArrayList来说，会更加耗费空间。但也正因为这个特性，它删除，插入节点很快。
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;
}
}Properties
Vector
Vector也是基于数组实现的，是一个动态数组，其容量能自动增长，它的源码实现总体与ArrayList类似。Vector内部很多方法都加入了synchronized关键字，来保证线程安全。
Stack
Stack是栈。它的特性是先进后出(FILO, First In Last Out)。
ArrayDeque
- 非线程安全。
- 基于数组实现的双端队列。
- 栈：后进先出(LIFO-last in first out)最后插入的元素最先出来。
- 队列：先进先出(FIFO-first in first out)最先插入的元素最先出来。
当做栈使用时，要比Stack(Stack是线程安全的，使用synchronized修饰方法)更高效，当队列使用时，要比LinkedList(使用链表实现)更高效。
构造方法
ArrayDeque对队列的容量有特殊的要求，必须是2n(这里和HashMap类似)，由于231超出int的最大值，故ArrayDeque的最大容量为2^30。
transient Object[] elements; // non-private to simplify nested class access
transient int head;
transient int tail;
private static final int MIN_INITIAL_CAPACITY = 8;
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
//与'+='符号类似，a |= b 等效于 a = a | b, 这里进行的是二进制的或运算
//假设initialCapacity = 24, 二进制数值为 00011000;
//initialCapacity >>> 1 二进制数值为 00001100;
// 00011000 | 00001100 = 00011100; 28
initialCapacity |= (initialCapacity >>> 1);
// 00011100 >>> 2 = 00000111;
// 00011100 | 00000111 = 00011111; 31
initialCapacity |= (initialCapacity >>> 2);
//00011111 >>> 4 = 00000001;
//00011111 | 00000001 = 00011111; 31
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
//int为32位 通过这连续几次左移操作总共左移了31位(1+2+4+8+16 = 31)
//将二进制数从第一个不为0的位开始后面每一位都变成1
//最后再加1取得比numElements大的最小2的次幂
initialCapacity++;
//initialCapacity超出int最大值时，左移一位(除以2)，最大容量为2 ^ 30
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}插入
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//head = (head - 1) & (elements.length - 1)实际上就是从数据最后一位开始依次向前添加元素
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)//当head==tail时说明数组已经装满了，需要进行扩容
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}取出
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h]; //将队列头部的元素赋值给result
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot 将头部元素置空
head = (h + 1) & (elements.length - 1); //将头部指针向右移一位
return result;
}
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}doubleCapacity
将原数组从head位置一分为二，分别拷贝到新数组中；比如数组容量16，head位置是7，则先将原数组下标从7开始，拷贝16-7个元素到新的下标从0开始，元素个数为16-7的数组中。然后将原数组下标从0开始到7的元素拷贝到新数组下标从(16-7)开始，元素个数是7的数组中。这么做的目的就是为了拷贝到新数组的时候保持元素原来的顺序。
重新确定头尾指针的位置。
private void doubleCapacity() {
//断言，当head == tail为true时才会向下执行，否则抛出AssertionError并终止执行
assert head == tail; //当head == tail时表明底层数组已经满了
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1; //长度扩大为2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r); //head后面的元素COPY到新数组的开始位置
System.arraycopy(elements, 0, a, r, p); //head前面的元素COPY到新数组的开始位置
elements = a; //底层数组替换成扩容后的数组
head = 0; //head重置为0
tail = n; //tail重置为最后一个位置索引+1
}