| 【面试官】数据结构 | 您所在的位置：网站首页 › hashmap如何扩容的 › 【面试官】数据结构 |
【面试官】数据结构
|
这里写目录标题
一，HashMap在JDK1.7和JDK1.8中有哪些不同二，说一下HashMap的实现原理JDK1.7中的HashMapJDK1.8中的HashMap
三，HashMap是怎么解决哈希冲突的四，HashMap的put方法的具体流程五，HashMap的扩容操作是怎么实现的六，HashMap 的长度为什么是2的幂次方七，HashMap 与 HashTable 有什么区别八，HashMap 和 ConcurrentHashMap （并发HashMap）的区别九，加载因子（扩容因子）为何默认是0.75十，ConcurrentHashMap 底层具体实现知道吗？实现原理是什么ConcurrentHashMap底层实现
十一，多线程下使用HashMap会有什么问题1.丢失元素2.put 造成链表形成闭环，get的时候出现死循环(jdk8已经解决该问题)
十二，何时会树化？何时会退化为链表
一，HashMap在JDK1.7和JDK1.8中有哪些不同
1.结构不同 首先HashMap在1.7中是以数组+链表的形式存在的,而HashMap在1.8中则是以数组+链表+红黑树构成的, 当一个节点的链表长度超过8并且数组长度超过64时会将链表转换为红黑树 2.扩容条件不同 在1.7中进行初始化或内部当size超过阈值时会触发扩容, 扩容之后的数组大小为之前的两倍, 并且之前该下标的元素只会继续保存在该下标或者两倍的下标位置. 在1.8中扩容触发条件有两个 当初始化或size超过阈值时会触发扩容一条链表上节点数量超过8时会调用扩容方法, 方法内部如果数组长度小于64则会触发3.扩容时间不同 在1.7中, hashmap会先检测是否需要扩容之后再往里面放数据, 而在1.8中hashmap会先把数据放进去在检测是否需要扩容 4.put插入方式不同 在1.7中, hashmap调用put()方法插入时时采用的是 头插法, 并且因为hashmap不是线程安全的, 所以当并发插入并触发扩容时可能会把数组内部的链表变成循环链表, 造成死循环的问题在1.8中, hashmap的put()方法改为了 尾插法插入, 因此解决了1.7中并发扩容造成的循环链表问题, 但是实际上在往红黑树内部并发插入时也有可能会造成两个父节点相互引用而导致的死循环问题 二，说一下HashMap的实现原理 JDK1.7中的HashMap
HashMap底层维护一个数组，数组中的每一项都是一个Entry transient Node[] table;//存储（位桶）的数组我们向 HashMap 中所放置的对象实际上是存储在该数组当中；而Map中的key，value则以Entry的形式存放在数组中 static class Entry implements Map.Entry { final K key; V value; Entry next; int hash; }而这个Entry应该放在数组的哪一个位置上（这个位置通常称为位桶或者hash桶，即hash值相同的Entry会放在同一位置，用链表相连），是通过key的hashCode来计算的。 当两个key通过hashCode计算相同时，则发生了hash冲突(碰撞)，HashMap解决hash冲突的方式是用链表。 当发生hash冲突时，则将存放在数组中的Entry设置为新值的next（这里要注意的是，比如A和B都hash后都映射到下标i中，之前已经有A了，当map.put(B)时，将B放到下标i中，A则为B的next，所以新值存放在数组中，旧值在新值的链表上） 所以当hash冲突很多时，HashMap退化成链表。 JDK1.8中的HashMapJDK7中HashMap采用的是位桶+链表的方式，即我们常说的散列链表的方式，而JDK8中采用的是位桶+链表/红黑树（有关红黑树请查看红黑树）的方式，也是非线程安全的。当某个位桶的链表的长度达到某个阀值的时候，这个链表就将转换成红黑树。 1.位桶数组 JDK中Entry的名字变成了Node，原因是和红黑树的实现TreeNode相关联。 transient Node[] table;//存储（位桶）的数组2.数组元素Node //Node是单向链表，它实现了Map.Entry接口 static class Node implements Map.Entry { final int hash; final K key; V value; Node next; //构造函数Hash值 键 值 下一个节点 Node(int hash, K key, V value, Node next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + = + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; }3.红黑树 //红黑树 static final class TreeNode extends LinkedHashMap.Entry { TreeNode parent; // 父节点 TreeNode left; //左子树 TreeNode right;//右子树 TreeNode prev; // needed to unlink next upon deletion boolean red; //颜色属性 TreeNode(int hash, K key, V val, Node next) { super(hash, key, val, next); } //返回当前节点的根节点 final TreeNode root() { for (TreeNode r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } } 三，HashMap是怎么解决哈希冲突的所谓hash冲突，是由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，所以总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。 通常解决hash冲突的方法有4种 （1）开放定址法，也称为线性探测法，就是从发生冲突的那个位置开始，按照一定的次序从hash表中找到一个空闲的位置，然后把发生冲突的元素存入到这个空闲位置中。 （2）链式寻址法，这是一种非常常见的方法，简单理解就是把存在hash冲突的key，以单向链表的方式来存储，比如HashMap就是采用链式寻址法来实现的。 （3）再hash法，就是当通过某个hash函数计算的key存在冲突时，再用另外一个hash函数对这个key做hash，一直运算直到不再产生冲突。这种方式会增加计算时间，性能影响较大。 （4）建立公共溢出区， 就是把hash表分为基本表和溢出表两个部分，凡事存在冲突的元素，一律放入到溢出表中。 四，HashMap的put方法的具体流程1、判断键值对数组table[i]是否为空（null）或者length=0，是的话就执行resize()方法进行扩容。 2、不是就根据键值key计算hash值得到插入的数组索引i。 3、判断table[i]==null，如果是true，直接新建节点进行添加，如果是false，判断table[i]的首个元素是否和key一样，一样就直接覆盖。 4、判断table[i]是否为treenode，即判断是否是红黑树，如果是红黑树，直接在树中插入键值对。 5、如果不是treenode，开始遍历链表，判断链表长度是否大于8，如果大于8就转成红黑树，在树中执行插入操作，如果不是大于8，就在链表中执行插入；在遍历过程中判断key是否存在，存在就直接覆盖对应的value值。 6、插入成功后，就需要判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过了，执行resize方法进行扩容。 五，HashMap的扩容操作是怎么实现的1.扩容的方法如下，主要干这几件事情，第一件，算出新数组长度和新数组扩容阈值，创建新数组。第二件，扩容前的数组元素迁移到扩容后的数组当中去。主要分为单个元素的迁移，链表的迁移，红黑树的迁移 为了快速运算出键值对存储的索引和让键值对均匀分布 1、首先计算键值对的索引要满足两个要求：不能越界、均匀分布 而 h % length （h根据key计算出来的哈希值）就能满足这一点，但是取模运算速度较慢。 容量为2的次幂时、而 h & (length-1)刚好也能满足，而且按位与运算速度很快。 所以最终结果认为：HashMap容量为2的次幂 开始是为了提高计算索引速度，但在解决哈希冲突过高的过程中通过右移+异或打乱哈希值，使得哈希冲突大大减少 七，HashMap 与 HashTable 有什么区别 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过 synchronized 修饰效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；对Null key 和Null value的支持： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在HashTable 中 put 进的键值只要有一个 null，直接抛NullPointerException。初始容量大小和每次扩充容量大小的不同 ： 创建时如果不指定容量初始值，Hashtable 默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。推荐使用：在 Hashtable 的类注释可以看到，Hashtable 是保留类不建议使用，推荐在单线程环境下使用 HashMap 替代，如果需要多线程使用则用 ConcurrentHashMap 替代。 八，HashMap 和 ConcurrentHashMap （并发HashMap）的区别HashMap 数据结构：数组 + 链表 + 红黑树 安全性：非线程安全，因为底层代码操作数组时未加锁。 应用场景：高并发情况下，put、remove 成员变量时可能产生线程安全问题，需加锁；操作非成员标量时不会发生线程安全问题，可以不用加锁。 扩容：元素插入后判断数组长度是否超阈，默认阈值0.75，若超阈则进行扩容，扩容大小为原数组的2的幂次方，若原数组所在内存上没有连续的可用空间，则申请新的可用连续空间，将旧数组复制到新的地址，再将旧数组置为null，等待GC回收。 缩容：无动态缩容机制，需手动缩容。 HconcurrentHashMap 数据结构：分段数组 + 链表 + 红黑树 安全性：线程安全，因为底层代码在操作每一个segment时都会对segment加锁，保证线程安全。 应用场景：高并发情况下，线程安全，操作成员变量或局部变量都不需要单独加锁处理。 性能：读取数据时不加锁，高效，且因为map中的value值是添加volatile关键字修饰的，可保证读取到最新值，降低CPU负载。 写入数据时，会先通过hashcode算法算出要写入的segment（桶的位置），然后锁定当前segment，而不是锁定整个数组，所以读写效率比hashTable要高很多。 扩容、缩容：同hashMap 九，加载因子（扩容因子）为何默认是0.75 加载因子就是表示Hash表中元素的填满程度加载因子 = 填入表中的元素个数 / 散列表的长度 加载因子越大，填满的元素越多，空间利用率越高，但发生冲突的机会变大了； 加载因子越小，填满的元素越少，冲突发生的机会减小，但空间浪费了更多了，而且还会提高扩容rehash操作的次数。冲突的机会越大，说明需要查找的数据还需要通过另一个途径查找，这样查找的成本就越高。因此，必须在“冲突的机会”与“空间利用率”之间，寻找一种平衡与折衷。选择0.75作为默认的加载因子，完全是时间和空间成本上寻求的一种折衷选择。 十，ConcurrentHashMap 底层具体实现知道吗？实现原理是什么 ConcurrentHashMap底层实现JDK1.7 底层数据结构：Segments数组+HashEntry数组+链表，采用分段锁保证安全性容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这 样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的”分段锁”思想 一个ConcurrentHashMap中有一个Segments数组，一个Segments中存储一个HashEntry数组，每个HashEntry是一个链表结构的元素。segment继承自ReentrantLock锁。 首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。可以通过构造函数指定,数组扩容不会影响其他的segment,get无需加锁,volatile保证内存可见性JDK1.8 底层数据结构：Synchronized + CAS +Node +红黑树.Node的val和next都用volatile保证,保证可见性,查找,替换,赋值操作都使用CAS 为什么在有Synchronized 的情况下还要使用CAS因为CAS是乐观锁,在一些场景中(并发不激烈的情况下)它比Synchronized和ReentrentLock的效率要高,当CAS保障不了线程安全的情况下(扩容或者hash冲突的情况下)转成Synchronized 来保证线程安全,大大提高了低并发下的性能. 锁 : 锁是锁的链表的head的节点,不影响其他元素的读写,锁粒度更细,效率更高,扩容时,阻塞所有的读写操作(因为扩容的时候使用的是Synchronized锁,锁全表),并发扩容. 十一，多线程下使用HashMap会有什么问题 1.丢失元素1.当多线程同时put值的时候，若发生hash碰撞，可能多个元素都落在链表的头部，从而造成元素覆盖（hashcode相同而eques值不同的元素） 列如：线程A put一个元素a ，线程B put一个元素b，a,b 发生hansh碰撞，本应该在map是链表的形式存在，但是可能线程A和线程B同时put到链表的第一个位置，从而后来者覆盖前者元素造成元素丢失。 2.put 造成链表形成闭环，get的时候出现死循环(jdk8已经解决该问题)该情况是出现在多线线程操作map扩容时会发生 形成循环链表的代码就在transfer方法的while循环中, 正是因为扩容之后链表中元素的会发生逆转, 所以会产生循环链表. // 扩容方法 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, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } /** * Transfers all entries from current table to newTable. * 这段代码主要是遍历原集合中的所有Entry, 然后依次将他们放入到新的集合中. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; // 遍历所有Entry for (Entry e : table) { // 这里的while主要针对存在链表的情况 while(null != e) { // 获取下一个元素, 如果存在链表, next就不为null Entry next = e.next; // 是否需要重新hash if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 获取新下标 int i = indexFor(e.hash, newCapacity); // 第一次while循环时, newTable[i]是null // 第二次while循环时, newTable[i]是第一次循环时的元素 // 原先链表的顺序为: 1,3,5,7,9 // 正常情况下, 扩容完成之后, 链表中元素的顺序为: 9,7,5,3,1 e.next = newTable[i]; // 覆盖上次循环的值, 因为上次循环时的值已经被链接到e.next上了 newTable[i] = e; // 继续循环链表上的下一个元素 e = next; } } } 十二，何时会树化？何时会退化为链表树化有两个条件：链表长度超过树化阈值并且数组容量大于等于64。 由于树化的开销很大，因此能使用扩容的方式解决链表长度过长的话，是不会树化的。 退化情况1：在扩容的时候如果拆分了树，使得树中元素个数小于等于6，那么红黑树会退化为链表。退化情况2：remove树中的节点的时候，在remove之前，若root，root.left，root.right，root.left.left中有一个为null，也会退化为链表，然后再移除这个节点。 |
首先我们看下新数组长度和新数组扩容阈值是怎么算出来的。这里也分为两种情况，第一种是数组已经初始化过了。第二种是hashMap里面的散列表为null的情况。先看下数组已经初始化过的情况。如下图所示。 
详细看：https://www.cnblogs.com/lufei-123/p/14384578.html【本文地址】