Map学习

算法与数据结构

目录

  1. HashMap
  2. WeakHashMap
  3. 线程安全的Map
    1. 1. HashTable/Collections.synchronizedMap()
    2. 2. ConcurrentHashMap
  4. Android特有Map
    1. ArrayMap
    2. SparseArray

HashMap

以Java1.8源码为准，其数据结构如下：

  • 默认值
常量名 解释 默认值
DEFAULT_INITIAL_CAPACITY 初始容量 1 << 4(16)
MAXIMUM_CAPACITY 最大容量 1 << 30
DEFAULT_LOAD_FACTOR 负载系数 0.75
TREEIFY_THRESHOLD 超过该值的链表改用红黑树存储 8
UNTREEIFY_THRESHOLD resize时,如果红黑树存储的节点数小于该值则使用链表存储 6
MIN_TREEIFY_CAPACITY 链表节点数大于8个时，先判断当前存储的mapping数是否大于该值，如果小于则resize，大于则改用红黑树 64
  • Node

  1. hash如何求？ 

    1
    2
    3
    4
    HashMap#hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

  2. table大小是2^n,好处是求下标: (table.length - 1) & hash

  3. 如果超过负载系数x容量，则resize();其原理图:

}

4. 允许key/value为null,非线程安全

5. HashSet底层实现是HashMap,key是集合元素e，value是dummy object

## LinkedHashMap

继承HashMap,底层通过双向链表存储顺序;排序方式有两种:

  • 根据写入顺序排序
  • 根据访问顺序排序

通过accessOrder成员变量标识，其中根据访问顺序排序时，每次 get 都会将访问的值移动到链表末尾，通过该性质可以实现LruCache

WeakHashMap

与HashMap类似,不同之处在Key是弱引用的,实现关键是

1
private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {...}

在get/put等操作中会首先调用expungeStaleEntries(),根据ReferenceQueue清除无用的Entry

线程安全的Map

1. HashTable/Collections.synchronizedMap()

线程安全，采用synchronized方法上加锁，使用阻塞同步，效率低

2. ConcurrentHashMap

数据结构与HashMap相同,采用CAS(CompareAndSwap,原子操作)和synchronized保证并发安全,CAS用于Entry数组指定位置第一个节点的插入，synchronized用于锁定当前链表或红黑二叉树的首节点

Android特有Map

ArrayMap

ArrayMap是Android专门针对内存优化而设计的，用于取代Java API中的HashMap数据结构。其数据结构如下:

  • 采用两个数组存储: mHashes存储key的hash值,按增序存储,通过二分查找指定key值的数组下标;根据mHashes指定下标在mArray中访问key/value. 内存使用相比HashMap节省，查找时间复杂度O(logN),并且增加/删除时需要数组copy，速度相对较慢，size小于1k时基本可以忽略。

  • 相比HashMap：ArrayMap在容量满的时机触发容量扩大至原来的1.5倍，在容量不足1/3时触发内存收缩，更节省内存；有缓存机制，避免频繁创建对象而分配内存与GC操作

  • 非线程安全

SparseArray

SparseArray是Android针对key为int而设计的Map,注意该类并没有实现Map接口。其数据结构如下:

  • 相比HashMap: 数组存储节省内存，因无需对int进行装箱操作，size较小时性能较好

  • 非线程安全

  • SparseIntArray、SparseBooleanArray、SparseLongArray与SparseArray类似，唯一区别是指定value类型，其value无需装箱