HashMap深入理解

HashMap也是我们使用非常多的集合，它是基于哈希表的 Map 接口的实现，以key-value的形式存在。在HashMap中，key-value总是会当做一个整体来处理，系统会根据hash算法来来计算key-value的存储位置，学过的同学都知道key-value使用起来非常方便，但是对于他的底层原理不是特别清楚。下面就来分析HashMap的原理。

一、HashMap的数据结构

java编程语言中，最基本的数据结构就两种。一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。IDK1.8里面对HaspMap做了一个更新，采用了数组+链表+红黑树，为什么要做更新呢？因为数组加链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布，当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化这个问题,当桶中的元素元素大于八个时就会转化为红黑树。图中的红色小圆点即代表一个key-value。

图片1.png

新增的红黑树代码如下
static final class TreeNode extends LinkedHashMap.Entry {

TreeNodeK,V> parent; // red-black tree linksTreeNodeK,V> left;TreeNodeK,V> right;TreeNodeK,V> prev; // needed to unlink next upon deletionboolean red;}

红黑树这块，JDK1.8更新了一个重要的操作----桶的树形化treeifyBin()

看下代码

//将桶内所有的 链表节点 替换成 红黑树节点1finalvoidtreeifyBin(Node[] tab, inthash) {2intn, index; Node e;3//如果当前哈希表为空，或者哈希表中元素的个数小于 进行树形化的阈值(默认为 64)，就去新建/扩容4if(tab == null|| (n = tab.length) <>5resize();6elseif((e = tab[index = (n - 1) & hash]) != null) {7//如果哈希表中的元素个数超过了 树形化阈值，进行树形化8// e 是哈希表中指定位置桶里的链表节点，从第一个开始9TreeNode hd = null, tl = null; //红黑树的头、尾节点10do{11//新建一个树形节点，内容和当前链表节点 e 一致12TreeNode p = replacementTreeNode(e, null);13if(tl == null) //确定树头节点14hd = p;15else{ 16p.prev = tl;17tl.next = p;18} 19tl = p;20} while((e = e.next) != null); 21//让桶的第一个元素指向新建的红黑树头结点，以后这个桶里的元素就是红黑树而不是链表了22if((tab[index] = hd) != null)23hd.treeify(tab);24}25}26TreeNode replacementTreeNode(Node p, Node next) {27returnnewTreeNode<>(p.hash, p.key, p.value, next);28}

上述操作做了这些事:

image

二、HashMap的put操作

get操作可以利用下图解释

hashMap put方法执行流程图.png

看下源码

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) //判断table是否为空 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node e; K k; //如果节点key存在的话则直接替换值 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判断该链是否为红黑树 else if (p instanceof TreeNode) e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); else { //该链为链表的情况 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //链表长度大于8转换为红黑树进行处理 treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; // key已经存在直接覆盖value p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //超过最大容量 就扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

三、HashMap的get操作

直接上源码

public V get(Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k;// table不为空 && table长度大于0 && table索引位置(根据hash值计算出)不为空if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; // first的key等于传入的key则返回first对象 if ((e = first.next) != null) { // 向下遍历 if (first instanceof TreeNode) // 判断是否为TreeNode // 如果是红黑树节点，则调用红黑树的查找目标节点方法getTreeNode return ((TreeNode)first).getTreeNode(hash, key); // 走到这代表节点为链表节点 do { // 向下 hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); }}return null; // 找不到符合的返回空

}

四、HashMap的扩容

JDK1.8中的扩容有点难，讲讲JDK1.7中的扩容。HaspMap的默认容量是16个桶。他有一个负载因子，值为0.75，当桶中的键值的个数超过了负载因子和桶个数的乘积(大于等于阈值)就会进行扩容，也就是超过160.75=12时就会扩容。那么是怎么进行扩容的呢？通过JDK源码发现，桶的大小变为了原大小的一倍。扩容(resize)*就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。