文章目录

1. HashMap的实现原理

HashMap的实现原理

特点

1.基于哈希表的Map实现
2.非同步,也就是非线程安全
3.允许NULL键和NULL值
4.无序
5.插入快，查询快，删除快

数据结构

由于HashMap是基于哈希表，所以拥有哈希表的所有优点和缺点;HashMap实际上是位桶和链表的结合体.

hashmap

//初始的数组容量大小
static final int DEFAULT_INITIAL_CAPACITY = 16;

   //负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

   //table数组扩容的临界值，是当前数组容量*负载因子
   int threshold;

   //table数组
   transient Entry[] table;

   //链表实现
   static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;
       V value;
       Entry<K,V> next;
       final int hash;

       /**
        * Creates new entry.
        */
       Entry(int h, K k, V v, Entry<K,V> n) {
           value = v;
           next = n;
           key = k;
           hash = h;
       }
       ...
   }

HashMap的存取实现

存储—Put

//放入数据，如果key已经存在，新值覆盖旧值，返回旧值
   //如果不存在，新增
public V put(K key, V value) {
   	//key为null,则将此键值对放到table数组的index=0的位子
       if (key == null)
           return putForNullKey(value);
       //根据key的hashCode计算出hash值
       int hash = hash(key.hashCode());
       //计算出此hash值找到table中对应的index
       int i = indexFor(hash, table.length);
       //获取数字index位置的Entry链表，不为null，循环获取next元素
       for (Entry<K,V> e = table[i]; e != null; e = e.next) {
           Object k;
           //如果hash值一致且找到key相等的元素，置入新值，返回旧值
           if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
               return oldValue;
           }
       }
	//执行到这里表示：
       //   1.index位置的Entry为null,不存在
       //   2.index位置的Entry不为null，但是此Entry链表中没有找到匹配的key值
       modCount++;
       //新建Entry放入table的index处
       addEntry(hash, key, value, i);
       return null;
   }

   void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
       //新建Entry放入table的index处，并且此Entry放在链表的头部
       table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
       //如果达到临界值，需要扩容*2
       if (size++ >= threshold)
           resize(2 * table.length);
   }

HashMap在put数据的时候,首先根据key值计算hash，根据hash计算出index值，然后获取数组的index位置的Entry,如果Entry不为null，循环获取的Entry的next元素，查看key值是否与put的key相等，如果相等，就将此Entry的旧值用新值覆盖，返回旧值，如果没有key相等的，就将新建Entry，将在index位置的Entry置入新建的Entry的next属性上，然后就新的Entry放在index位，这样数据就存储成功了。
在这个过程中，有2个比较有意思的设计，一个是hash值的计算，另一个是index的定位，代码如下

   static int hash(int h) {
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
   }

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

为什么hash的计算要这么设计，其实这个是为了防止key的hashcode值，如果高位的值变化，低位的值不变，导致的hash冲突，具体可以查看这个帖子：HashMap hash方法分析
那indexFor为什么要h & (length-1) 计算呢？首先我们要知道HashMap中的table数组的容量大小都是2的n次方，默认为16，是2的4次方，计算我们自己设置初始的容量(看代码)，HashMap也会设置table的容量大小为大于你设置容量的最近的2的n次方那个值;

public HashMap(int initialCapacity, float loadFactor) {
	...
       ...
       int capacity = 1;
       while (capacity < initialCapacity)
           capacity <<= 1;
       ...

这个设计有什么好处呢?那就得看h & (length-1)，如果table的容量不是2的n次方，我们拿15,16做对比：

h & (table.length-1)	hash & (table.length-1)	index
8 & (15-1)：	1000 & 1110	1000
9 & (15-1)：	1001 & 1110	1000
8 & (16-1)：	1000 & 1111	1000
9 & (16-1)：	1001 & 1111	1001

当table数组的容量为15是，8和9计算出来的index值是一样的，这样就导致在index上形成了链表，最终获取元素的时候还要遍历链表，影响效率，而且由于’1110’的最后一位为0，导致table中的index的2进制以1位结尾的位置不会存放元素，导致空间的浪费；而容量为2的n次方，’length-1’使得2进制每个位子上的数字都为1,这样index的值计算就有hash的低位值决定，再加上之前讲的hash的计算方式本来就对低位的值不变的情况进行了优化，这样就尽量避免了hash冲突。

扩容-resize

HashMap的扩容是HashMap最低效的一部分,当HashMap中的元素原来越多，hash的冲突的几率也会越来越高，当达到threshold临界值的时候，HashMap就必须扩容，由于底层采用的是固定长度的数组，这个必定导致新的数组容器的创建和元素的重新置入

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

  /**
   * Transfers all entries from current table to newTable.
   */
  void transfer(Entry[] newTable) {
      Entry[] src = table;
      int newCapacity = newTable.length;
      //遍历原来的数组，依次拿到Entry链表
      for (int j = 0; j < src.length; j++) {
          Entry<K,V> e = src[j];
          //如果链表不为null，就遍历链表中的元素，重新计算index，放入到新数组中
          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);
          }
      }
  }

