HashMap在java编程中，算使用频率top10中的类了。这里是关于HashMap的源码的分析。一个类的源码分析，要看他的来龙去脉，他的历史迭代。一来从以前的版本开始分析，由易到难；二来可以看到他的迭代优化过程。HashMap的源码分析，就从很老以前的一个版本开始分析。
简要说明，HashMap内部是一个数组，Object key 通过hash得到数组的index，如果数组index的位置有碰撞，则通过链表的形式接到那个位置上。取值是先hash到某个位置，然后在比较链表中每个值，获取到要取的值。
这里先重点分析java1.2中HashMap的源码。
private transient Entry table[]; private transient int count; private int threshold; private float loadFactor; private transient int modCount = 0; // 构造方法一 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Initial Capacity: "+ initialCapacity); if (loadFactor <= 0) throw new IllegalArgumentException("Illegal Load factor: "+ loadFactor); if (initialCapacity==0) initialCapacity = 1; this.loadFactor = loadFactor; table = new Entry[initialCapacity]; threshold = (int)(initialCapacity * loadFactor); } // 构造方法二 public HashMap(int initialCapacity) { this(initialCapacity, 0.75f); } // 构造方法三 public HashMap() { this(101, 0.75f); } // 构造方法四 public HashMap(Map t) { this(Math.max(2*t.size(), 11), 0.75f); putAll(t); }
属性数组table就是HashMap内部存放各种实体的数组。
count是当前存放实体的数量。
modCount是HashMap修改的次数，这里不是做什么统计用，在后面的HashIterator里要用到，HashIterator计算中，不希望HashMap被修改的。
initialCapacity是HashMap内数组的初始长度。构造方法三中，默认初始长度为101，不太清楚这个101是怎么定义出来的。在构造方法四中，他的初始长度是11和入参map长度的2倍之间的大值。这里的11和101比较诡异。
capacity是HashMap里数组的最大长度，随着HashMap里数组长度的变化而变化。
threshold是用来提醒数组table该增大了的一个阀值。
loadFactor是threshold值计算的一个系数，默认0.75， threshold ＝ capacity * loadFactor 。
基本的方法：
// 查看HashMap存放数，count是HashMap的存放数属性 public int size() { return count; } // 查看HashMap存放数是否为空，count＝=0表示存放数为空 public boolean isEmpty() { return count == 0; }
对于调用方存入的一个个key和value，HashMap内部存放的是一个个内部实体对象，这里分析他的内部实体类。
// HashMap内部实体类 private static class Entry implements Map.Entry { int hash; // 存入HashMap key值的hashCode值 Object key; // 存入HashMap的key值 Object value; // 存入HashMap的value值 Entry next; // 存入HashMap中下一个值，这里是为产生Hash碰撞后，链表结构准备的，单向链表 // 构造方法 Entry(int hash, Object key, Object value, Entry next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // 对象克隆方法 protected Object clone() { return new Entry(hash, key, value, (next==null ? null : (Entry)next.clone())); } public Object getKey() { return key; } public Object getValue() { return value; } // 设置value值，并返回老的value值 public Object setValue(Object value) { Object oldValue = this.value; this.value = value; return oldValue; } // 判断实体对象的相等方法；只有在实体的key和value都相等时，才相等 public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry e = (Map.Entry)o; return (key==null ? e.getKey()==null : key.equals(e.getKey())) && (value==null ? e.getValue()==null : value.equals(e.getValue())); } // hashCode值，实体的hashCode值为key的hashCode和value的hashCode的异或值 public int hashCode() { return hash ^ (value==null ? 0 : value.hashCode()); } public String toString() { return key+"="+value; } }
HashMap同时也实现了Iterator接口，这里分析他的实现逻辑
// Iterator的类型 private static final int KEYS = 0; // Iterator对key进行操作 private static final int VALUES = 1;// Iterator对value进行操作 private static final int ENTRIES = 2;// iterator对entry进行操作 // HashMap对Iterator接口的实现 private class HashIterator implements Iterator { Entry[] table = HashMap.this.table; int index = table.length; Entry entry = null; // 临时变量，存放hasNext方法时，遍历到的数组位链表对象 Entry lastReturned = null; // 临时变量，存放next方法时，遍历到的对象；为remove方法中准备 int type; // iterator的类型 // 存放HashMap修改的次数 private int expectedModCount = modCount; // 构造方法，入参为设定Iterator的类型 HashIterator(int type) { this.type = type; } // 判断容器内是否有值 public boolean hasNext() { while (entry==null && index>0) entry = table[--index]; return entry != null; } // 获取下一个值 public Object next() { // 遍历过程中，HashMap是不允许有改动，否则抛出异常ConcurrentModificationException if (modCount != expectedModCount) throw new ConcurrentModificationException(); // 遍历过程中，处理那种没有先调用hasNext方法的情况 while (entry==null && index>0) entry = table[--index]; // 如果entry不为null，处理entry if (entry != null) { // entry存放在临时变量lastReturned Entry e = lastReturned = entry; // entry存放链表的下一个节点，为下一次调用next方法做准备 entry = e.next; // 根据type的类型，返回不同的值 return type == KEYS ? e.key : (type == VALUES ? e.value : e); } throw new NoSuchElementException(); } // 移除实体对象 public void remove() { // remove调用之前，需要先调用hasNext方法，否则lastReturned=null,抛出异常 if (lastReturned == null) throw new IllegalStateException(); // 移除操作，HashMap也不希望在其他地方有修改 if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry[] tab = HashMap.this.table; // 找到lastReturned对应数组的位置 int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length; // 找到对应数组的位置后，删除对应链表中的lastReturned值，下面是链表的操作 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { if (e == lastReturned) { modCount++; expectedModCount++; if (prev == null) tab[index] = e.next; else prev.next = e.next; count--; lastReturned = null; return; } } throw new ConcurrentModificationException(); } }
下面主要分析HashMap的添删查
// 判断HashMap是否包含key值 public boolean containsKey(Object key) { Entry tab[] = table; // key值不为null if (key != null) { // 通过key计算出key对应数组table的下标，其实这里是可以封装成一个方法的，多个地方都要用到，后面jdk的版本都有改进 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 查找链表，判断key是否存在 for (Entry e = tab[index]; e != null; e = e.next) if (e.hash==hash && key.equals(e.key)) return true; } else { // key为null // 查找链表，判断key是否存在 for (Entry e = tab[0]; e != null; e = e.next) if (e.key==null) return true; } return false; } // 判断HashMap是否包含value值 // 这个方法实际效率是很低的，需要先遍历数组，在一个个遍历链表，没有用到hash特性 public boolean containsValue(Object value) { Entry tab[] = table; // value值为null if (value==null) { // 遍历数组 for (int i = tab.length ; i-- > 0 ;) // 遍历链表 for (Entry e = tab[i] ; e != null ; e = e.next) if (e.value==null) return true; } else {// value值不为null // 遍历数组 for (int i = tab.length ; i-- > 0 ;) // 遍历链表 for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; } return false; } // 获取key对应的value值 public Object get(Object key) { Entry tab[] = table; // key不为null if (key != null) { // key的hashCode值 int hash = key.hashCode(); // key的hashCode计算出的hash值 int index = (hash & 0x7FFFFFFF) % tab.length; // 通过index定位到数组，然后遍历对应的链表结构 for (Entry e = tab[index]; e != null; e = e.next) if ((e.hash == hash) && key.equals(e.key)) return e.value; } else { // 如果key为null，直接遍历对应的链表结构 for (Entry e = tab[0]; e != null; e = e.next) if (e.key==null) return e.value; } return null; } // 往HashMap中存放key和value public Object put(Object key, Object value) { Entry tab[] = table; int hash = 0; int index = 0; // 这部分操作是当数组下标的对应位置已经有值，并且 // key不为null if (key != null) { // 获得key对应数组的下标 hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; // 在数组对应的下标有值的情况下 // key已经存在，把新的value代替老的value，并返回老的value for (Entry e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && key.equals(e.key)) { Object old = e.value; e.value = value; return old; } } } else { // key为null，数组的下标是确定的，为0 // 在数组对应的下标有值的情况下 // key已经存在，把新的value代替老的value，并返回老的value for (Entry e = tab[0] ; e != null ; e = e.next) { if (e.key == null) { Object old = e.value; e.value = value; return old; } } } // HashMap的修改次数加一 modCount++; // 如果数组的使用长度大于或等于阀值threshold后 if (count >= threshold) { // 扩展数组 rehash(); // 重新赋值tab tab = table; // 重新计算index index = (hash & 0x7FFFFFFF) % tab.length; } // 在原HashMap中，key没找到对应的value时 // 这里先构造一个实体，把实体的next属性指向数组下标index对应的位置 Entry e = new Entry(hash, key, value, tab[index]); // 数组下标对应的位置赋值实体e tab[index] = e; // 实体数量加一 count++; return null; } // 推展数组 private void rehash() { // 原数组长度 int oldCapacity = table.length; // 原数组 Entry oldMap[] = table; // 新数组长度，这里数组的增长策略是2倍加一的增 int newCapacity = oldCapacity * 2 + 1; // 重新创建数组 Entry newMap[] = new Entry[newCapacity]; // HashMap的修改次数加一 modCount++; // 更新HashMap的扩展数组的阀值 threshold = (int)(newCapacity * loadFactor); // 赋值新数组到HashMap的数组 // 这个地方存在并发问题，因为此时数组虽然创建了，但是实体值还是没有迁移过来的。 // 如果此时有人读取value值，可能会返回为空 table = newMap; // 把老数组里的值迁移到新数组里 // 遍历数组 for (int i = oldCapacity ; i-- > 0 ;) { // 遍历链表 for (Entry old = oldMap[i] ; old != null ; ) { Entry e = old; old = old.next; int index = (e.hash & 0x7FFFFFFF) % newCapacity; e.next = newMap[index]; newMap[index] = e; } } } // 移除实体 public Object remove(Object key) { Entry tab[] = table; // key不为null if (key != null) { // 获得key对应的hash值和对应的数组下标 int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; // 根据对应的数组下标，找到链表对象 // 遍历链表 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) { if ((e.hash == hash) && key.equals(e.key)) { modCount++; if (prev != null) prev.next = e.next; else tab[index] = e.next; count--; Object oldValue = e.value; e.value = null; return oldValue; } } } else {// key为null，对应的数组下标为0 // 根据对应的数组下标，找到链表对象 // 遍历链表 for (Entry e = tab[0], prev = null; e != null; prev = e, e = e.next) { if (e.key == null) { modCount++; if (prev != null) prev.next = e.next; else tab[0] = e.next; count--; Object oldValue = e.value; e.value = null; return oldValue; } } } return null; } // 批量添加 public void putAll(Map t) { Iterator i = t.entrySet().iterator(); while (i.hasNext()) { Map.Entry e = (Map.Entry) i.next(); put(e.getKey(), e.getValue()); } } // 清除数组内容 public void clear() { Entry tab[] = table; modCount++; for (int index = tab.length; --index >= 0; ) tab[index] = null; count = 0; }