1.前言
前几章分析了常用数据结构底层实现,部分数据结构的实现还是比较复杂,需要花时间慢慢理解.这章继续了解特定场景的数据结构,他们基本上是某个数据结构的变种,为了实现每一特定功能或者提升时间或者空间效率而延伸出来的
2.目录
目录
3.常用集合
3.1.LinkedHashMap
在使用上,LinkedHashMap和HashMap的区别就是LinkedHashMap是有序的,
LinkedHashMap根据accessOrder决定是否在此基础上顺序访问数据
//table位置上连接entry的顺序的双向链表 头 最旧插入的数据
transient LinkedHashMapEntry<K,V> head;
//尾 最新插入的数据
transient LinkedHashMapEntry<K,V> tail;
//是否顺序访问
final boolean accessOrder;
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {
//在Node的基础上添加before和after两个指针
LinkedHashMapEntry<K,V> before, after;
LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
添加元素,通过Node新增的两个指针连接成双向链表
putMapEntries(m, false); //增添元素
-->putVal(hash(key), key, value, false, evict);
-->newNode(hash, key, value, null); //创建节点 调用的是LinkedHashMap
-->linkNodeLast(p);//将节点插入链尾
-->afterNodeAccess(e); //在节点被访问后移动链尾
LinkedHashMap存储结构
通过iterator遍历有序的原理,先访问新插入的数据
linkedHashMap.entrySet().iterator();
-->new LinkedEntrySet()
-->new LinkedEntryIterator()
-->next()
-->nextNode()
-->next = e.after; //获取后面的节点
LruCache算法,最近最少使用算法,底层使用的就是LinkedHashMap,新增或使用的元素都放置链尾
public class LRUCache extends LinkedHashMap {
protected int maxElements;
public LRUCache(int maxSize) {
super(maxSize, 0.75F, true);
maxElements = maxSize;
}
protected boolean removeEldestEntry(Map.Entry eldest) {
//当大小超出了Map的容量，就移除掉双向队列头部的元素
return size() > maxElements;
}
//将节点插入链尾
public V putCache(K key, V val) {
return put(key, val);
}
//将节点从缓存取出 放置链尾
public V getCache(K key) {
return get(key);
}
}
3.2. ConcurrentHashMap
ConcurrentHashMap 采用了分段锁技术(jdk1.8中放弃了Segment分段锁,采用CAS+synchronized来保证线程的安全,java并发再做深入分析),其中 Segment 继承于 ReentrantLock.不会像HashTable那样不管是 put 还是 get 操作都需要做同步处理,理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发.每当一个线程占用锁访问一个 Segment 时,不会影响到其他的 Segment()
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
//volatile修饰保证内存可见性
volatile V val;
volatile Node<K, V> next;
Node(int hash, K key, V val, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
...
}
Segment就是table的一个节点,内部维护了一个链表
如下是JDK1.7的Segment
static final class Segment<K,V> extends ReentrantLock implements Serializable {
//Segment中元素的数量
transient volatile int count;
//对table的大小造成影响的操作的数量
transient int modCount;
//阈值,Segment里面元素的数量超过这个值依旧就会对Segment进行扩容
transient int threshold;
//链表数组,数组中的每一个元素代表了一个链表的头部
transient volatile HashEntry<K,V>[] table;
//负载因子
final float loadFactor;
}
JDK1.7
JDK1.8
3.3.TreeMap
该集合是基于红黑树的 NavigableMap实现,最重要的特点就是可排序,根据映射的键自然顺序进行排序,,或者根据创建映射时提供的 Comparator 进行排序
public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable {
// 比较器对象
private final Comparator<? super K> comparator;
// 根节点
private transient Entry<K,V> root;
// 静态内部类用来表示节点类型
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; //
}
...
}
TreeMap元素插入
3.4.HashSet
HashSet的实现是基于HashMap的,是一个没有重复元素的集合,也不能保证元素的顺序,可以有null值,但最多只能有一个
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
static final long serialVersionUID = -5024744406713321676L;
//用HashMap保存HashSet的元素
private transient HashMap<E, Object> map;
//静态空的对象用于存储所有的value
private static final Object PRESENT = new Object();
public HashSet() {
//初始化HashMap
map = new HashMap<>();
}
}
HashSet底层原理完全就是包装了一下HashMap
3.5.Android中特有的数据结构
3.5.1.SparseArray
SparseArray有节约自动装箱开销的优点外(key为int,存在int[]中),还提到SparseArray因为少了需要Map.Entry<K, V>作为辅助的存储结构引入的内存开销
public class SparseArray<E> implements Cloneable {
//标注数据DELETED状态 并不执行实际删除操作
private static final Object DELETED = new Object();
//是否有标注DELETED的元素
private boolean mGarbage = false;
//存储key的int数组
private int[] mKeys;
//存储value的object数组(int 可以用SparseIntArray...)
private Object[] mValues;
//实际容量的大小
private int mSize;
}
SparseArray的存储结构
扩容,简单的说就是翻倍,没有缩容机制,只适用于少量数据和短期使用,大量数据场景下binarySearch操作数据(put时保证key有序)时会影响效率
public static int growSize(int currentSize) {
return currentSize <= 4 ? 8 : currentSize * 2;
}
3.5.2.ArrayMap
ArrayMap 实现了implements Map<K, V>接口,存储以key->value 结构形式的数据.它也是线程不安全的,允许key为null,value为null.它的内部实现是基于两个数组,一个int[]数组,用于保存每个item的hashCode值,一个Object[]数组,保存key/value键值对,对比HashMap,空间效率更高.
public final class ArrayMap<K, V> implements Map<K, V> {
//用于缓存大小为4的ArrayMap,超过10个则不再缓存
static Object[] mBaseCache;
//记录已经缓存的数目
static int mBaseCacheSize;
//用于缓存大小为8的ArrayMap,超过10个则不再缓存
static Object[] mTwiceBaseCache;
//记录已经缓存的数目
static int mTwiceBaseCacheSize;
//这个变量决定key的hash的生成方法
final boolean mIdentityHashCode;
//保存key的hash值的数组
int[] mHashes;
//保存key/value(前后连续存)的数组。
Object[] mArray;
//已经存放的元素的个数
int mSize;
}
ArrayMap的存储结构
- 初始化时,mArray是mHashes的容量的两倍
- mArray 在 hash code 的 index<<1 处存储 key,在 index<<1 + 1 处存储 value.简单点说就是偶数处存储 key,相邻奇数处存储 value
- 插入时,根据key的hash利用二分查找(hash排序)计算出index,index<0表示这个key不存在(那么就需要插入而且~index就是要插入的位置),否则表示key存在,需要把mArray保存的value覆盖更新下就行了(开放地址法解决hash冲突,冲突时查找下一个位置)
- 扩容时,如果容量大于8，则扩容一半(1.5倍)，否则容量大于4，则扩容到8，否则扩容到4
4.总结
这几章学习了常用的数据结构及其底层的实现,也对特定场景下几种数据结构的实现进行了简单的分析,每种数据结构都有其场景下的优势,使用合适的数据结构,能帮助我们写出性能优良的程序
网友评论