HashMap中的元素玩起了躲猫猫

当你明明put进了一对非null key-value进了HashMap，某个时候你再用这个key去取的时候却发现value为null，再次取的时候却又没问题，都知道是HashMap的非线程安全特性引起的，分析具体原因如下：

 

public V get(Object key) {
		if (key == null)
			return getForNullKey();
		int hash = hash(key.hashCode());

		// indexFor方法取得key在table数组中的索引，table数组中的元素是一个链表结构，遍历链表，取得对应key的value
		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.equals(k)))
				return e.value;
		}
		return null;
	}

 

 

 再看看put方法：

 

public V put(K key, V value) {
		if (key == null)
			return putForNullKey(value);
		int hash = hash(key.hashCode());
		int i = indexFor(hash, table.length);
		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;
			}
		}

		modCount++;
		// 若之前没有put进该key，则调用该方法
		addEntry(hash, key, value, i);
		return null;
	}

 

 

 

再看看addEntry里面的实现：

 

void addEntry(int hash, K key, V value, int bucketIndex) {
		Entry<K, V> e = table[bucketIndex];
		table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
		if (size++ >= threshold)
			resize(2 * table.length);
	}

 里面有一个if块，当map中元素的个数（确切的说是元素的个数-1）大于或等于容量与加载因子的积时，里面的resize是就会被执行到的，继续resize方法：

 

 

void resize(int newCapacity) {
		Entry[] oldTable = table;
		int oldCapacity = oldTable.length;
		if (oldCapacity == MAXIMUM_CAPACITY) {
			threshold = Integer.MAX_VALUE;
			return;
		}

		Entry[] newTable = new Entry[newCapacity];
		transfer(newTable);
		table = newTable;
		threshold = (int) (newCapacity * loadFactor);
	}

 

 

resize里面重新new一个Entry数组，其容量就是旧容量的2倍，这时候，需要重新根据hash方法将旧数组分布到新的数组中，也就是其中的transfer方法：

 

void transfer(Entry[] newTable) {
		Entry[] src = table;
		int newCapacity = newTable.length;
		for (int j = 0; j < src.length; j++) {
			Entry<K, V> e = src[j];
			if (e != null) {
				src[j] = null;
				do {
					Entry<K, V> next = e.next;
					int i = indexFor(e.hash, newCapacity);
					e.next = newTable[i];
					newTable[i] = e;
					e = next;
				} while (e != null);
			}
		}
	}

在这个方法里，将旧数组赋值给src，遍历src，当src的元素非null时，就将src中的该元素置null，即将旧数组中的元素置null了，也就是这一句：

 

if (e != null) {
		src[j] = null;

 此时若有get方法访问这个key，它取得的还是旧数组，当然就取不到其对应的value了。

 

 

下面，我们重现一下场景：

 

import java.util.HashMap;
import java.util.Map;
public class TestHashMap {
	public static void main(String[] args) {
		final Map<String, String> map = new HashMap<String, String>(4, 0.5f);
		
		new Thread(){
			public void run() {
				while(true) { 
					System.out.println(map.get("name1"));
					try {
						Thread.sleep(1000);
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
			}
		}.start();
		for(int i=0; i<3; i++) {
			map.put("name" + i, "value" + i);
		}
	}
}

Debug上面这段程序，在map.put处设置断点，然后跟进put方法中，当i=2的时候就会发生resize操作，在transfer将元素置null处停留片刻，此时线程打印的值就变成null了。

 

 

 

 

学习了，不过楼主所贴的代码不能正确证明。我改了下，如下：

public static void main(String[] args) {
		final Map<String, String> map = new HashMap<String, String>(4, 0.5f);

		Thread thread = new Thread() {
			@Override
			public void run() {
				while (true) {
					System.out.println(map.get("name1"));
					try {
						Thread.sleep(1000);
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
			}
		};
		thread.setDaemon(true);
		thread.start();
		for (int i = 0; i < 3; i++) {
			map.put("name" + i, "value" + i);
			System.out.println("put");
		}
		try {
			Thread.sleep(1000000);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}

我实际debug的，没问题啊

我怎么不能评价

四哥~~~顶一个

看到这我突然想弱弱地问一句：很看到几次HASHMAP通过KEY查找值得时间复杂度为O(1)
然我疑惑的是 get()方法中不是也先要遍历table数组么 难道这不算时间复杂度？

是不用遍历table数组的，数组的下标是通过indexFor迅速定位的，但是table中的元素是一个链表，如果hash的加载因子太大，就有可能出现很多元素hash得到的table索引是一样的，这就需要遍历这个链表了

K，HashMap本来就不是线程安全的，多此一举

对，这时遍历是因为有了”键冲突“。