本文共 10078 字,大约阅读时间需要 33 分钟。
接前一篇博文,继续探析Map接口的实现类。
Map|------HashTable| |-------WeakHashTable|------HashMap| |-------LinkedHashMap|------TreeMap|------WeakHashMap
HashTable不但实现了Map接口,同时继承自Dictionary类。其中Dictionary类是任何可将键映射到相应值的类(如 Hashtable)的抽象父类。每个键和每个值都是一个对象。在任何一个 Dictionary 对象中,每个键至多与一个值相关联。Map是”key-value键值对”接口。
//同HashMap,用于存储键值对 private transient Entry[] table; //同HashMap的size属性,保存键值对的数量 private transient int count; //hash调整的阈值 private int threshold; //平衡因子,同HashMap,默认值为0.75f private float loadFactor; //默认阈值 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; //数组最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
HashTable提供如下四种初始化方法:
public Hashtable(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load: "+loadFactor); if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; table = new Entry[initialCapacity]; threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1); initHashSeedAsNeeded(initialCapacity); } public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); } public Hashtable() { this(11, 0.75f); } public Hashtable(Map t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }
可以看出,HashTable的默认初始容量为11,默认的平衡因子为0.75f。其余部分于HashMap的初始化过程大同小异。
public synchronized V put(K key, V value) { // Make sure the value is not null if (value == null) { throw new NullPointerException(); } // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entrye = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } modCount++; if (count >= threshold) { // Rehash the table if the threshold is exceeded rehash(); tab = table; hash = hash(key); index = (hash & 0x7FFFFFFF) % tab.length; } // Creates the new entry. Entry e = tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; return null; } protected void rehash() { int oldCapacity = table.length; Entry [] oldMap = table; // overflow-conscious code int newCapacity = (oldCapacity << 1) + 1; if (newCapacity - MAX_ARRAY_SIZE > 0) { if (oldCapacity == MAX_ARRAY_SIZE) // Keep running with MAX_ARRAY_SIZE buckets return; newCapacity = MAX_ARRAY_SIZE; } Entry [] newMap = new Entry[newCapacity]; modCount++; threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1); boolean rehash = initHashSeedAsNeeded(newCapacity); table = newMap; for (int i = oldCapacity ; i-- > 0 ;) { for (Entry old = oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; if (rehash) { e.hash = hash(e.key); } int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = newMap[index]; newMap[index] = e; } } }
此方法带有synchronized关键字,表示此方法必须同步访问以此达到线程安全的目的;
新增Entry的key和value不能为null;
hash运算与HashMap有所区别,这里直接是自身hashcode与hash种子与运算;
获取Entry数组索引与HashMap不一样;
HashTable的扩容策略为原先容量的2倍加1,最大不超过默认最大值;
public synchronized V get(Object key) { Entry tab[] = table; int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entrye = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return e.value; } } return null; }
从代码中可以看出get方法,get方法被synchronized关键字修饰,也是线程安全的,计算Entry数组索引的方式与put方法一致,不再详细说明。
public synchronized V remove(Object key) { Entry tab[] = table; int hash = hash(key); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entrye = tab[index], prev = null ; e != null ; prev = e, e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { modCount++; if (prev != null) { prev.next = e.next; } else { tab[index] = e.next; } count--; V oldValue = e.value; e.value = null; return oldValue; } } return null; }
remove方法也是线程安全的,计算Entry数组索引的方式与put方法一致,删除的过程就是重新建立Entry引用的过程,不再详细说明。
WeakHashMap是以弱键实现的基于哈希表的 Map。在 WeakHashMap 中,当某个键不再正常使用时,将自动移除其条目。更精确地说,对于一个给定的键,其映射的存在并不阻止垃圾回收器对该键的丢弃,这就使该键成为可终止的,被终止,然后被回收。丢弃某个键时,其条目从映射中有效地移除。
//默认初始容量 private static final int DEFAULT_INITIAL_CAPACITY = 16; //最大容量 private static final int MAXIMUM_CAPACITY = 1 << 30; //默认平衡因子 private static final float DEFAULT_LOAD_FACTOR = 0.75f; //entry数组 Entry[] table; //引用队列 private final ReferenceQueue
从代码中可以看出,WeakHashMap的内部成员变量与HashMap绝大多数都是相似的,唯独多了一个ReferenceQueue类型的queue,用来保存被清理掉的WeakEntrys。
WeakHashMap提供如下四种构造方法:
public WeakHashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor); int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; table = newTable(capacity); this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); } public WeakHashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public WeakHashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } public WeakHashMap(Map m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); putAll(m); }
可以看出,jdk1.8以后WeakHashMap与HashMap的初始化逻辑基本一样,主要体现在初始化的时候数组长度的设置上。
WeakHashMap实现了Map接口,我们重点关注put、get、remove方法。我们先关注一个私有方法,代码如下:
private void expungeStaleEntries() { for (Object x; (x = queue.poll()) != null; ) { synchronized (queue) { @SuppressWarnings("unchecked") Entrye = (Entry ) x; int i = indexFor(e.hash, table.length); Entry prev = table[i]; Entry p = prev; while (p != null) { Entry next = p.next; if (p == e) { if (prev == e) table[i] = next; else prev.next = next; // Must not null out e.next; // stale entries may be in use by a HashIterator e.value = null; // Help GC size--; break; } prev = p; p = next; } } } }
代码的大致逻辑就是,遍历并删除queue中的元素,寻找是否有被清楚的key对象,如果有则在table中找到其值,并将value设置为null,让GC去回收这些资源。
public V put(K key, V value) { Object k = maskNull(key); int h = hash(k); //getTable方法会调用上述的expungeStaleEntries方法; Entry[] tab = getTable(); int i = indexFor(h, tab.length); for (Entry e = tab[i]; e != null; e = e.next) { if (h == e.hash && eq(k, e.get())) { V oldValue = e.value; if (value != oldValue) e.value = value; return oldValue; } } modCount++; Entry e = tab[i]; tab[i] = new Entry<>(k, value, queue, h, e); if (++size >= threshold) resize(tab.length * 2); return null; }
put方法在新增entry之前,先调用expungeStaleEntries方法清理持有弱引用的key,之后的处理跟HashMap相似,需要注意的是HashMap将null的entry固定在数组的第一个元素,而WeakHashMap并没有此限制。
public V get(Object key) { Object k = maskNull(key); int h = hash(k); //getTable方法会调用上述的expungeStaleEntries方法; Entry[] tab = getTable(); int index = indexFor(h, tab.length); Entry e = tab[index]; while (e != null) { if (e.hash == h && eq(k, e.get())) return e.value; e = e.next; } return null; } public V remove(Object key) { Object k = maskNull(key); int h = hash(k); Entry [] tab = getTable(); int i = indexFor(h, tab.length); Entry prev = tab[i]; Entry e = prev; while (e != null) { Entry next = e.next; if (h == e.hash && eq(k, e.get())) { modCount++; size--; if (prev == e) tab[i] = next; else prev.next = next; return e.value; } prev = e; e = next; } return null; }
WeakHashMap的get方法和remove方法会先调用expungeStaleEntries方法,之后的处理和HashMap类似,不再赘述。
笔者花了两篇博文介绍了常用Map实现类的具体实现逻辑,更为复杂的实现类,比如TreeMap后续会有详细的介绍,希望能帮助读者对于Map有更深入的理解。
转载地址:http://psgmi.baihongyu.com/