Arraylist

底层数据结构

1
transient Object[] elementData;  //元素数据底层数组实现

默认构造函数

1
2
3
4
5
public MyArrayList(){
//数组默认大小
elementData = new Object[10];
size = 0;
}

简单实现增删改查方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// add方法
public void add(T t){
elementData[size++] = t;
}

// get方法
public Object get(int index){

if(index > size){
throw new RuntimeException("数组没有"+index+"这个元素");
}

return elementData[index];
}

// remove
public void remove(int moveNum){
// 获取删除元素后的元素数量
int lastes = size - moveNum - 1;

// 核心将删除索引后的元素赋值到前面
if(moveNum > 0){
// 删除索引的后一位开始复制数组到原数组的删除索引,复制大小为lastes
System.arraycopy(elementData,moveNum+1,elementData,moveNum,lastes);
}
}

// set
public String set(int index,String newValue){
// 判断索引是否存在
if(index >= size){
throw new RuntimeException("索引越界");
}
String oldValue = (String)elementData[index];
elementData[index] = newValue;
return oldValue;
}

扩容核心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int newCapacity(int minCapacity) {
int oldCapacity = this.elementData.length;
// 新容量为老容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(10, minCapacity);
} else if (minCapacity < 0) {
throw new OutOfMemoryError();
} else {
return minCapacity;
}
} else {
// 新容量大于最大值时的处理
return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
}
}

elementData 用transient 修饰,序列化后数据会丢失吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();

// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size);

// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}

if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}

不对elementData序列化,对elementData中的元素进行循环,取出来单独进行序列化。

为什么不直接对数组序列化

一般情况下数组是没有存满的,直接序列化会造成空间浪费

与Vector的比较

  • 与Arraylist相似,除了添加了synchronized保证线成安全,扩容自定义
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 在add方法上添加了synchronizated
    public synchronized boolean add(E e) {
    ++this.modCount;
    this.add(e, this.elementData, this.elementCount);
    return true;
    }
    // 扩容 用户可在初始化阶段指定capacityIncrement的大小
    // 没指定就扩容原来的2倍
    int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);

    LinkedList

    底层数据结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    // 被transient修饰的成员变量不参与序列化过程。
    transient int size;
    transient LinkedList.Node<E> first; // 记录第一个节点
    transient LinkedList.Node<E> last; // 记录最后一个节点
    // 构造函数
    private static class Node<E> {
    E item;
    // 底层为双向链表
    LinkedList.Node<E> next;
    LinkedList.Node<E> prev;

    Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
    }
    }

    简单实现增删改查方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    //add
    public void add(E e){
    Node l = last; // 保存最后节点
    MyLinkedList.Node<E> newNode = new MyLinkedList.Node(l, e, null);
    this.last = newNode;
    if(l == null) // 集合中没有数据
    first = newNode;
    else
    l.next = newNode;
    size++;
    }
    //set
    public E set(int index, E element) {
    // 判断index的合理性
    if(0 >= index || index >= size){
    throw new RuntimeException("不存元素");
    }
    MyLinkedList.Node<E> x = this.get(index); // 获取当前索引节点
    E oldVal = x.item;
    x.item = element;
    return oldVal;
    }
    // get
    public MyLinkedList.Node<E> get(int index){
    // 判断index的合理性
    if(0 >= index || index >= size){
    throw new RuntimeException("不存元素");
    }

    MyLinkedList.Node x;
    int i;
    if(index < size >> 1){ //判断索引在前半部分还是后半部分
    x = this.first;
    for(i = 0; i < index; i++){
    x = x.next;
    }
    }else{
    x = this.last;
    for(i = size; i > index; i--){
    x = x.prev;
    }
    }
    return x;
    }
    // remove
    public E remove(int index){
    // 判断index的合理性
    if(0 >= index || index >= size){
    throw new RuntimeException("不存元素");
    }
    // 通过get方法得到该节点
    Node<E> x = get(index);
    // 保存该节点的信息
    E element = x.item;
    MyLinkedList.Node<E> next = x.next;
    MyLinkedList.Node<E> prev = x.prev;

    if(prev == null){
    this.first = next;
    }else{
    // 让当前节点的前一个节点的下一个节点指向当前节点的下一个节点
    // 1 <-> 2 <-> 3 删除2
    // 1 -> 3
    prev.next = next;
    x.prev = null;
    }

    if(next == null){
    this.last = prev;
    }else{
    // 让当前节点的后一个节点的前一个节点指向当前节点的前一个节点
    // 1 <-> 2 <-> 3 删除2
    // 1 <- 3
    next.prev = prev;
    x.next = null;
    }

    x.item = null;
    --this.size;
    return element;
    }

    HashMap

    底层数据结构

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //底层是 数组和链表和红黑树 结合在一起使用也就是 链表散列。
    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;
    }
    // get set equals方法

