在面试中我面试包括我参见的一些面试一直比较喜欢问HashMap原理,不是其原理有多深奥,是因为HashMap几乎是面试的必问点,然而还有大部分的人不能清楚的描述。觉得有必要写一篇来记录一下,一来希望可以帮助有需要的人,二来让自己加深印象。在写这篇之前我也是把源码看了又看,博客翻了又翻,生怕描述错误,如果大家有发现错误的地方还望指正,另外大牛勿喷。以下进入正题:
这是百度百科给的定义:基于 哈希表 的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键,特别是它不保证该顺序恒久不变。通俗的讲,其实HashMap如何有效的存、取、键值对。
现在Java开发面试、Android开发面试,大家好像都喜欢问HaspMap的实现原理,我曾经遇到过一个面试,面试就问了一个HaspMap,从头到尾面了接近30分钟,然后我就被淘汰了...。其实好多同事也会问,HashMap有什么可聊的,开发中直接使用就可以了,如果要用到的时候直接去网上一百度不是都有吗?但是面试了很多候选人,就算在面试前告诉他们会问到HashMap,还是有大部分人挂在这,这其中涉及对数据结构的不理解,对策略的不理解。个人感觉深入的问其原理无非是想从一个点开始,逐渐打开你的知识体系,了解你对基础数据结构、策略的掌握程度,由点及面储备知识的广度,从而更能考验候选人的能力。
其实表示键值对非常简单,在Java的知识体系中声明一个类即可,如下:这个类就可以代表键值对,包含两个属性 K 和 V。
static class Node<K,V> { final K key; V value; }
只有一个类还是不够的,根据Java的面向设计规则,需要一个接口来描述一些动作,在Map接口中还提供了一个内部接口 Entry<K , V>,它表示Map中的一个实体,接口中有 getKey() , getValue() 方法。所以在HashMap中上面这类定义为:
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }
下面是Entry接口:
interface Entry<K, V> { K getKey(); V getValue(); }
在Java中,最基础的存储结构就是两种,一种是数组,另一种是引用,这两个存储结构可以构造所有的数据结构,在Java1.8以前采用数据+链表,在1.8以后采用数组+链表+红黑树的方式构成的。HashMap本质上是一种叫做"链表散列"的数据结构,也就是我们通常所说的数组和链表,关于数组和链表的优缺点其实大家已经非常了解了。
在使用中到底会选用哪种方式来存储呢?查找、插入、删除的场景在实际的开发中都会用到,其实在使用的时候考虑到查找的需求会比较多,因为可以直接用下标定位到数组存储的位置,所以HashMap采用的数组存储的方法。下面截取了一段。可以看到确实是使用了数组进行存储。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); }
上面说到,以数组的形式来存储key-value对象,那在HashMap中是怎样确定数组索引的位置的呢?
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
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就是数组中的索引,如果为null或0就初始化*/ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /*根据计算的下标,如果有值则直接覆盖,如果没有值则直接插入,n是一个2的幂*/ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; /*到这里说明发生了碰撞,这个时候就会进行碰撞处理*/ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; /*如果节点属于树,说明碰撞程度已经超过8个了,就转为红黑树来处理*/ else if (p instanceof TreeNode) e = ((TreeNode<K,V>)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 treeifyBin(tab, hash); break; } /*碰撞的key相等,这时会新老节点替换*/ 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); return oldValue; } } ++modCount; /* 超过了预定的值,这时候就需要扩容了*/ if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
当然后边还有插入红黑树的操作,这里不做分析,有兴趣请查看putTreeVal()这个函数。
下面有一个拓展阅读我觉得讲的特别详细 Hash冲突
HashMap设计的初衷是希望可以存储一组键值对,并且可以快速的查找
今天不想跑,所以才去跑,这才是长距离跑者的思维方式.
欢迎关注个人公众号 HenryFusu,希望一起成长.