HashMap遍历及源码解析

一：遍历HashMap的两种方法：

1、使用EntrySet遍历HashMap

 

Map map = new HashMap(); for (Iterator iter = map.entrySet().iterator(); iter.hasNext();) { Map.Entry entry = (Map.Entry) iter.next(); Object key = entry.getKey(); Object val = entry.getValue(); }

2、使用KeySet遍历HashMap

Map map = new HashMap(); for (Iterator iter = map.keySet().iterator(); iter.hasNext();) { Object key = iter.next(); Object val = map.get(key); }

二、HashMap源码解析

/** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or * <tt>null</tt> if there was no mapping for <tt>key</tt>. * (A <tt>null</tt> return can also indicate that the map * previously associated <tt>null</tt> with <tt>key</tt>.) */ 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++; addEntry(hash, key, value, i); return null; }

如果key为null，则调用putForNullKey(value)，先检查Entry[]中是否有key=null的Entry，如果有则把原来的value值取出来

赋值给一个临时变量，将新的value覆盖原来的value，同时返回原来的value，如果没有key=null的Entry，则直接把null和value

添加到Entry[]数组中：如下所示

/** * Offloaded version of put for null keys */ private V putForNullKey(V value) { for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(0, null, value, 0); return null; }

如果key不为null，首先调用key.hashCode()方法返回对象Key的hash code value，在通过hash算法，对刚才返回的hash code value 进行加工处理确保hash code的不同：如下

 

/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

在根据hash code value 和Entry[]的长度找到对象Key所在的下标index，

/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }

如果有重复的key了，先取出原来的，在将新的Value值覆盖原来的，讲原来的value返回；

如果没有重复的key，直接把key-value存入Entry中。

参考资料：

通过分析 JDK 源代码研究 Hash 存储机制

研究 Hash 存储机制

HashMap源码分析（基于JDK1.6）