获取-Get

HashMap的获取元素十分高效，一般情况下获取某个元素的复杂度可以为O(1),达到数组查询的效果

public V get(Object key) {
   	//如果key为null，从数组的index=0获取Entry查找
       if (key == null)
           return getForNullKey();
       //计算hash值
       int hash = hash(key.hashCode());
       //计算得到index值，获取Entry元素，遍历得到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;
   }

删除-Remove

//根据Key删除元素,并返回值
public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}

//删除
final Entry<K,V> removeEntryForKey(Object key) {
    //计算hash值
    int hash = (key == null) ? 0 : hash(key.hashCode());
    //根据hash计算出index值
    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;
        //如果key相等，则将此元素的前一位元素的next位置放置为此元素的后一位元素
        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：

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

方式2：

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

方式1直接遍历的是Entry，方式2遍历的是key，然后在用get获取，方式1的效率会2更高。

Fail-Fast机制

由于HashMap是非线程安全，所以如果在迭代器使用的过程中，有其他的线程来修改HashMap的时候，那么将抛出ConcurrentModificationException，这个就是Fail-Fast机制，原理也很简单，就是在迭代的过程中，用全局的modCount和迭代器范围的expectedModCount做比较，如果不相等，表示在迭代的过程中有其他的线程对HashMap做了修改，就会抛出ConcurrentModificationException异常，最快的完成失败，避免并发导致的不确定性错误！
最常见的就是HashMap的死循环，详情看这个链接：HashMap的死循环

private abstract class HashIterator<E> implements Iterator<E> {
       ...
       int expectedModCount;	// For fast-fail

       HashIterator() {
           expectedModCount = modCount;
           if (size > 0) { // advance to first entry
               Entry[] t = table;
               while (index < t.length && (next = t[index++]) == null)
                   ;
           }
       }

       final Entry<K,V> nextEntry() {
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
           Entry<K,V> e = next;
           ...
       }

       public void remove() {
           if (current == null)
               throw new IllegalStateException();
           if (modCount != expectedModCount)
               throw new ConcurrentModificationException();
          ...
       }

   }

同步实现

1	Map<String,String> synmap = Collections.synchronizedMap(new HashMap<String,String>())

使用集合工具类Collections在HashMap的基础上实现同步,当然你还有更好的选择，就是使用ConcurrentHashMap

JAVA8的优化

JDK1.6中HashMap采取的是位桶+链表的体式格式，即我们常说的散列链表的体式格式，而JDK1.8中采取的是位桶+链表/红黑树的体式格式。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树，这样做的好处就是原来查找元素的效率从O(n)变成了O（log n），查询效率更高了。

	//存放数据
    public V put(K key， V value) {
        return putVal(hash(key)， key， value， false， true);
    }

    final V putVal(int hash， K key， V value， boolean onlyIfAbsent，
            boolean evict) {
         Node<K，V>[] tab;
         Node<K，V> p;
         int n， i;
         //若是table为空或者长度为0，则resize()
         if ((tab = table) == null || (n = tab.length) == 0)
             n = (tab = resize()).length;
         //找到key值对应的数组index并且是第一个，直接加入
         if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash， key， value， null);
         else {
                 Node<K，V> e;
                 K k;
                 //第一个node的hash值即为要加入元素的hash，并且key相等
                 if (p.hash == hash &&
                     ((k = p.key) == key || (key != null && key.equals(k)))){
                      e = p;
                 }else if (p instanceof TreeNode)//第一个节点是TreeNode，即红黑树
                     //将元素放入到红黑树中
                     e = ((TreeNode<K，V>)p).putTreeVal(this， tab， hash， key， value);
                 else {
                     //不是TreeNode，即为链表，遍历链表
                     for (int binCount = 0; ; ++binCount) {
                         /*达到链表的尾端也没有找到key值雷同的节点，
                          *则生成一个新的Node，并且断定链表的节点个数是不是达到转换成红黑树的上界
                          *达到，则转换成红黑树
                          */
                         if ((e = p.next) == null) {
                             p.next = newNode(hash， key， value， null);
                             //如果链表达到了生成红黑树的临界值-1，就将链表转化为红黑树
                             if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                 treeifyBin(tab， hash);
                             break;
                         }
                         if (e.hash == hash &&
                             ((k = e.key) == key || (key != null && key.equals(k))))
                             break;
                         p = e;
                     }
                 }
                 if (e != null) { // existing mapping for key
                     V oldValue = e.value;
                     if (!onlyIfAbsent || oldValue == null)
                         e.value = value;
                     afterNodeAccess(e);
                     //返回旧的value值
                     return oldValue;
                 }
         }
         ++modCount;
         if (++size > threshold)
             resize();
         afterNodeInsertion(evict);
         return null;
}

Roy.Yin's Blog

不要见怪，不要见外

JAVA集合系列——HashMap实现原理