KEY的hash过程

1
2
3
4
5
6
7
8
9
//   首先取 key值进行 hashcode 算出hashcode赋值给 h , 在用自己的底16位和自己的高16位进行异或
static final int hash(Object key) {
int h;
// 扰动机制,table的长度一般都小于2^16,所有让高16位参与运算会让hash值更散
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 在 put 元素时进行了 与操作
n = (tab = resize()).length; // hash表长度
if ((p = tab[i = (n - 1) & hash]) == null)

这里可以体现为什么HashMap的长度建议为2的幂次

  • 当数组长度为 2 的幂次是 length - 1就刚好所有的二进制全为 1

不是2的幂次,则算出的length - 1就会存在一些位置为 0,而0进行&操作,就一定为0,增加了hash冲突概率

jdk如何保证刚好是2的幂次

1
2
3
4
5
6
7
8
9
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;
}

n 如果是正整数,那么最高位肯定是 1

  1. n或上无符号右移1位,则不管n的第二位是0,1都会变成1,现在就最高位和次位都为1
  2. n或上无符号右移2位,就是将第一步前两个1与第3,4个或变成1,现在就是前4位为1

。。。。。。。

为什么要cap - 1;

  1. 因为如果n 刚好是2的整数幂,则会将n变成2^(n + 1);

扩容过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 成员变量含义
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 默认容量
static final int MAXIMUM_CAPACITY = 1 << 30; // 最大容量
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认负载因子
static final int TREEIFY_THRESHOLD = 8; // 树化的门限
static final int UNTREEIFY_THRESHOLD = 6; // 解除树化的门限
// 树化时table的最小容量,当hashmap中不超过64个元素,即使hash冲突超过树化门限时也不会树化,而是进行扩容
static final int MIN_TREEIFY_CAPACITY = 64;
// 关键构造函数
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 的幂次
}

负载因子越大则散列表的装填程度越高也就是能容纳更多的元素,元素多了,链表大了,所以此时索引效率就会降低

负载因子越小则链表中的数据量就越稀疏,此时会对空间造成浪费,但是此时索引效率高。

扩容大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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;
else if (p instanceof TreeNode)
// 如果当前节点是 树 节点就按照树节点插入数据
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 否则就为 链表节点 ,按照尾插法插入数据
//JDK1.8的链表插入元素为什么改为了尾插法,
//则是为了避免出现逆序且链表死循环的问题(JDK1.7的HashMap扩容导致死循环)
// 。。。省略实现
}
++modCount; // 修改次数
if (++size > threshold) // 先 put 元素在 扩容
resize();
afterNodeInsertion(evict);
return null;
}
// ---------------------------扩容实现核心---------------
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; // 扩容为原来的两倍
}
// 。。。。。。
// 跟新容量和长度
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) {
// 当前索引只有一个元素 , 直接重新计算Hash下标索引
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 {
// 链表结构处理
// 循环链表中的元素,计算是新索引还是老索引
}
}
}
}
return newTab;
}
// -------------------------------红黑树扩容情况--------------------
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this; // 调用方法的原始节点
// 扩容就两位置 原索引 原索引+oldCap
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 遍历整棵树
for (TreeNode<K,V> e = b, next; e != null; e = next) {
// 拿到所有节点 重新计算hash
//.....
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD) // 节点个数 <= 6改成链表
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
// 重新构建红黑树
hiHead.treeify(tab);
}
}
}

}

HashTable和HashMap区别

  1. 继承的父类不同 Hashtable继承自Dictionary类,而HashMap继承自AbstractMap类。
  2. 线程安全性不同

Hashtable 中的方法是Synchronize的,而HashMap中的方法在缺省情况下是非Synchronize的。

  1. key和value是否允许null值
