HashMap源码分析

今天我们来看一下HashMap 一.Hash表的介绍 在学习数据结构的时候，我们有学过一种查找方式叫作哈希查找 我们举个例子说明： 例如内存中有这样的8个位置 这个8个位置就构成了一张hash表 3.0 1 2 3 4 5 6 7 现在我有一个对象需要存储在以上8个位置之一，该对象中有一个属性key，如果不用hashCode而任意存放，那么当查找时就需要到这八个位置里挨个去找，或者用二分法一类的算法。 但如果用hashCode那就会使效率提高很多。 我们定义我们的hashCode为key％8，然后把我们的类存放在取得得余数那个位置。比如我们的key为9，9除8的余数为1，那么我们就把该类存在1这个位置，如果key是13，求得的余数是5，那么我们就把该类放在5这个位置。这样，以后在查找该类时就可以通过key除 8求余数直接找到存放的位置了。 这就是hash查找的原理。 但是如果连个对象的hashCode相同时就会造成hash冲突，10/8为2.18/8也为2，我们必须要解决hash冲突，将hash值一样的放在同一个hash“桶”里。 二.HashMap的数据结构 我们的HashMap的数据结构就是基于上述的列子形成的。 HashMap 的底层实现是数组和链表 链表使用头插法。 数组就是Hash表 链表就是为了防止Hash冲突 我们看代表HashMap的底层数据结构的内部类

/** Entry是单向链表。 * 它是 “HashMap链式存储法”对应的链表。 *它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数 **/ static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; // 指向下一个节点 Entry<K,V> next; final int hash; // 构造函数。 // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)" Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } // 判断两个Entry是否相等 // 若两个Entry的“key”和“value”都相等，则返回true。 // 否则，返回false public final boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; Object k1 = getKey(); Object k2 = e.getKey(); if (k1 == k2 || (k1 != null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue(); if (v1 == v2 || (v1 != null && v1.equals(v2))) return true; } return false; } // 实现hashCode() public final int hashCode() { return (key==null ? 0 : key.hashCode()) ^ (value==null ? 0 : value.hashCode()); } public final String toString() { return getKey() + "=" + getValue(); } // 当向HashMap中添加元素时，绘调用recordAccess()。 // 这里不做任何处理 void recordAccess(HashMap<K,V> m) { } // 当从HashMap中删除元素时，绘调用recordRemoval()。 // 这里不做任何处理 void recordRemoval(HashMap<K,V> m) { } }

HashMap其实就是一个Entry数组，Entry对象中包含了键和值，其中next也是一个Entry对象， 它就是用来处理hash冲突的，形成一个链表。

HashMap中的关键属性 transient Entry[] table; transient int size;//存放元素的个数 int threshold;//临界值 当实际大小超过临界值时，会进行扩容threshold = 加载因子*容量 final float loadFactor; transient int modCount; 其中loadFactor加载因子是表示Hsah表中元素的填满的程度.

若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.链表长度会越来越长,查找效率降低。

反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）

冲突的机会越大,则查找的成本越高.

因此,必须在 “冲突的机会”与”空间利用率”之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的”时-空”矛盾的平衡与折衷.

　　如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。 三.存储 我们来看一下HashMap的数据储存

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; }

我们来分析一下这段代码，HashMap中允许Null值存在，即key为null,至于Value是不是为null,HashMap不关心。null所对应的hashCode值默认为0,所以key为null时，对应hash表中为0的位置的hash桶中，由于HashMap中一个key（key.equals(key1)为true）只能对应一个Value,所以不用插入链表，而是直接替换掉原值。

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，则调用hash方法，参数为key.hashCode返回的整数值

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方法，生成一个整数，降低不同key的hash值重复的几率，提高存储的效率。 之后接着执行indexFor(hash, table.length);

static int indexFor(int h, int length) { return h & (length-1); }

得到该key对应的hash表的位置， 如果hash表中该索引已经有数据了，则用头插法将该数据插入链表中（即放到这个hash桶中） 如果有key.equals()也就是之前有这个key值了，替换原来的value的值 这里有一个细节我们需要注意 return h & (length-1); 一般来说，我们都是和length进行与操作，而这里是和length-1，为什么呢。 我们来分析一下，看HashMap源码可知，length是2的幂也就意味着length-1是一个奇数，我们知道，和一个奇数与，最后可能是奇数也可能是偶数，但是和偶数与就一定只能是偶数，因为最后一位肯定为0。而这就意味着浪费了差不多一半的空间。所以这里采用和length-1与。

