2017网站开发发展前景,网站推广软件app,公司和网站备案查询密码,wordpress淘客板块来源公众号#xff1a;非科班的科班本文思维导图HashMap简介HashMap 是很常用的一种集合框架#xff0c;其底层实现方式在 JDK 1.7和 JDK 1.8中却有很大区别。HashMap 是用来存储数据的#xff0c;它底层在JDK 1.7是数组链表实现的#xff0c;而JDK 1.8是使用数组链表红黑树… 来源公众号非科班的科班本文思维导图HashMap简介HashMap 是很常用的一种集合框架其底层实现方式在 JDK 1.7和 JDK 1.8中却有很大区别。HashMap 是用来存储数据的它底层在JDK 1.7是数组链表实现的而JDK 1.8是使用数组链表红黑树实现通过对 key 进行哈希计算等操作后得到数组下标把 value 等信息存放在链表或红黑树存在此位置。如果两个不同的 key 运算后获取的数组下标一致就出现了哈希冲突。数组默认长度是16如果实际数组长度超过一定的值就会进行扩容。HashMap的面试不管小厂还是大厂都是高频问点特别是大厂一定会深究底层采用持续的追问知道你怀疑人生在Java7和Java8中对HashMap的数据结构进行了很大的优化。今天这篇文章就以HashMap的高频问点为主层层的剖析HasMap的底层实现话不多说直接进入正题。问点一你了解HashMap的底层数据结构吗对于HashMap的底层数据结构在Java7和Java8中的实现是不同的在Java7中是采用数组链表的数据结构进行实现而在Java8中是采用数组链表红黑树的数据结构实现的。说时迟那时快刚话说完从兜里拿出笔和纸啪地一声放在桌子上画了起来许久之后出现了两幅jdk7和jdk8的HashMap的内部结构图上图是jdk7内部结构图以Entry[]数组作为哈希桶每个哈希桶的后面又可以连着一条单向链表在链表中以kv的形式存储数据并且每一个节点有指向下一节点的指针。上图是jdk8的HashMap的内部结构图此时在源码源码中就不再使用Entry[]作为数组而是使用Node[]数组作为哈希桶每个哈希桶的后面也可能连着一条单向链表或者红黑树。当单向链表的值8的时候链表就会转换为红黑树进行存储数据在面试大厂的时候其实答到这里还是不完整的为什么呢因为你想你说的上面的实际由jdk7和jdk8转变的一个结果但是重要的为什么要这样做你还没有回答。如果你聪明点的话就不会等着面试官抛出接下来的问题而是自己去回答这个为什么不是等着面试官继续抛出这个为什么一个会聊天的人他会去猜测对方想知道什么问点二哈希冲突是怎么回事HashMap又是怎么解决的哈希冲突是怎么回事呢当的数据将要存进HashMap中的时候会先把k值经过hash函数进行计算得到hash值再通过hash值进行计算得到数据在数组的下标在jdk7中的源码如下//key 进行哈希计算int hash hash(key);//获取数组下标int i indexFor(hash, table.length);通过计算后的下标从而得到数组的对应下标的位置最后把kv值存进去同样的当再次第二次存值的时候同样把kv传进来当k再次进行计算出数组下标index有可能和第一次计算的index的值相同。为什么有可能相同呢这个是hash函数的原因看完上面推荐的那篇hash函数详细介绍你就懂了。当两次的计算index相同这就是hash冲突。但是两次的需要存进去的value值是不同的这就出现了同一个数组后面有一条链表会比较链表上的每一个value值与当前的value是否相同若是不相同通过头插法将数值插入链表中。如下图所示接下来通通过源码进行分析在jdk 7插入的put 方法源码如下public V put(K key, V value) { //数组为空就进行初始化 if (table EMPTY_TABLE) { inflateTable(threshold); } if (key null) return putForNullKey(value); //key 进行哈希计算 int hash hash(key); //获取数组下标 int i indexFor(hash, table.length); //如果此下标有值遍历链表上的元素key 一致的话就替换 value 的值 for (Entry 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;//新增一个key addEntry(hash, key, value, i);return null; }put方法中主要做了以下几件事判断table数组是否为空若为空进行初始化table数组。判断key值是否为null将null是作为key存进去。若key不为空通过key计算出数组下标判断table[i]是否为空。若是不为空通过链表循环判断在链表中是否存在与该key相等若是存在直接将value替换成新的value。若是table[i]为空或者链表中不存在与之相同的key就addEntry(hash, key, value, i)新增一个节点。接下来看看addEntry(hash, key, value, i)新增节点的源码如下void addEntry(int hash, K key, V value, int bucketIndex) {//数组长度大于阈值且存在哈希冲突(即当前数组下标有元素)就将数组扩容至2倍 if ((size threshold) (null ! table[bucketIndex])) { resize(2 * table.length); hash (null ! key) ? hash(key) : 0; bucketIndex indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }这个方法很简单直接就是判断当前数组的大小是否threshold并且table[bucketIndex]是否为null。若成立扩容然后rehash重新得到新数组的下标值最后 createEntry(hash, key, value, bucketIndex)创建新节点。最后来看一下createEntry(hash, key, value, bucketIndex)创建新节点的源码如下void createEntry(int hash, K key, V value, int bucketIndex) { //此位置有元素就在链表头部插入新元素(头插法) Entry e table[bucketIndex]; table[bucketIndex] new Entry(hash, key, value, e); size; }该方法就是通过头插法加入新节点方法非常简单相信都能看懂。经过上面对put方法的源码分析在jdk 7 中put操作的原理图如下所示在JDK 7中链表存储有一个缺点就是当数据很多的时候链表就会很长每次查询都会遍历很长的链表。因此在JDK 8中为了优化HashMap的查询效率将内部的结构改为数组链表和红黑树当一个哈希桶后面的链表长度8的时候就会将链表转化为红黑树红黑树是二分查找提高了查询的效率。接下来通过JDK 8的put源码分析如下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[] tab; Node 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);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);//链表长度超过8就把链表转为红黑树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; }通过分析源码上面的方法主要做了以下几件事判断当前桶是否为空空的就需要初始化(resize 中会判断是否进行初始化)。根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。如果当前桶有值( Hash 冲突)那么就要比较当前桶中的 key、key 的 hashcode 与写入的 key是否相等相等就赋值给 e。如果当前桶为红黑树那就要按照红黑树的方式写入数据。如果是个链表就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面(形成链表)。接着判断当前链表的大小是否大于预设的阈值大于时就要转换为红黑树。如果在遍历过程中找到 key 相同时直接退出遍历。如果 e ! null 就相当于存在相同的 key,那就需要将值覆盖。最后判断是否需要进行扩容。继续看下 treeifyBin 的源码final void treeifyBin(Node[] tab, int hash) { int n, index; Node e;//链表转为红黑树时若此时数组长度小于64扩容数组if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize();else if ((e tab[index (n - 1) hash]) ! null) { TreeNode hd null, tl null;//链表转为树结构do { TreeNode p replacementTreeNode(e, null);if (tl null) hd p;else { p.prev tl; tl.next p; } tl p; } while ((e e.next) ! null);if ((tab[index] hd) ! null) hd.treeify(tab); } }由此可以看到1.8中数组有两种情况会发生扩容一是超过阈值二是链表转为红黑树且数组元素小于64时由此在jdk1.8中默认长度为16情况下要么元素一直放在同一下标链表转为红黑树且数组元素小于64时就会扩容要么超过阈值12时才会扩容。依据上面的源码分析在JDK 1.8中put方法的执行的原理图如下通过上面的分析我们可以看到jdk1.7和1.8情况下 hashmap实现方式区别是非常大的。在源码的分析中也可以找到下面问题的答案。问点三HashMap的扩容机制是怎么样的JDK7与JDK8有什么不同吗JDK 1.7的扩容条件是数组长度大于阈值且存在哈希冲突在JDK 7中的扩容的源码如下void addEntry(int hash, K key, V value, int bucketIndex) { //数组长度大于阈值且存在哈希冲突(即当前数组下标有元素)就将数组扩容至2倍 if ((size threshold) (null ! table[bucketIndex])) { resize(2 * table.length); hash (null ! key) ? hash(key) : 0; bucketIndex indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); }而JDK 1.8扩容条件是数组长度大于阈值或链表转为红黑树且数组元素小于64时源码中的体现如下所示//数组长度大于阈值就扩容if (size threshold) resize();//链表转为红黑树时若此时数组长度小于64扩容数组if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize();问点四HashMap中的键值可以为Null吗能简单说一下原理吗在JDK7中是允许null存进去的通过 putForNullKey(value)方法来存储key为null值具体的实现的源代码如下if (key null) return putForNullKey(value);而在JDK 8中当传进key为null值的时候就直接将hash值取0进行计算存入值的位置。public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}问点五HashMap中能put两个相同的Key吗为什么能或为什么不能这个问题比较简单在JDK7和JDK8中的做法是一样的若是存入的key值一样就会将原来的key所对应的value值直接替换掉可以从源码中看出// JDK1.7if (e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value; // 直接替换原来的value值 e.value value; e.recordAccess(this); return oldValue; }// JDK 1.8else { 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) // 替换掉原来value值 e.value value; afterNodeAccess(e); return oldValue;}问点六聊一聊JDK 7的HashMap中的“死锁”是怎么回事HashMap是线程不安全的在HashMap的源码中并未对其操作进行同步执行所以在并发访问的时候就会出现线程安全的问题。由于上一篇的ConcurrentHashMap篇中讲到了死锁也画了图但是很多读者说看不懂这里我的锅在这里详细的进行图解。假设有线程A和线程B并发访问HashMap中的数据。假设HashMap的长度为2(这里只是为了讲解方便假设长度为2)链表的结构图如下所示4和8都位于同一条链表上其中的threshold为1现在线程A和线程B都要进行put操作首先线程A进行插入值。此时线程A执行到transfer函数中(transfer函数是resize扩容方法中调用的另一个方法)当执行(1)位置的时候如下所示/*** Transfers all entries from current table to newTable.*/void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (Entry e : table) {while(null ! e) { Entry next e.next; ---------------------(1)if (rehash) { e.hash null e.key ? 0 : hash(e.key); }int i indexFor(e.hash, newCapacity); e.next newTable[i]; newTable[i] e; e next; } // while }}此时线程A挂起在此时在线程A的栈中就会存在如下值e 4next 8此时线程B执行put的操作并发现在进行put操作的时候需要扩容当线程B执行 transfer函数中的while循环即会把原来的table变成新一table(线程B自己的栈中)再写入到内存中。执行的过程如下图所示(假设两个元素在新的hash函数下也会映射到同一个位置)此时线程A有获取到cpu的执行时间接着执行(但是纤层A中的数据仍是旧表数据)即从transfer代码(1)处接着执行当前的 e 4, next 8, 上面已经描述执行的的过程若下图所示当操作完成执行查找时会陷入死循环问点七HashMap是线程安全的吗为什么安全或者不安全从上图JDK8的put操作原理图中可以看出为HashMap的put方法的详细过程其中造成线程不安全的方法主要是resize(扩容)方法。假设现在有线程A 和线程B 共同对同一个HashMap进行put操作假设A和B插入的Key-Value中key的hashcode是相同的,这说明该键值对将会插入到Table的同一个下标的,也就是会发生哈希碰撞。此时HashMap按照平时的做法是形成一个链表(若超过八个节点则是红黑树),现在我们插入的下标为null(Table[i]null)则进行正常的插入。此时线程A进行到了这一步正准备插入这时候线程A堵塞线程B获得运行时间进行同样操作也是Table[i]null 。此时它直接运行完整个put方法,成功将元素插入。随后线程A获得运行时间接上上面的判断继续运行进行了Table[i]null的插入(此时其实应该是Table[i]!null的操作因为前面线程B已经插入了一个元素了)这样就会直接把原来线程B插入的数据直接覆盖了如此一来就造成了线程不安全问题。-End-90后中年人の爽点大赏拼多多的厕所上了热搜996的大厂员工没有如厕自由为什么鬼不会攻击被子里的人 可乐记得加冰爱我就要置顶 素质三连biubiubiu~
