JAVA中其它常用集合原理分析

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.总结

这几章学习了常用的数据结构及其底层的实现,也对特定场景下几种数据结构的实现进行了简单的分析,每种数据结构都有其场景下的优势,使用合适的数据结构,能帮助我们写出性能优良的程序