Java知识点<14>Map 之 HashMap, TreeMap,ConcurrentHashMap,ArrayMap
1. HashMap
1.1 基本概念
1.1.1 HashMap 是一个散列表,它存储的内容是键值对(key-value)映射。
1.1.2 HashMap<K,V>extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
1.1.3 HashMap 的实现不是同步的,这意味着它不是线程安全的
1.1.4 HashMap 的实例有两个参数影响其性能:“初始容量” 和 “加载因子”.
初始容量 只是哈希表在创建时的容量
-> static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时,则要对该哈希表进行 rehash 操作(即重建内部数据结构),从而哈希表将具有大约两倍的桶数。
-> static final float DEFAULT_LOAD_FACTOR = 0.75f;
1.2 HashMap 的数据结构
实际上 HashMap的实现,是一个Entry数组,然后每个Entry元素又是一个单向链表。HashMap是以这种数据结构来解决hash碰撞的。在使用HashMap的时候,需要根据自己的实际情况来判断是否重写equals 和 hashcode方法 。
因为也是以数组的形式存在,所以扩容的时候,和Arraylist是一样的,需要开辟一个更大的空间,然后copy老数据。但是扩容的方式是不一样的,当hashmap的使用达到初始容量*加载因子的时候,HashMap 是直接扩展到原先的2倍。
1.3 主要的对外方法
1.3.1 clear() :clear() 的作用是清空HashMap。它是通过将所有的元素设为null来实现的。
1.3.2 containsKey() containsKey() 的作用是判断HashMap是否包含key。
1.3.3 containsValue() containsValue() 的作用是判断HashMap是否包含“值为value”的元素。
注意: 在hashset的方法中是contains方法,因为set不存在相同的元素,所以不用区分 key 和 value
1.3.4 entrySet()、values()、keySet()
entrySet()的作用是返回“HashMap中所有Entry的集合”,它是一个集合。当我们通过entrySet()获取到的Iterator的next()方法去遍历HashMap时,实际上调用的是 nextEntry() 。而nextEntry()的实现方式,先遍历Entry(根据Entry在table中的序号,从小到大的遍历);然后对每个Entry(即每个单向链表),逐个遍历。
1.3.5 get() get() 的作用是获取key对应的value,
1.3.6 put() put() 的作用是对外提供接口,让HashMap对象可以通过put()将“key-value”添加到HashMap中。
注意 :
若要添加到HashMap中的键值对对应的key已经存在HashMap中,则找到该键值对;然后新的value取代旧的value,并退出!
若要添加到HashMap中的键值对对应的key不在HashMap中,则将其添加到该哈希值对应的链表中,并调用addEntry()。
1.3.7 putAll() 将"m"的全部元素都添加到HashMap中
1.3.8 remove() remove() 的作用是删除“键为key”元素
2. ConcurrentHashMap
2.1 背景
哈希表是中非常高效,复杂度为O(1),我们最常见到最频繁使用的就是HashMap和HashTable,但是在线程竞争激烈的并发场景中使用都不够合理。
HashMap :先说HashMap,HashMap是线程不安全的,在并发环境下,可能会形成环状链表(扩容时可能造成,具体原因自行百度google或查看源码分析),导致get操作时,cpu空转,所以,在并发环境中使用HashMap是非常危险的。
HashTable : HashTable和HashMap的实现原理几乎一样,差别无非是1.HashTable不允许key和value为null;2.HashTable是线程安全的。但是HashTable线程安全的策略实现代价却太大了,简单粗暴,get/put所有相关操作都是synchronized的,这相当于给整个哈希表加了一把大锁,多线程访问时候,只要有一个线程访问或操作该对象,那其他线程只能阻塞,相当于将所有的操作串行化,在竞争激烈的并发场景中性能就会非常差。
HashTable性能差主要是由于所有操作需要竞争同一把锁,而如果容器中有多把锁,每一把锁锁一段数据,这样在多线程访问时不同段的数据时,就不会存在锁竞争了,这样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的"分段锁"思想。
ConcurrentHashMap采用了非常精妙的"分段锁"策略,ConcurrentHashMap的主干是个Segment数组。
final Segment<K,V>[] segments;
Segment继承了ReentrantLock,所以它就是一种可重入锁(ReentrantLock)。在ConcurrentHashMap,一个Segment就是一个子哈希表,Segment里维护了一个HashEntry数组,并发环境下,对于不同Segment的数据进行操作是不用考虑锁竞争的。(就按默认的ConcurrentLeve为16来讲,理论上就允许16个线程并发执行,有木有很酷)
所以,对于同一个Segment的操作才需考虑线程同步,不同的Segment则无需考虑。
Segment类似于HashMap,一个Segment维护着一个HashEntry数组
transient volatile HashEntry<K,V>[] table;
HashEntry是目前我们提到的最小的逻辑处理单元了。一个ConcurrentHashMap维护一个Segment数组,一个Segment维护一个HashEntry数组。
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K,V> next;
//其他省略
}
我们说Segment类似哈希表,那么一些属性就跟我们之前提到的HashMap差不离,比如负载因子loadFactor,比如阈值threshold等等,看下Segment的构造方法
从上面的代码可以看出来,Segment数组的大小ssize是由concurrentLevel来决定的,但是却不一定等于concurrentLevel,ssize一定是大于或等于concurrentLevel的最小的2的次幂。比如:默认情况下concurrentLevel是16,则ssize为16;若concurrentLevel为14,ssize为16;若concurrentLevel为17,则ssize为32。为什么Segment的数组大小一定是2的次幂?其实主要是便于通过按位与的散列算法来定位Segment的index。
3. TreeMap (参考 : https://www.cnblogs.com/skywang12345/p/3310928.html)
3.1 基本概念
3.1.1 TreeMap<K,V> extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable
3.1.2 TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。
3.1.3 TreeMap基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的 Comparator 进行排序,具体取决于使用的构造方法。
3.1.4 TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。
3.1.5 TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fast的。
3.2 TreeMap的数据结构 -> 基于红黑树的
3.3 主要的对外方法 :
3.3.1 TreeMap的Entry相关函数
firstEntry()、 lastEntry()、 lowerEntry()、 higherEntry()、 floorEntry()、 ceilingEntry()、 pollFirstEntry() 、 pollLastEntry()
3.3.2 TreeMap的key相关函数
firstKey()、lastKey()、lowerKey()、higherKey()、floorKey()、ceilingKey()
3.3.3 values(), 返回“TreeMap中值的集合”
3.3.4 entrySet()函数 返回“键值对集合”。
3.3.5 顺序遍历和逆序遍历
由于TreeMap中的元素是从小到大的顺序排列的。因此,顺序遍历,就是从第一个元素开始,逐个向后遍历;而倒序遍历则恰恰相反,它是从最后一个元素开始,逐个往前遍历。
我们可以通过 keyIterator() 和 descendingKeyIterator()来说明!
keyIterator()的作用是返回顺序的KEY的集合,
descendingKeyIterator()的作用是返回逆序的KEY的集合。
因为很多操作涉及到红黑树(目前理解不是特别好),后续有时间,再多补充一些内容
-》红黑树请参考http://www.cnblogs.com/skywang12345/p/3245399.html , 感谢大神的分析
4. ArrayMap
4.1 存储方式 : ArrayMap的存储中没有Entry这个东西,他是由两个数组来维护的
[java] view plaincopy
int[] mHashes;
Object[] mArray;
mHashes数组中保存的是每一项的HashCode值,mArray中就是键值对,每两个元素代表一个键值对,前面保存key,后面的保存value,
4.2 扩容
//如果容量不够
s1 ize >= mHashes.length) {
final int n = mSize >= (BASE_SIZE*2) ? (mSize+(mSize>>1))
: (mSize >= BASE_SIZE ? (BASE_SIZE*2) : BASE_SIZE);
if (DEBUG) Log.d(TAG, "put: grow from " + mHashes.length + " to " + n);
final int[] ohashes = mHashes;
final Object[] oarray = mArray;
//分配数组
allocArrays(n);
if (mHashes.length > 0) {if (DEBUG) Log.d(TAG, "put: copy 0-" + mSize + " to 0");
//特别注意这,是copy,而不是new,效率提升
System.arraycopy(ohashes, 0, mHashes, 0, ohashes.length);
System.arraycopy(oarray, 0, mArray, 0, oarray.length);
}
//释放无用空间,收缩数组
freeArrays(ohashes, oarray, mSize);
}
ArrayMap用的是copy数据,所以效率相对要高。
4.3、ArrayMap提供了数组收缩的功能,在clear或remove后,会重新收缩数组,是否空间
4.4、ArrayMap采用二分法查找;