1
2
3
4
5
6
7
8
9
10
11
#################### hashMap #####################
static final int hash(Object key) { //自定义的hash算法
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
#################### hashtable #####################
int hash = key.hashCode(); //直接用object提供的hashcode方法,所以key不能为null
int index = (hash & 0x7FFFFFFF) % tab.length;
if (value == null) { // 在put元素是也判断了value
throw new NullPointerException();
}
  1. 内部实现使用的数组初始化和扩容方式不同

Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。 Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11,增加的方式是 old*2+1。

HashSet

底层数据结构

1
2
3
4
5
6
7
8
9
// 底层数据为hashMap
private transient HashMap<E, Object> map;
// HashSet的所有元素的Value值
private static final Object PRESENT = new Object();
// 去重的原因就是 判断插入元素返回的值是否为null
public boolean add(E e) {
// map在 put相同元素时产生Hash冲突,返回被覆盖的元素值
return map.put(e, PRESENT)==null;
}

ConcurrentHashMap

核心构造函数

1
2
3
4
5
6
7
8
9
10
11
12
public ConcurrentHashMap(int initialCapacity,
float loadFactor,
int concurrencyLevel) { // 并发级别
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}

concurrencyLevel:并行级别、并发数、Segment 数,怎么翻译不重要,理解它。默认是 16,也就是说 ConcurrentHashMap 有 16 个 Segments,所以理论上,这个时候,最多可以同时支持 16 个线程并发写,只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值,但是一旦初始化以后,它是不可以扩容的。

currenthashmap是如何保证并发的

JDK8中彻底放弃了Segment转而采用的是Node,其设计思想也不再是JDK1.7中的分段锁思想。

Node:保存key,value及key的hash值的数据结构。其中value和next都用volatile修饰,保证并发的可见性。

Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样,不过保证线程安全性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 在高版本的JDK中,抛弃了桶设计,大量使用了 CAS + Volatile + Synchronized来实现并发安全
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;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
// 如果元素 CAS 插入失败 则采用 Synchronized 锁
V oldVal = null;
synchronized (f) {
// 。。。。。。
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); // 容量加一也用到了CAS
return null;
}

区别总结

特性/集合类 HashMap Hashtable ConcurrentHashMap
线程安全 是,基于方法锁 是,基于分段锁
继承关系 AbstractMap Dictionary AbstractMap,ConcurrentMap
允许null值 K-V都允许 K-V都不允许 K-V都不允许
默认初始容量 16 11 16
默认加载因子 0.75 0.75 0.75
扩容后容量 原来的两倍 原来的两倍加1 原来的两倍
是否支持fail-fast 支持 不支持 fail-safe

LinkedHashMap实现LRU

介绍LinkedHashMap维护的两种顺序,插入顺序和访问顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16,0.75f,true);;
linkedHashMap.put("f", "1");
linkedHashMap.put("s", "2");
linkedHashMap.put("t", "3");

System.out.println("插入顺序:");
for (Map.Entry<String, String> item : linkedHashMap.entrySet()) {
System.out.println(item.getKey() + ": =>" + item.getValue());
}

System.out.println("访问顺序:");
for (Map.Entry<String, String> item : linkedHashMap.entrySet()) {
System.out.println(item.getKey() + ": =>" + item.getValue());
}
}

插入顺序:
f: =>1
s: =>2
t: =>3
访问顺序:
f: =>1
s: =>2
t: =>3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16,0.75f,true);
linkedHashMap.put("f", "1");
linkedHashMap.put("s", "2");
linkedHashMap.put("t", "3");

System.out.println("插入顺序:");
for (Map.Entry<String, String> item : linkedHashMap.entrySet()) {
System.out.println(item.getKey() + ": =>" + item.getValue());
}

linkedHashMap.get("s");
System.out.println("访问顺序:");
for (Map.Entry<String, String> item : linkedHashMap.entrySet()) {
System.out.println(item.getKey() + ": =>" + item.getValue());
}

插入顺序:
f: =>1
s: =>2
t: =>3
访问顺序:
f: =>1
t: =>3
s: =>2

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {

private int cap; // 缓存容量

LRULinkedHashMap(int cap){
super(16,0.75f,true);
this.cap = cap;
}

@Override // 集合容量大于缓存,就删除顶端元素
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cap;
}
}