第1章-005节

remove()、clear()、containsKey()和containsValue()

1.1 remove()⽅法

remove⽅法和put get类似，计算hash，计算index，然后遍历查找，将找到的元素从table[index]
链表移除

```
public V remove(Object key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry prev = table[i];
Entry 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; }

1.2 clear()⽅法

clear⽅法⾮常简单，就是遍历table然后把每个位置置为null，同时修改元素个数为0
需要注意的是clear⽅法只会清楚⾥⾯的元素，并不会重置capactiy

```java
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}

1.3 containsKey()⽅法

containsKey⽅法是先计算hash然后使⽤hash和table.length取摸得到index值，遍历table[index]
元素查找是否包含key相同的值
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
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;
}

1.4 containsValue()⽅法

containsValue⽅法就⽐较粗暴了，就是直接遍历所有元素直到找到value，由此可⻅HashMap的
containsValue⽅法本质上和普通数组和list的contains⽅法没什么区别，你别指望它会像
containsKey那么⾼效
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}

1.5 Fail-Fast机制

我们知道java.util.HashMap不是线程安全的，因此如果在使⽤迭代器的过程中有其他线程修改了
map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。
fail-fast 机制是java集合(Collection)中的⼀种错误机制。当多个线程对同⼀个集合的内容进⾏操
作时，就可能会产⽣ fail-fast 事件。
例如：当某⼀个线程A通过 iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变
了；那么线程A访问集合时，就会抛出 ConcurrentModificationException异常，产⽣ fail-fast 事
件。
这⼀策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap
内容（当然不仅仅是HashMap才会有，其他例如ArrayList也会）的修改都将增加这个值（⼤家可
以再回头看⼀下其源码，在很多操作中都有modCount++这句），那么在迭代器初始化过程中会
将这个值赋给迭代器的expectedModCount。
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他
线程修改了Map：
注意到modCount声明为volatile，保证线程之间修改的可⻅性。
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
在HashMap的API中指出：
由所有HashMap类的“collection 视图⽅法”所返回的迭代器都是快速失败的：在迭代器创建之
后，如果从结构上对映射进⾏修改，除⾮通过迭代器本身的 remove ⽅法，其他任何时间任何⽅
式的修改，迭代器都将抛出 ConcurrentModificationException。因此，⾯对并发的修改，迭代器
很快就会完全失败，⽽不冒在将来不确定的时间发⽣任意不确定⾏为的⻛险。
注意，迭代器的快速失败⾏为不能得到保证，⼀般来说，存在⾮同步的并发修改时，不可能作出
任何坚决的保证。快速失败迭代器尽最⼤努⼒抛出ConcurrentModificationException。因此，编
写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败⾏为应该仅⽤于检测程
序错误。
在上⽂中也提到，fail-fast机制，是⼀种错误检测机制。它只能被⽤来检测错误，因为JDK并不保
证fail-fast机制⼀定会发⽣。若在多线程环境下使⽤ fail-fast机制的集合，建议使
⽤“java.util.concurrent包下的类”去取代“java.util包下的类”。

1.6 两种遍历⽅式

第⼀种效率⾼,以后⼀定要使⽤此种⽅式！
java
　　Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
　　}
第⼆种效率低,以后尽量少使⽤！
java
　　　Map map = new HashMap();
　　Iterator iter = map.keySet().iterator();
　　while (iter.hasNext()) {
　　Object key = iter.next();
　　Object val = map.get(key);
　　}
大家一起学习丫~