数据结构整理
数据结构主要是要了解它的底层存储模型（数组、链表、map之类），是否线程安全，它加对象的方法，获取对象的方法，是否是有序这五点。
Collection
List extends Collection
Vector
底层基于数组实现，多用于查询，线程安全（因为Vector的操作方法大多增加了synchronized锁）
1 | class Vectore extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ |
ArrayList
- 底层基于数组实现，多用于查询，线程不安全
1
2
3private int size; // 实际元素个数
transient Object[] elementData; // 保存数据的数组
// 增长系数为1.5，如果太小增赋值所需的容量，如果太大则赋值Integer.MAX_VALUE
LinkedList
- 底层基于链表实现，多用于插入和删除，线程不安全。
- 属于双联表，get(index)查询时会判断index和链表长度，超过一半从末尾查，小于一半从开始查。
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
27public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList(. {
//
}
public LinkedList(Collection<? extends E> c. {
this();
addAll(c);
}
//
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;
}
}
}
Set extends Collection
HashSet
- 无序存储数据，不能重复，可存储null，通底层过HashMap实现（将数据保存到HashMap的Key，value统一为Object()）。线程不安全。
1
2
3
4
5
6
7
8
9
10
11public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E, Object> map; // 底层使用HashMap来保存HashSet中所有元素。
private static final Object PRESENT = new Object();// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。
public HashSet(. {
map = new HashMap<E, Object>();
}
public boolean add(E e. {
return map.put(e, PRESENT. == null;
}
TreeSet
- 有序存储数据，不能重复，可以存储null，底层通过 TreeMap 实现，排序通过二叉树的排序实现。线程不安全。
- 因为有顺序所以存储的对象需要实现Comparable接口、或者给TreeSet构造器传入Comparator实现类。
1
2
3
4
5
6
7
8
9
10
11
12public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable{
private transient NavigableMap<E,Object> m; //PRESENT会被当做Map的value与key构建成键值对
private static final Object PRESENT = new Object();
TreeSet()// 默认构造函数。使用该构造函数，TreeSet中的元素按照自然排序进行排列。
TreeSet(Comparator<? super E> comparator)// 指定TreeSet的比较器
public boolean add(E e. {
return m.put(e, PRESENT)==null;
}
}
LinkedHashSet
- 根据插入的顺序排列，不能重复，可以存储null，底层通过 LinkedHashMap 实现。线程不安全。
Map
HashMap（jdk1.8加入了红黑树）
- 基于Map实现、可null键/值、非同步、不保证有序(比如插入的顺序)、也不保证顺序不随时间变化.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public class HashMap<K,V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable{
static final int DEFAULT_INITIAL_CAPACITY = 16; // 默认存储容量
static final int MAXIMUM_CAPACITY = 1073741824; // 2的31次方-1；
static final float DEFAULT_LOAD_FACTOR = 0.75F; // 默认扩容因子
static final int TREEIFY_THRESHOLD = 8; // 链表最大长度
static final int MIN_TREEIFY_CAPACITY = 64; // 树形化最小容量（链表的4倍）
transient HashMap.Node<K, V>[] table; // 存储数据的数组
transient int size; // Node节点总数（数组+链表+树）
int threshold; // = capacity（数组容量） * loadFactor（扩容因子）
// 数组存储对象
static class Node<K, V> implements Entry<K, V> {
final int hash;
final K key;
V value;
HashMap.Node<K, V> next; // 服务于链表
Node(int hash, K key, V value, HashMap.Node<K, V> next. {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
} - 添加数据过程
- 1 第一次会初始化Node数组（默认长度16）；计算数组下表index，index位置没有值直接插入数据。
- 2 如果index位置有值，判断hash和key是否相等，相等则覆盖原有Node。
- 3 如果发生碰撞，判断该位置存放的是否是TreeNode，如果是调用TreeNode.putTreeVal插入树中
- 4 如果不是TreeNode节点说明是链表，则添加至链表尾部。最后检查链表的长度是否超过链表阈值8，是的化将链表转为红黑树。
- 5 只有原值覆盖会返回旧值，不会出发size++；否则都会size+1和阈值（threshold = capacity * loadFactor）比较，如果size大于阈值会进行扩容。
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// 获取hash值
static final int hash(Object key. {
int h;
// 如果为 null 则返回的就是 0，否则就是 hashCode 异或上（hashCode 无符号右移 16 位）
return (key == null. ? 0 : (h = key.hashCode(). ^ (h >>> 16);
}
// 获取index。自己抽离获取数组下表的方法，原HashMap类是没有的，单独拿出来方便记忆
// hash:hash(Object key);n:table.length
static final int index(int hash,int n){
return hash & (n -1);// 按位与获得，等于（hash%n）
}
// HashMap的put方法最终会执行此方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict. {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab为空则通过resize()创建，插入第 1 个值的时候发生
if ((tab = table. == null || (n = tab.length. == 0)
n = (tab = resize()).length;
// 计算散列 index，没有冲突直接插入
if ((p = tab[i = (n - 1. & hash]. == null)
tab[i] = newNode(hash, key, value, null);
// 有冲突
else {
Node<K,V> e; K k;
// 存在 hash 值相同且 key 相等的，先记录下来，后面的插入步骤会使用新值将旧值替换掉
if (p.hash == hash && ((k = p.key. == key || (key != null && key.equals(k))))
e = p;
// 该节点为树，散列冲突过长，大于 TREEIFY_THRESHOLD = 8 时会转换成树
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 - 1 则转换成树
if (binCount >= TREEIFY_THRESHOLD - 1. // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 在链表中又相同的key，替换node
if (e.hash == hash && ((k = e.key. == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 插入 existing mapping for key
if (e != null. {
// 取出旧值，onlyIfAbsent此时为 false，所以不管 oldValue 有与否，都拿新值来替换
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超过阈值 threshold = capacity * factor，调用 resize(. 进行扩容
resize();
if (++size > threshold)
afterNodeInsertion(evict);
return null;
} // end putVal - 扩容过程（如果resize方法被调用意味着除了达到最大容量否则都会出发扩容或则初始化）
- 1 如果是初始化，容量为默认的16，阈值threshold为capacity * loadFactor = 12。
- 2 不是初始化，容量扩大1 倍，阈值也是扩大1倍。
- 3 如果扩大的容量大于最大容量（2的30次方-1），取最大容量。
- 4 如果当前容量已经为最大容量不扩容，通过碰撞存数据。
- 5 创建扩容后数组，将原数组的数据移入新数组中，因为新组数的长度发生了变化所以存入的数据都需要重新计算index。参考
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// 扩容会对性能会造成十分严重的影响，看下resize的具体内容
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. {
// 超过最大值就不再扩充 table，但并不表示不能插入了，只是后面的只能碰撞冲突了
if (oldCap >= MAXIMUM_CAPACITY. {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 没超过最大值，就扩充为原来的 2 倍。主要是容量以及阈值都为原来的 2倍。容量和阈值本身就都必须是2的幂，所以扩容的倍数必须是2的倍数，那么扩2倍就非常合理了。
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);
}
// 计算新的resize阈值
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. {
// 把原来 tables 中的每个节点都移动到新的 tables 中
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)// 冲突的是一棵树节点，分裂成 2 个树，或者如果树很小就转成链表
((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;
}
// 原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next. != null);
// 原索引放到 tables 里
if (loTail != null. {
loTail.next = null;
newTab[j] = loHead;
}
// 原索引+oldCap放到 tables 里
if (hiTail != null. {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} // end resize
参考
LinkedHashMap extends HashMap
- 基于HashMap，并且通过增加head和tai以及自定义Entry（比Node多了before和after）实现双链表达到有序存储的功能。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> {
transient LinkedHashMap.Entry<K, V> head; // 头节点
transient LinkedHashMap.Entry<K, V> tail; // 尾节点
final boolean accessOrder; // 是否通过访问调整顺序，true：访问过将对象放置最末尾
// 自定义Entry
static class Entry<K, V> extends Node<K, V> {
LinkedHashMap.Entry<K, V> before; // 前一节点
LinkedHashMap.Entry<K, V> after; // 下一个节点
Entry(int var1, K var2, V var3, Node<K, V> var4. {
super(var1, var2, var3, var4);
}
}
} - put对象和HashMap的put的逻辑一样，区别是在newNode(hash, key, value, null)方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17Node<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;
}
// 放置末尾方法，服务于putVal方法，无视 accessOrder 属性
private void linkNodeLast(LinkedHashMap.Entry<K,V> p. {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
} - get方法和HashMap的区别是多了 accessOrder 的逻辑，如果accessOrder为true会调用afterNodeAccess方法。
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
35public V get(Object key. {
Node<K,V> e;
if ((e = getNode(hash(key), key). == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
// 总结一点就是将访问的当前对象放到最末尾，只有在accessOrder==true时起作用。
void afterNodeAccess(Node<K,V> e. {
//在执行方法前的上一次的尾结点
LinkedHashMap.Entry<K,V> last;
//当accessOrder为true并且传入的节点并不是上一次的尾结点时,执行下面的方法
if (accessOrder && (last = tail. != e. {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p：当前节点，b：当前节点的前一个节点，a：当前节点的后一个节点；
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;
}
} - 移除链表中最老的对象，但在JDK8中不会执行。参考
1
2
3
4
5
6
7
8
9
10
11void 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;
}
TreeMap（会有Key值的比较器，使用默认比较器时Key值不能为null）
- 基于红黑树存储的Map（底层没有数组），通过Key值比较大小，也可以自己传入Comparator比较器。
- HashMap适用于快速查找，LinkedHashMap适用于按操作顺序查找，TreeMap适用于按排序的统计查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25public class TreeMap<K, V> extends AbstractMap<K, V> implements NavigableMap<K, V>, Cloneable, Serializable {
private final Comparator<? super K> comparator; // 比较器
private transient TreeMap.Entry<K, V> root; // 根节点
private transient int size = 0; // entry个数
private transient TreeMap<K, V>.EntrySet entrySet;
private transient TreeMap.KeySet<K> navigableKeySet;
private transient NavigableMap<K, V> descendingMap;
private static final boolean RED = false;
private static final boolean BLACK = true;
static final class Entry<K, V> implements java.util.Map.Entry<K, V> {
K key;
V value;
TreeMap.Entry<K, V> left;
TreeMap.Entry<K, V> right;
TreeMap.Entry<K, V> parent;
boolean isBlck = true;
Entry(K var1, V var2, TreeMap.Entry<K, V> var3. {
this.key = var1;
this.value = var2;
this.parent = var3;
}
}
} - put对象，就是将entry插入到红黑树的过程
- 1 如果是第一次插入，作为跟节点即可。
- 2 不是第一次查找是否，通过比较器二分法查找key值相同的节点进行替换
- 3 没有相同的key节点，在末尾插入节点
- 4 调用fixAfterInsertion进行红黑树的合规维护。
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
74public V put(K key, V value. {
Entry<K,V> t = root;
// 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红黑树中已经有一个节点了，同时修改操作+1。
if (t == null. {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；定义parent，是new Entry时必须要的参数
int cmp;
Entry<K,V> parent;
// cpr表示有无自己定义的排序规则，分两种情况遍历执行
Comparator<? super K> cpr = comparator;
if (cpr != null. {
/**
* 从root节点开始遍历，通过二分查找逐步向下找
* 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
* cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
* 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
* 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
* 那么直接根据root节点的value值即可。
* 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
*
* 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
*/
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 {
//从这里看出，当默认排序时，key值是不能为null的
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);
}
/**
* 能执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
* 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;
} - get数据，就是红黑树的查找。
参考
Hashtable（线程安全，key、value都不能为null）
- Hashtable 是针对 HashMap 线程安全的一种实现（在操作方法前添加了Synchronized关键字）
- 由于会直接调用key.hashCode，key不能为null；在put方法总会判断value == null而抛出异常，所以value也不能为null
- 数组索引方式和HashMap不一样（HashTable底层的扩容方式不一样，是通过hashCode & 0x7FFFFFFF. % tab.length）
- 扩容方式和HashMap不一样（默认容量为11，扩容为原来的2倍+1）
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
28public class Hashtable<K, V> extends Dictionary<K, V> implements Map<K, V>, Cloneable, Serializable {
private transient Hashtable.Entry<?, ?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount;
private static final int MAX_ARRAY_SIZE = 2147483639;
private transient volatile Set<K> keySet;
private transient volatile Set<java.util.Map.Entry<K, V>> entrySet;
private transient volatile Collection<V> values;
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;
private static class Entry<K, V> implements java.util.Map.Entry<K, V> {
final int hash;
final K key;
V value;
Hashtable.Entry<K, V> next;
protected Entry(int var1, K var2, V var3, Hashtable.Entry<K, V> var4. {
this.hash = var1;
this.key = var2;
this.value = var3;
this.next = var4;
}
}
}
ConcurrentHashMap（jdk1.7和jdk1.8的实现又大变化）(1.8版本put方法会判KV空抛出错误)
jdk1.7
1 外层通过数组存储segment，通过segment实现真是数据HashEntry的操作。
2 segment继承自ReentrantLockjava线程知识梳理，通过数组+链表存储数据。(ReentrantLock对象提供手动锁和解锁，可实现公平锁，响应中断和限时等待的功能)
3 添加对象
3.1 如果是第一次会进行segment数组初始化和调用ensureSegment初始化当前segment。
3.2 ConcurrentHashMap现通过Hash值、segmentShift和SegmentMark算出segment组数的下表获取segment，调用segment.put方法。
3.3 segment的put方法添加对象和HashMap大致相同，区别在于开头和结尾会调用自身的lock和unlock以达到线程安全，因为HashEntry的next为final，所以新添加的元素会放在表头。（获取锁时有个自旋等待过程）
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
54final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 是否获取锁,失败自旋获取锁(直到成功)
HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
// 定义位置
int index = (tab.length - 1) & hash;
// 获取第一个桶的第一个元素
// entryAt 底层调用getObjectVolatile 具有volatile读语义
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) { // 证明链式结构有数据 遍历节点数据替换,直到e=null
K k;
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) { // 找到了相同的key
oldValue = e.value;
if (!onlyIfAbsent) { // 默认值false
e.value = value; // 替换value
++modCount;
}
break; // 结束循环
}
e = e.next;
}
else { // e=null (1) 之前没有数据 (2) 没有找到替换的元素
// node是否为空,这个获取锁的是有关系的
// (1) node不为null,设置node的next为first
// (2) node为null,创建头节点,指定next为first
if (node != null)
// 底层使用 putOrderedObject 方法 具有volatile写语义
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
// 扩容条件 (1)entry数量大于阈值 (2) 当前table的数量小于最大容量 满足以上条件就扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
// 扩容方法,方法里面具体讲
rehash(node);
else
// 给table的index位置设置为node,
// node为头结点,原来的头结点first为node的next节点
// 底层也是调用的 putOrderedObject 方法 具有volatile写语义
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}4 扩容数组。算法类似HashMap，当素组元素个数>阈值（数组长度*负载因子）时将容量扩大到原来的2被，此时元素的都需要重新计算数组下标。
5 get新元素。get方法没有加锁，原因是segment的数组使用了volatile修饰，而且HashEntry的的属性（value和next）也都是volatile，其余（hash和k）为final，确保了读取的是最新的数据。
jdk1.8
1 底层和HashMap即为相似都是数组搭配链表和红黑树。
2 线程安全通过Synchronized和CAS（compare and set）java线程知识梳理实现。
3 添加对象。
3.1 第一次put会现初始化table数组。
3.2 通过hash计算出数组的下表，如果没有元素则通过cas添加，此时没有加锁。
3.3 如果该下表有元素，通过Node.hash == MOVED(MOVED == -1)判断是否处于数组扩容阶段，如果是则加入扩容复制元素任务中。
3.4 如果不在扩容阶段，则采用Synchronized对该下表的元素加锁进入链表或则红黑树的添加阶段。
3.5 添加完会判断链表或则数组长度。如果数组长度>阈值则扩容至原来的2倍，如果链表的长度>8且数组容量>64则将链表转红黑树。
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
75final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException(); //K,V都不能为空，否则的话跑出异常
int hash = spread(key.hashCode()); //取得key的hash值
int binCount = 0; //用来计算在这个节点总共有多少个元素，用来控制扩容或者转移为树
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //第一次put的时候table没有初始化，则初始化table
//通过哈希计算出一个表中的位置因为n是数组的长度，所以(n-1)&hash肯定不会出现数组越界
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果这个位置没有元素的话，则通过cas的方式尝试添加，注意这个时候是没有加锁的 。创建一个Node添加到数组中区，null表示的是下一个节点为空
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
/*
* 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
* 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
*/
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
/*
* 如果在这个位置有元素的话，就采用synchronized的方式加锁，
* 如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
* 如果找到了key和key的hash值都一样的节点，则把它的值替换到
* 如果没找到的话，则添加在链表的最后面
* 否则，是树的话，则调用putTreeVal方法添加到树中去
* 在添加完之后，会对该节点上关联的的数目进行判断，
* 如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
*/
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) { //再次取出要存储的位置的元素，跟前面取出来的比较
if (fh >= 0) { //取出来的元素的hash值大于0，当转换为树之后，hash值为-2
binCount = 1;
for (Node<K,V> e = f;; ++binCount) { //遍历这个链表
K ek;
//要存的元素的hash，key跟要存储的位置的节点的相同的时候，替换掉该节点的value即可
if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) //当使用putIfAbsent的时候，只有在这个key没有设置值得时候才设置
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) { //如果不是同样的hash，同样的key的时候，则判断该节点的下一个节点是否为空，
pred.next = new Node<K,V>(hash, key,value, null); //为空的话把这个要加入的节点设置为当前节点的下一个节点
break;
}
}
}
else if (f instanceof TreeBin) { //表示已经转化成红黑树类型了
Node<K,V> p;
binCount = 2;
//调用putTreeVal方法，将该元素添加到树中去
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) //当在同一个节点的数目达到8个的时候，则扩张数组或将给节点的数据转为tree
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); //计数
return null;
}4 扩容算法和HashMap一样
5 get对象。get没有使用Synchronized和cas控制。原因是 Node 的属性（value和next）也都是volatile，其余（hash和k）为final，确保了读取的是最新的数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
Linked<一种设计思想>
链表在物理内存上不连续也无序，通过元素的指针达到逻辑有序。
- 优点：增删快，时间都是O(1)；内存申请高效不需要连续地址。
- 缺点：查询比数组慢，时间是O(n)。
单链表
包含本身的数据外，还有一个指向下一个元素的引用。
1
2
3
4
5
6
7
8
9public class Node {
public Object data;
public Node next;
public Node(Object data,Node next){
this.data = data;
this.next = next;
}
}添加元素
1
2
3
4
5
6
7
8
9
10
11public void add(Object data){
Node temp = this.last;
Node current = new Node(data,null)
this.last = current;
if(temp == null){ // 说明此时添加的是第一个节点
this.first = current;
}else{
temp.next = current;
}
this.size ++;
}元素获取
1
2
3
4
5
6
7
8
9
10
11// 获取列表中第index个元素
public Node get(int index){
if(index > this.size-1){
return null;
}
Node temp = this.first;
for(int i =0; i<index ;i++ ){
temp = temp.next;
}
return temp;
}
双链表
包含本身数据外，还有2个引用，一个指向前一个节点，一个指向后一个节点。
1
2
3
4
5
6
7
8
9
10
11public class Node {
public Object data;
public Node prev;
public Node next;
public Node(Object data,Node next,Node prev){
this.data = data;
this.next = next;
this.prev = prev;
}
}添加元素
1
2
3
4
5
6
7
8
9
10
11public void add(Object data){
Node temp = this.last;
Node current = new Node(data,null,temp) // Node(Object data,Node next,Node prev)
this.last = current;
if(temp == null){ // 说明此时添加的是第一个节点
this.first = current;
}else{
temp.next = current;
}
this.size ++;
}元素获取
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19// 获取列表中第index个元素，因为是双链表可以从后向前查询，所以当index>(size>>1)时，从last开始向前迭代
public Node get(int index){
if(index > this.size-1){
return null;
}
Node temp;
if(index<(this.size>>1)){
temp = this.first;
for(int i =0; i<index ;i++ ){
temp = temp.next;
}
}else{
temp = this.last;
for(int i =0; i>-1 ;i-- ){
temp = temp.prev;
}
}
return temp;
}
树结构
二叉树
二叉的排序树
- 左子树上所有节点的值均小于它的根节点的值;
- 右子树上所有节点的值均大于它的根节点的值。
平衡二叉树（AVL）
二叉排序树因为插入的顺序有可能编程一个链表(比如顺序为1、2、3)，为了避免此情况发生而出现了平衡二叉树
- 要求两个子树的高度差不能超过1;
- 每次增删都会通过一次或多次旋转来平衡二叉树。
- 1 插入到不平衡节点左子树的左边需要RR（右旋）
- 2 插入到不平衡节点又子树的右边需要LL（左旋）
- 3 插入到不平衡节点左子树的右边需要LR（先左再右旋）
- 4 插入到不平衡节点右子树的左边需要RL（先右再左旋）
红黑树（R-B Tree）
在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。在大量增删的情况下平衡二叉树因为需要保持左右树高度差不能超过1，所以需要频繁旋转。
红黑树就称为了首选（最多3此旋转）。Java集合中的TreeSet和TreeMap，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
- 节点要么黑要么红；
- 根节点一定时黑色；
- 所有叶节点都为null，且为黑色；
- 红色节点的两个子节点都为黑色，不会有两个连续的红；
- 任意一个路径上的黑节点数，一定时相等的。（保证查询和平衡二叉树效率一样，算是不严格的平衡二叉树）
参考
多路叉树
B-Trees（平衡多路查找树，b为balance）
主要使用在文件系统中。
- 每个节点最多有m个孩子。
- 除了根节点和叶子节点外，其它每个节点至少有Ceil(m/2)个孩子。
- 若根节点不是叶子节点，则至少有2个孩子
- 所有叶子节点都在同一层，且不包含其它关键字信息
- 每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn）
- 关键字的个数n满足：ceil(m/2)-1 <= n <= m-1
- ki(i=1,…n)为关键字，且关键字升序排序。
- Pi(i=1,…n)为指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于k(i-1)
B+Trees
所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息；实现文件索引结构方面比B树使用得更普遍
- 非叶子节点只存储键值信息。
- 所有叶子节点之间都有一个链指针。
- 数据记录都存放在叶子节点中。
栈(先进后出)
栈的数据结构具有先进后出的特点（FILO first in last out），一般是通过数组加上业务控制模拟。
队列（队列先进先出）
队列数据结构具有先进先出的特点（FIFO），通过peek可以访问第一个元素，通过poll可以访问并删除第一个元素。
单端队列
单端队列从末尾来添加、删除元素。通过offer将元素放到尾部。
- PriorityQueue
PriorityQueue是一个比较标准的队列实现类，它会根据元素的大小排列（元素不能为null），所以其实不是FIFO。
双端队列（Deque extends Queue）
双端队列可以同时从两端来添加、删除元素。通过push将元素押入头部，通过offer将元素放到尾部。
ArrayDeque
底层通过数组实现，可以通过numElement指定长度，默认是16。LinkedList
参考List部分。
android特定的数据结构
Map部分
ArrayMap（获取key的hash值时做了判空处理，所以key可为null）
ArrayMap底层有2个数组，一个用来存储Key的HashCode（是有序存储），另一个用来存储Key和Value，所以第二个数组的长度是第一个数组的2倍。
添加数据（分为put和append，append作用于插入元素的HashCode大于数组中现有的值时，否则内部依然会调用put）
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
49public V put(K key, V value) {
final int hash;
int index;
if (key == null) {//key为空时，取hash值为定值0
hash = 0;
index = indexOfNull();
} else {
//根据mIdentityHashCode判断是否使用固定的hash值
hash = mIdentityHashCode ? System.identityHashCode(key) : key.hashCode();
index = indexOf(key, hash);//通过hash值计算下标值,最终也是使用的二分查找
}
if (index >= 0) {//如果找到了，说明之前已经put过这个key值了，这时直接覆盖对应value值
//mHashes数组中的index值，对应的value值在mArray中index*2+1处
index = (index<<1) + 1;
final V old = (V)mArray[index];//记录旧值
mArray[index] = value;//覆盖旧值，增加新的value值
return old;
}
//如果index<0，也就是没有根据key的hash值在mhashes数组中找到对应的下标值
index = ~index;//哇，经典复现！！！（具体SparseArray里才讲过）获取key的hash值要插入的位置
if (mSize >= mHashes.length) {//如果数组容量已满
//获取扩容的大小，这个就是一个稍显复杂的三目运算符，应该--问题不大！就不赘述了，嘿嘿
final int n = mSize >= (BASE_SIZE*2)?(mSize+(mSize>>1)):(mSize >= BASE_SIZE?(BASE_SIZE*2):BASE_SIZE);
//接下来这三步，进行了allocArrays一个操作，我们暂且不管，放一放，待会再来收拾它
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
allocArrays(n);
//将旧的数组赋值给进行allocArrays操作之后的数组
if (mHashes.length > 0) {
if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//进行一个叫freeArrays的操作，我们和allocArrays一样，待会再来收拾它
freeArrays(ohashes, oarray, mSize);
}
//如果待插入的位置小于mSize,则需要将mHashes数组index的位置空出来，相应的后面元素后移
//同时mArray数组中index*2和index*2+1这两个位置也要空出来，相应的后面的元素后移
if (index < mSize) {
System.arraycopy(mHashes, index, mHashes, index + 1, mSize - index);
System.arraycopy(mArray, index << 1, mArray, (index + 1) << 1, (mSize - index) << 1);
}
//呼！终于可以进行插入操作了
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
mSize++;
return null;
}添加、删除元素出发的数组容量维护（ArrayMap的缓存机制）。
大致逻辑将数组的0下标位指向上一个混存数组，数组的1下标位指向当前hashCode数组，其他位置置空。这样形成一个缓存数组链表。
每次扩容为BASE_SIZE/BASE_SIZE*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// 缓存数组
private static void freeArrays(final int[] hashes, final Object[] array, final int size) {
//参数hashes数组对应mHashes数组 参数array数组对应mArray数组 size代表容器元素数量
if (hashes.length == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {//防止多线程不同步
//如果没有达到缓存数量上限
if (mTwiceBaseCacheSize < CACHE_SIZE) {
array[0] = mTwiceBaseCache;//将array的第一个元素指向缓存数组
array[1] = hashes;//将array的第二个元素指向hashes数组
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;//将从下标2起始的位置，全部置空，释放空间
}
//将缓存数组指向设置完毕的array数组
//也就是将array数组添加到缓存数组的链表头
mTwiceBaseCache = array;
mTwiceBaseCacheSize++;//缓存完毕，缓存数组的数量加一
}
}
} else if (hashes.length == BASE_SIZE) {//完全一样的逻辑，同上
synchronized (ArrayMap.class) {
if (mBaseCacheSize < CACHE_SIZE) {
array[0] = mBaseCache;
array[1] = hashes;
for (int i=(size<<1)-1; i>=2; i--) {
array[i] = null;
}
mBaseCache = array;
mBaseCacheSize++;
}
}
}
}
// 分配容量（获取混存数组）
private void allocArrays(final int size) {
//mHashes数组容量为0，直接抛出异常
//EMPTY_IMMUTABLE_INTS这个值是mHashes数组的初始值,是一个大小为0的int数组
//直接写mHashes.length==0不好吗，真是一个奇怪的作者，莫非暗藏玄机？暂且留作疑问
if (mHashes == EMPTY_IMMUTABLE_INTS) {
throw new UnsupportedOperationException("ArrayMap is immutable");
}
//如果大小为BASE_SIZE*2=8，这时缓存使用mTwiceBaseCache数组来缓存
if (size == (BASE_SIZE*2)) {
synchronized (ArrayMap.class) {//防止多线程操作带来的不同步
if (mTwiceBaseCache != null) {
final Object[] array = mTwiceBaseCache;
//将mArray指向mTwiceBaseCache（相当于缓存链表的头指针）
//初始化mArray的大小（其实里面0号位置和1号位置也有数据，只不过没有意义）
mArray = array;
//将mTwiceBaseCache的指针指向头节点数组的0号元素，也就是指向第二个缓存数组
mTwiceBaseCache = (Object[])array[0];
//获取头节点数组array的1号元素指向的hash值数组，并赋给mHashes数组
mHashes = (int[])array[1];
//将mTwiceBaseCache缓存链表的头节点0号元素和1号元素置空，释放
array[0] = array[1] = null;
//缓存数组的数量减一
mTwiceBaseCacheSize--;
return;//结束
}
}
} else if (size == BASE_SIZE) {//使用mBaseCache数组来缓存，同上
synchronized (ArrayMap.class) {
if (mBaseCache != null) {
final Object[] array = mBaseCache;
mArray = array;
mBaseCache = (Object[])array[0];
mHashes = (int[])array[1];
array[0] = array[1] = null;
mBaseCacheSize--;
return;//结束
}
}
}
//如果size既不等于BASE_SIZE，也不等于BASE_SIZE*2
//那么就new新的数组来初始化mHashes和mArray，里面数据均为空，相当于没有使用缓存
mHashes = new int[size];
mArray = new Object[size<<1];
}获取数据。通过二分法查找hashCode数组下标index，第二个数组对应的key和value下标就是index<<1和index<<1+1。
1
2
3
4
5public V get(Object key) {
final int index = indexOfKey(key);//二分查找获取下标
//mHashes数组中index位置对应mArray中index*2+1的位置，使用位移操作以提高效率
return index >= 0 ? (V)mArray[(index<<1)+1] : null;
}删除元素。删除后当元素个数低于数组长度的1/3，并且数组的长度大于BASE_SIZE*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
62public V removeAt(int index) {
final Object old = mArray[(index << 1) + 1];//又是神秘操作，待会再看用来干嘛的
if (mSize <= 1) {//如果数组为空或者只有一个元素，那么直接将数组置空即可
freeArrays(mHashes, mArray, mSize);//又看到这个待会要收拾的方法了
mHashes = EmptyArray.INT;//置空，INT为一个大小为0的int数组
//奇怪的作者为什么要使用这个置空方法，是因为简洁嘛？真想问问他
mArray = EmptyArray.OBJECT;//置空,OBJECT为一个大小为0的Object数组
mSize = 0;//数组大小置0
} else {
//当数组长度大于BASE_SIZE*2=8并且当前元素数量小于总容量的1/3时
if (mHashes.length > (BASE_SIZE*2) && mSize < mHashes.length/3) {
// 嘿嘿，通过下面的英文注释，可以看到下面的操作是在干嘛了
// Shrunk enough to reduce size of arrays. We don't allow it to
// shrink smaller than (BASE_SIZE*2) to avoid flapping between
// that and BASE_SIZE.
//翻译过来就是，收缩足够的空间来减少数组大小，也就是说这样是为了避免连续
//删除元素导致大量无用内存，这些内存需要及时释放,以提高内存效率
//（哎，再感叹一次，为了一点点点点的内存，设计人员真的是煞费苦心啊）
//但是注释里也说了，还要控制数组不能收缩到小于8的值，以避免“抖动”
//这个抖动我本来想具体解释下的，但是我感觉这个东西完全可以意会，我就不言传了
//所以就留给你们自己感受这个“抖动”吧！哈哈
//计算新的容量，如果大于8，那么就收缩为当前元素数量的1.5倍，否则，就置为8
final int n = mSize > (BASE_SIZE*2) ? (mSize + (mSize>>1)) : (BASE_SIZE*2);
//保存当前数组的值
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//又看到allocArrays这个方法了，嘿嘿，现在我们知道他是干嘛的了
allocArrays(n);//浓缩成一句话：复用内存以初始化mHashes数组和mArray数组
//数组元素减一
mSize--;
//如果删除的下标index值大于0，则赋值以恢复mHashes和mArray数组index之前的数据
if (index > 0) {
//将之前保存的数组的值赋值给初始化之后的mHashes和mArray数组，恢复数据
//但是注意到第五个参数index，表示这一步只是赋值了删除元素index之前的数据
if (DEBUG) Log.d(TAG, "remove: copy from 0-" + index + " to 0");
System.arraycopy(ohashes, 0, mHashes, 0, index);
System.arraycopy(oarray, 0, mArray, 0, index << 1);
}
//如果index小于容器元素数量，则赋值index之后的数据
if (index < mSize) {
//对mHashes数组和mArray数组作前移操作，前移index位置以后的元素
System.arraycopy(ohashes, index + 1, mHashes, index, mSize - index);
//当然对mArray来说，就是前移index*2+2之后的数据元素
System.arraycopy(oarray, (index + 1) << 1, mArray, index << 1, (mSize - index) << 1);
}
} else {//当前数组容量<8或者大于总容量的1/3时，不需要收缩数组容量
mSize--;//直接减小1
if (index < mSize) {
//前移index之后的元素
System.arraycopy(mHashes, index + 1, mHashes, index, mSize - index);
//前移index*2+2之后的元素
System.arraycopy(mArray, (index + 1) << 1, mArray, index << 1, (mSize - index) << 1);
}
//前移后，最后一个元素空出来了，及时置空，以释放内存
mArray[mSize << 1] = null;
mArray[(mSize << 1) + 1] = null;
}
}
//呼！分析完了
return (V)old;
}优缺点
- 优点：内存利用率高，具有空间压缩机制。虽然二分法查询效率相比map底，但是通过索引迭代效率却高过map。
- 缺点：存取复杂度高。二分法查找比map底。没有实现Serializable，不利于bundle传输。
SparseArray
底层采用双数组分别存储key和value，key只能是int类型存储时会排序。采用SparseArray相比map可以提高内存使用效率，针对移动开发来说很有用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22public class SparseArray<E> implements Clonable{
private boolean mGarbage = false; // 是否需要调用gc();
private int[] mKeys; // 存储key
private Object[] mValues; // 存储value
private int mSize; // 数组中元素的个数
//
public SparseArray() {
this(10);
}
//
public SparseArray(int initialCapacity) {
if (initialCapacity == 0) {
mKeys = EmptyArray.INT;
mValues = EmptyArray.OBJECT;
} else {
mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
mKeys = new int[mValues.length];
}
mSize = 0;
}
}添加元素
SparseArray添加元素有2个方法put和append，当元素的key大于数组中的key时使用append，否则append会调用put。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
87public void put(int key, E value) {
//利用二分查找，找到 待插入key 的 下标index
int i = ContainerHelpers.binarySearch(mKeys, mSize, key);
//如果返回的index是正数，说明之前这个key存在，直接覆盖value即可
if (i >= 0) {
mValues[i] = value;
} else {
//若返回的index是负数，说明 key不存在.
//先对返回的i取反，得到应该插入的位置i
i = ~i;
//如果i没有越界，且对应位置是已删除的标记，则复用这个空间
if (i < mSize && mValues[i] == DELETED) {
//赋值后，返回
mKeys[i] = key;
mValues[i] = value;
return;
}
//如果需要GC，且需要扩容
if (mGarbage && mSize >= mKeys.length) {
//先触发GC
gc();
//gc后，下标i可能发生变化，所以再次用二分查找找到应该插入的位置i
// Search again because indices may have changed.
i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
}
//插入key（可能需要扩容）
mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
//插入value（可能需要扩容）
mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
//集合大小递增
mSize++;
}
}
// 二分法查找写的比较艺术
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // 找到了
}
}
return ~lo; // 没找到
}
// gc将标记为DELETE的位置释放出来
private void gc() {
//奇怪的作者没有删掉注释，代码强迫症的我好想给他把这句日志的注释删掉，但是没有权限，嘤嘤嘤！
// Log.e("SparseArray", "gc start with " + mSize);
int n = mSize;//压缩前数组的容量
int o = 0;//压缩后数组的容量，初始为0
int[] keys = mKeys;//保存新的key值的数组
Object[] values = mValues;//保存新的value值的数组
for (int i = 0; i < n; i++) {
Object val = values[i];
if (val != DELETED) {//如果该value值不为DELETED，也就是没有被打上“删除”的标签
if (i != o) {//如果前面已经有元素打上“删除”的标签，那么 i 才会不等于 o
//将 i 位置的元素向前移动到 o 处,这样做最终会让所有的非DELETED元素连续紧挨在数组前面
keys[o] = keys[i];
values[o] = val;
values[i] = null;//释放空间
}
o++;//新数组元素加一
}
}
//回收完毕，置为false
mGarbage = false;
//回收之后数组的大小
mSize = o;
//哼！，这里的注释也没删
// Log.e("SparseArray", "gc end with " + mSize);
}获取元素
删除元素
优缺点
- 优点：内存利用率高，具有”gc”机制。频繁插入删除效率高，有延迟删除机制。
- 缺点：二分法查找效率低于map。key只能是int或者long。
结构体部分
Pair
- Pair用于存储一组对象的数据结构，内部是两个final类型的first和second属性。
- equals通过值比较，判断first和second的值。
- 利用Pair和List结合，形成类似Map的效果。
