HashMap 及 HashTable 源码解析
[java] view plain copy
static?final?Entry<?,?>[]?EMPTY_TABLE?=?{};??
??/**?
???*?The?table,?resized?as?necessary.?Length?MUST?Always?be?a?power?of?two.?
???*/??
??transient?Entry<K,V>[]?table?=?(Entry<K,V>[])?EMPTY_TABLE;??
??/**?
???*?The?number?of?key-value?mappings?contained?in?this?map.?
???*/??
??transient?int?size;??
??/**?
???*?The?next?size?value?at?which?to?resize?(capacity?*?load?factor).?
???*?@serial?
???*/??
??//?If?table?==?EMPTY_TABLE?then?this?is?the?initial?capacity?at?which?the??
??//?table?will?be?created?when?inflated.??
??int?threshold;??
下面讲解几个比较重要的方法
1）当我们进行 put 操作的时候
先贴出源码
[java] view plain copy
public?V?put(K?key,?V?value)?{??
????????if?(key?==?null)??
????????????return?putForNullKey(value);?//处理 null 值??
????????int?hash?=?hash(key.hashCode());//计算 hash??
????????int?i?=?indexFor(hash,?table.length);//计算在数组中的存储位置??
????//遍历 table[i]位置的链表，查找相同的 key，若找到则使用新的 value 替换掉原来的 oldValue 并返回 oldValue??
????????for?(Entry<K,V>?e?=?table[i];?e?!=?null;?e?=?e.next)?{??
????????????Object?k;??
????????????if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?key.equals(k)))?{??
????????????????V?oldValue?=?e.value;??
????????????????e.value?=?value;??
????????????????e.recordAccess(this);??
????????????????return?oldValue;??
????????????}??
????????}??
????//若没有在 table[i]位置找到相同的 key，则添加 key 到 table[i]位置，新的元素总是在 table[i]位置的第一个元素，原来的元素后移??
????????modCount++;??
????????addEntry(hash,?key,?value,?i);??
????????return?null;??
????}??
a HashMap 会对 null 值 key 进行特殊处理，总是放到 table[0]位置
b 计算 has 值
c 找到在 table 数组中的索引
1）遍历 table[i
]位置的链表，查找相同的 key，若找到则使用新的 value 替换掉原来的 oldValue 并返回 oldValue
2）若没有在 table[i]位置找到相同的 key，则添加 key 到 table[i]位置，新的元素总是在 table[i]位置的第一个元素，原来的元素后调用 addEntry 方法
[java] view plain copy
void?addEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{??
????????if?((size?>=?threshold)?&&?(null?!=?table[bucketIndex]))?{??
????????????resize(2?*?table.length);??
????????????hash?=?(null?!=?key)???hash(key)?:?0;??
????????????bucketIndex?=?indexFor(hash,?table.length);??
????????}??
????????createEntry(hash,?key,?value,?bucketIndex);??
????}??
[java] view plain copy
void?createEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{??
????Entry<K,V>?e?=?table[bucketIndex];??
????table[bucketIndex]?=?new?Entry<>(hash,?key,?value,?e);??
????size++;??
}??
所做的工作就是：
1）判断当元素数量达到临界值(capactiy*factor)时，则进行扩容，是 table 数组长度变为 table.length*2
2）当 table[index]已存在其它元素时，会在 table[index]位置形成一个链表，将新添加的元素放在 table[index]，原来的元素通过 Entry 的 next 进行链接，这样以链表形式解决 hash 冲突问题，
**2）get 方法
**同样当 key 为 null 时会进行特殊处理，在 table[0]的链表上查找 key 为 null 的元素
[java] view plain copy
public?V?get(Object?key)?{??
???????if?(key?==?null)??
???????????return?getForNullKey();??
???????Entry<K,V>?entry?=?getEntry(key);??
???????return?null?==?entry???null?:?entry.getValue();??
???}??
get 的过程是先计算 hash 然后通过 hash 与 table.length 取摸计算 index 值，然后遍历 table[index]上的链表，直到找到 key，
然后返回，找不到返回 null
[java] view plain copy
final?Entry<K,V>?getEntry(Object?key)?{??
????????if?(size?==?0)?{??
????????????return?null;??
????????}??
????????int?hash?=?(key?==?null)???0?:?hash(key);??
????????for?(Entry<K,V>?e?=?table[indexFor(hash,?table.length)];??
?????????????e?!=?null;??
?????????????e?=?e.next)?{??
????????????Object?k;??
????????????if?(e.hash?==?hash?&&??
????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))??
????????????????return?e;??
????????}??
????????return?null;??
????}??
3）remove 方法
remove 方法和 put get 类似，计算 hash，计算 index，然后遍历查找，将找到的元素从 table[index]链表移除
[java] view plain copy
public?V?remove(Object?key)?{??
????????Entry<K,V>?e?=?removeEntryForKey(key);??
????????return?(e?==?null???null?:?e.value);??
????}??
[java] view plain copy
final?Entry<K,V>?removeEntryForKey(Object?key)?{??
????????if?(size?==?0)?{??
????????????return?null;??
????????}??
????????int?hash?=?(key?==?null)???0?:?hash(key);??
????????int?i?=?indexFor(hash,?table.length);??
????????Entry<K,V>?prev?=?table[i];??
????????Entry<K,V>?e?=?prev;??
????????while?(e?!=?null)?{??
????????????Entry<K,V>?next?=?e.next;??
????????????Object?k;??
????????????if?(e.hash?==?hash?&&??
????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))?{??
????????????????modCount++;??
????????????????size--;??
????????????????if?(prev?==?e)??
????????????????????table[i]?=?next;??
????????????????else??
????????????????????prev.next?=?next;??
????????????????e.recordRemoval(this);??
????????????????return?e;??
????????????}??
????????????prev?=?e;??
????????????e?=?next;??
????????}??
????????return?e;??
????}??
4）clear()方法
clear 方法非常简单，就是遍历 table 然后把每个位置置为 null，同时修改元素个数为 0
需要注意的是 clear 方法只会清楚里面的元素，并不会重置 capactiy
[java] view plain copy
public?void?clear()?{??
????????modCount++;??
????????Arrays.fill(table,?null);??
????????size?=?0;??
????}??
5）containsKey 和 containsValue
containsKey 方法是先计算 hash 然后使用 hash 和 table.length 取摸得到 index 值，遍历 table[index]元素查找是否包含 key 相同的值
[java] view plain copy
public?boolean?containsKey(Object?key)?{??
???????return?getEntry(key)?!=?null;??
???}??
[java] view plain copy
final?Entry<K,V>?getEntry(Object?key)?{??
????????if?(size?==?0)?{??
????????????return?null;??
????????}??
????????int?hash?=?(key?==?null)???0?:?hash(key);??
????????for?(Entry<K,V>?e?=?table[indexFor(hash,?table.length)];??
?????????????e?!=?null;??
?????????????e?=?e.next)?{??
????????????Object?k;??
????????????if?(e.hash?==?hash?&&??
????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))??
????????????????return?e;??
????????}??
????????return?null;??
????}??
6）containsValue 方法就比较粗暴了，就是直接遍历所有元素直到找到 value，由此可见 HashMap 的 containsValue 方法本质上和普通数组和 list 的 contains 方法没什么区别，你别指望它会像 containsKey 那么高效
[java] view plain copy
public?boolean?containsValue(Object?value)?{??
????????//?Same?idea?as?size()??
????????if?(value?==?null)??
????????????throw?new?NullPointerException();??
????????final?Segment<K,V>[]?segments?=?this.segments;??
????????boolean?found?=?false;??
????????long?last?=?0;??
????????int?retries?=?-1;??
????????try?{??
????????????outer:?for?(;;)?{??
????????????????if?(retries++?==?RETRIES_BEFORE_LOCK)?{??
????????????????????for?(int?j?=?0;?j?<?segments.length;?++j)??
????????????????????????ensureSegment(j).lock();?//?force?creation??
????????????????}??
????????????????long?hashSum?=?0L;??
????????????????int?sum?=?0;??
????????????????for?(int?j?=?0;?j?<?segments.length;?++j)?{??
????????????????????HashEntry<K,V>[]?tab;??
????????????????????Segment<K,V>?seg?=?segmentAt(segments,?j);??
????????????????????if?(seg?!=?null?&&?(tab?=?seg.table)?!=?null)?{??
????????????????????????for?(int?i?=?0?;?i?<?tab.length;?i++)?{??
????????????????????????????HashEntry<K,V>?e;??
????????????????????????????for?(e?=?entryAt(tab,?i);?e?!=?null;?e?=?e.next)?{??
????????????????????????????????V?v?=?e.value;??
????????????????????????????????if?(v?!=?null?&&?value.equals(v))?{??
????????????????????????????????????found?=?true;??
????????????????????????????????????break?outer;??
????????????????????????????????}??
????????????????????????????}??
????????????????????????}??
????????????????????????sum?+=?seg.modCount;??
????????????????????}??
????????????????}??
????????????????if?(retries?>?0?&&?sum?==?last)??
????????????????????break;??
????????????????last?=?sum;??
????????????}??
????????}?finally?{??
????????????if?(retries?>?RETRIES_BEFORE_LOCK)?{??
????????????????for?(int?j?=?0;?j?<?segments.length;?++j)??
????????????????????segmentAt(segments,?j).unlock();??
????????????}??
????????}??
????????return?found;??
????}??
2 HashTable 源码分析
1）构造方法有三个 ，带零个、一个、两个参数的，最终都会调用两个参数的构造方法
其思想也比较简单，检查参数的合法性
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);
}
2）put 操作，直接在方法的前面加上 synchronized 关键字，简单粗暴，在并发激烈的情况下，效率较低，所以才会有
ConcurrentHashMap 的诞生。
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 (Entry<K,V> e = 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<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
3）get 操作也一样，直接在访问该方法的时候上锁，确保同一个时刻只有一个线程能访问
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
4）其他方法就不说了，基本更 HashMap 里面的方法一样，只是加上同步机制而已
评论