get(Object)方法 寻找某个元素也是一样，先通过hashcode值找到元素所在的hash桶，然后通过key.equals（）找到对应的Value值。

public V get(Object key) { if (key == null) return getForNullKey(); int hash = 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.equals(k))) return e.value; } return null; }

四.遍历 我们在遍历HashMap时一般采用以下方法

public class TestHashMap { public static void main(String[] args) { // TODO Auto-generated method stub Map<String, String> map = new HashMap<String, String>(); map.put("1", "kobe"); map.put("2", "james"); map.put("3", "paul"); Iterator<Map.Entry<String, String>> itEntry = map.entrySet().iterator(); while (itEntry.hasNext()) { Map.Entry<String, String> entry = itEntry.next(); System.out.println("KEY:" + entry.getKey() + "Value:" + entry.getValue()); } for (Map.Entry<String, String> myEntry : map.entrySet()) { System.out.println("KEY:" + myEntry.getKey() + "Value:" + myEntry.getValue()); } Iterator<String> itKeySet = map.keySet().iterator(); while (itKeySet.hasNext()) { String key = itKeySet.next(); System.out.println("KEY:" + key + "VALUE:" + map.get(key)); } for (String key : map.keySet()) { System.out.println("KEY:" + key + "VALUE:" + map.get(key)); } // Map<String, String> map1 = new TreeMap<String, String>(); }

我们可以在上述代码中看出，HashMap利用的是Iterator迭代器进行的遍历，但是我们知道HashMap实现了Map接口并没有实现Collection接口（Map和Collection是平级的，Collection有List和Set），是没有重写iterator方法的。为什么可以用iterator()方法呢？我们观察HashMap的源码发现

public Set<K> keySet() { Set<K> ks = keySet; return (ks != null ? ks : (keySet = new KeySet())); } private final class KeySet extends AbstractSet<K> { public Iterator<K> iterator() { return newKeyIterator(); } public int size() { return size; } public boolean contains(Object o) { return containsKey(o); } public boolean remove(Object o) { return HashMap.this.removeEntryForKey(o) != null; } public void clear() { HashMap.this.clear(); } } public Set<Map.Entry<K,V>> entrySet() { return entrySet0(); } private Set<Map.Entry<K,V>> entrySet0() { Set<Map.Entry<K,V>> es = entrySet; return es != null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { return newEntryIterator(); } public boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<K,V> e = (Map.Entry<K,V>) o; Entry<K,V> candidate = getEntry(e.getKey()); return candidate != null && candidate.equals(e); } public boolean remove(Object o) { return removeMapping(o) != null; } public int size() { return size; } public void clear() { HashMap.this.clear(); } }

原来HashMap中有着两个内部类，分别代表这一个Set集合，都继承了AbstractSet类， 一个是装有key的keySet 集合，一个EntrySet集合 Set集合实现了iterator（）方法。故可以通过Iterator迭代器遍历。 这里也说明了内部类的一个好处，一定程度打破了单继承的限制。对于内部类以后会写博客专门探讨一下。 我们具体看一下KeySet和EntrySet中迭代器的实现 先看KeySet

Iterator<K> newKeyIterator() { return new KeyIterator(); } Iterator<K> newKeyIterator() { return new KeyIterator(); } private final class KeyIterator extends HashIterator<K> { public K next() { return nextEntry().getKey(); } } private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } } final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); 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; //(k = e.key) == key || (key != null && key.equals(k))) //(k = e.key) == key 对应primitive type //(key != null && key.equals(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; }

我们来看看HashIterator这个类，该类页是HashMap的内部类，这个类是一个抽象类，实现了Iterator接口，因为是抽象类，所以不必显示的实现Iterator的方法，所以HashIterator在这里没有显式的实现Iterator的next()方法。而在KeyIterator中实现了next()方法

Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } private final class EntryIterator extends HashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); } }

五.解答为什么要重写hashCode方法 **通过对HashMap的讲解，我相信对为什么要重写hashCode有了解了吧。在HashMap元素查找时，我们必须重写hashcode。因为我们要先通过hashCode找到hash桶，然后再从hash桶（链表中）通过equals找到我们要的Value。这时如果不重写hashCode，使用Object类的hashCode就无法找到hash桶了。 在元素插入时，如果不重写hashCode使用Object类的hashCode，就极易发生hash冲突，大大降低插入元素的效率。 所以我们一定要重写hashCode!!!!!!!**