JDK源码-Map系列
2017-08-17 本文已影响31人
薛云龙
Map
- 类图
TreeMap实现
-
TreeMap是通过红黑树进行的,红黑树能够保证在最坏的情况,基本的动态集合操作的时间复杂度为O(lgn);
-
TreeMap是根据键的自然顺序进行排序的,或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。
-
TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。另外，TreeMap是非同步的。 它的iterator 方法返回的迭代器是fail-fastl的。
-
jdk里边的实现分析请看这篇文章Java提高篇（二七）-----TreeMap, Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例由于红黑树这部分太过复杂,需要好好研究之后再给大家分享.
HashMap实现
- 它是基于哈希表的Map接口的实现.了解hashMap前先看下hashcode的定义:
hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点，例如，java.util.Hashtable 提供的哈希表。
hashCode 的常规协定是：
在 Java 应用程序执行期间，在同一对象上多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是对象上 equals 比较中所用的信息没有被修改。从某一应用程序的一次执行到同一应用程序的另一次执行，该整数无需保持一致。
如果根据 equals(Object) 方法，两个对象是相等的，那么在两个对象中的每个对象上调用 hashCode 方法都必须生成相同的整数结果。
以下情况不 是必需的：如果根据 equals(java.lang.Object) 方法，两个对象不相等，那么在两个对象中的任一对象上调用 hashCode 方法必定会生成不同的整数结果。但是，程序员应该知道，为不相等的对象生成不同整数结果可以提高哈希表的性能。
实际上，由 Object 类定义的 hashCode 方法确实会针对不同的对象返回不同的整数。（这一般是通过将该对象的内部地址转换成一个整数来实现的，但是 JavaTM 编程语言不需要这种实现技巧。）
当equals方法被重写时，通常有必要重写 hashCode 方法，以维护 hashCode 方法的常规协定，该协定声明相等对象必须具有相等的哈希码。
- 总结来说:
如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；
如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；
两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。
- HashMap有几个重要的属性:table, size, threshold, loadFactor, modCount。
table:
存储Entry对象的数组,Node对象实现了Entry.在必要的时候,会进行扩容.Node对象本身是一个内嵌链表.
transient Node<K,V>[] table;
size:
map包含数据的个数
transient int size;
modcount:
map被修改的次数,用来实现fail-fast机制
transient int modCount;
threshold:
阈值，用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子"，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
int threshold;
loadFactor:
map的负载因子
final float loadFactor;
看一下Node的定义:它继承了Map中的Entry接口,定义了key,value,下一个节点的引用,以及hash值.由此及上文的Node数组,HashMap底层是一个数组,每一个数组的元素都是一个单向链表.
class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
那么问题来了:数组下表对应的Key的hash值,hash值一般都很大,那数组也要那么大吗?
Key的hash算法如下:纳莫,通过下文中的扰动函数得到一个hash,再通过数组大小逻辑与hash:
(n - 1) & hash
得到数组下标.
参考文章JDK 源码中 HashMap 的 hash 方法原理是什么？
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-
设计理念:
HashMap进行存储的时候,将key进行hash散列为一个int值,将int值设为底层数组的下标,将key的hash值相同的Entry存入到该元素的链表上.
那么通过key进行查找的时候,就可以通过key的hash值,先去数组找到对应元素,再通过元素寻找Entry; -
HashMap 扩容方法
final Node<K,V>[] resize() {
//原始的table
Node<K,V>[] oldTab = table;
//原始table的大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//原始table的阈值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果原来table的大小大于定义的最大容量1 << 30(2^30),将阈值设为计算机能标识的最大整数
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果原始table的大小的二倍小于默认的最大容量,并且大于默认的最小容量,则将阈值翻倍并返回
newThr = oldThr << 1; // double threshold
}else if (oldThr > 0)
//如果原来的table大小等于0且原始阈值大于0,那么,table的大小赋值为原始阈值
newCap = oldThr;
else {
// 如果原始阈值不大于0,且原始table容量不大于0
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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"})
//通过新的table容量创建table
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//将原来的table数据copy到新建的table中
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)
//如果当前节点是TreeNode,那么就通过红黑树存入.
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//循环copy
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;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
LinkedHashMap实现
-
LinkedHashMap在逻辑关系上是通过外层的链表控制,空间关系上仍然是通过和HashMap一样的hash桶进行存储,
-
LinkedHashMap是基于HashMap的一个实现,它保证了HashMap元素没有的有序性,LinkedHashMap可以让元素实现两种有序的方式:当AccessOrder=true时,元素按照访问的先后顺序进行排序,AccessOrder=false时,元素按照插入的顺序进行排序.它是由双向链表+hashmap实现的.
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
-
LinkedHashMap如何基于HashMap进行的扩展?
通过查看源码,LinkedHashMap进行的时候,并没有重写hashMap的put,remove等方法,那么怎么保证LinkedHashMap的put和remove操作不同于HashMap.原因就是这三个方法:
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
HashMap在实现putVal,remove等方法的时候,调用了这几个空方法.这样LinkedHashMap通过重载这几个方法,来实现了自己的一些逻辑.
- 从afterNodeInsertion(boolean evict)看出的LinkedHashMap对外提供的扩展的接口.
void 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;
}
- 外部通过重载方法removeEldestEntry(),可以自定义移除老元素的规则.如LruCache一样的扩展实现
public class LRUCache2<K, V> extends LinkedHashMap<K, V> {
private final int MAX_CACHE_SIZE;
public LRUCache2(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_CACHE_SIZE;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (Map.Entry<K, V> entry : entrySet()) {
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
}
- LinkedHashMap的迭代
LinkedHashMap是对Array与Link的折衷处理，Array与Link可以说是两个速度方向的极端，Array注重于数据的获取，而处理修改（添加/删除）的效率非常低；Link由于是每个对象都保持着下一个对象的指针，查找某个数据需要遍历之前所有的数据，所以效率比较低，而在修改操作中比较快。
