看完这篇 HashMap ,和面试官扯皮就没问题了(4)

简介: 看完这篇 HashMap ,和面试官扯皮就没问题了(4)

讲一讲 get 方法全过程


我们上面讲了 HashMap 中的 put 方法全过程,下面我们来看一下 get 方法的过程,


public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
  Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  // 找到真实的元素位置
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n - 1) & hash]) != null) {
    // 总是会check 一下第一个元素
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
      return first;
    // 如果不是第一个元素,并且下一个元素不是空的
    if ((e = first.next) != null) {
      // 判断是否属于 TreeNode,如果是 TreeNode 实例,直接从 TreeNode.getTreeNode 取
      if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
      // 如果还不是 TreeNode 实例,就直接循环数组元素,直到找到指定元素位置
      do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          return e;
      } while ((e = e.next) != null);
    }
  }
  return null;
}


来简单介绍下吧,首先会检查 table 中的元素是否为空,然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空,如果不为空,是否匹配,如果匹配,直接返回这条记录;如果匹配,再判断下一个元素的值是否为 null,为空直接返回,如果不为空,再判断是否是 TreeNode 实例,如果是 TreeNode 实例,则直接使用 TreeNode.getTreeNode 取出元素,否则执行循环,直到下一个元素为 null 位置。


getNode 方法有一个比较重要的过程就是 「(n - 1) & hash」,这段代码是确定需要查找的桶的位置的,那么,为什么要 (n - 1) & hash 呢?


n 就是 HashMap 中桶的数量,这句话的意思也就是说 (n - 1) & hash 就是 (桶的容量 - 1) & hash


// 为什么 HashMap 的检索位置是 (table.size - 1) & hash
public static void main(String[] args) {
  Map<String,Object> map = new HashMap<>();
  // debug 得知 1 的 hash 值算出来是 49
  map.put("1","cxuan");
  // debug 得知 1 的 hash 值算出来是 50
  map.put("2","cxuan");
  // debug 得知 1 的 hash 值算出来是 51
  map.put("3","cxuan");
}


那么每次算完之后的 (n - 1) & hash ,依次为


image.png


也就是 「tab[(n - 1) & hash]」 算出的具体位置。


HashMap 的遍历方式


HashMap 的遍历,也是一个使用频次特别高的操作


HashMap 遍历的基类是 HashIterator,它是一个 Hash 迭代器,它是一个 HashMap 内部的抽象类,它的构造比较简单,只有三种方法,「hasNext 、 remove 和 nextNode」 方法,其中 nextNode 方法是由三种迭代器实现的



这三种迭代器就就是


  • KeyIterator ,对 key 进行遍历


  • ValueIterator,对 value 进行遍历


  • EntryIterator, 对 Entry 链进行遍历


虽然说看着迭代器比较多,但其实他们的遍历顺序都是一样的,构造也非常简单,都是使用 HashIterator 中的 nextNode 方法进行遍历


final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }
final class ValueIterator extends HashIterator
  implements Iterator<V> {
  public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
  implements Iterator<Map.Entry<K,V>> {
  public final Map.Entry<K,V> next() { return nextNode(); }
}


HashIterator 中的遍历方式


abstract class HashIterator {
  Node<K,V> next;        // 下一个 entry 节点
  Node<K,V> current;     // 当前 entry 节点
  int expectedModCount;  // fail-fast 的判断标识
  int index;             // 当前槽
  HashIterator() {
    expectedModCount = modCount;
    Node<K,V>[] t = table;
    current = next = null;
    index = 0;
    if (t != null && size > 0) { // advance to first entry
      do {} while (index < t.length && (next = t[index++]) == null);
    }
  }
  public final boolean hasNext() {
    return next != null;
  }
  final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    if (modCount != expectedModCount)
      throw new ConcurrentModificationException();
    if (e == null)
      throw new NoSuchElementException();
    if ((next = (current = e).next) == null && (t = table) != null) {
      do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
  }
  public final void remove() {...}
}


next 和 current 分别表示下一个 Node 节点和当前的 Node 节点,HashIterator 在初始化时会遍历所有的节点。下面我们用图来表示一下他们的遍历顺序


image.png


你会发现 nextNode() 方法的遍历方式和 HashIterator 的遍历方式一样,只不过判断条件不一样,构造 HashIterator 的时候判断条件是有没有链表,桶是否为 null,而遍历 nextNode 的判断条件变为下一个 node 节点是不是 null ,并且桶是不是为 null。


HashMap 中的移除方法


HashMap 中的移除方法也比较简单了,源码如下


public V remove(Object key) {
  Node<K,V> e;
  return (e = removeNode(hash(key), key, null, false, true)) == null ?
    null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
  Node<K,V>[] tab; Node<K,V> p; int n, index;
  if ((tab = table) != null && (n = tab.length) > 0 &&
      (p = tab[index = (n - 1) & hash]) != null) {
    Node<K,V> node = null, e; K k; V v;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      node = p;
    else if ((e = p.next) != null) {
      if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
      else {
        do {
          if (e.hash == hash &&
              ((k = e.key) == key ||
               (key != null && key.equals(k)))) {
            node = e;
            break;
          }
          p = e;
        } while ((e = e.next) != null);
      }
    }
    if (node != null && (!matchValue || (v = node.value) == value ||
                         (value != null && value.equals(v)))) {
      if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
      else if (node == p)
        tab[index] = node.next;
      else
        p.next = node.next;
      ++modCount;
      --size;
      afterNodeRemoval(node);
      return node;
    }
  }
  return null;
}


remove 方法有很多,最终都会调用到 removeNode 方法,只不过传递的参数值不同,我们拿 remove(object) 来演示一下。



首先会通过 hash 来找到对应的 bucket,然后通过遍历链表,找到键值相等的节点,然后把对应的节点进行删除。


关于 HashMap 的面试题


HashMap 的数据结构


JDK1.7 中,HashMap 采用位桶 + 链表的实现,即使用链表来处理冲突,同一 hash 值的链表都存储在一个数组中。但是当位于一个桶中的元素较多,即 hash 值相等的元素较多时,通过 key 值依次查找的效率较低。


所以,与 JDK 1.7 相比,JDK 1.8 在底层结构方面做了一些改变,当每个桶中元素大于 8 的时候,会转变为红黑树,目的就是优化查询效率。


HashMap 的 put 过程


大致过程如下,首先会使用 hash 方法计算对象的哈希码,根据哈希码来确定在 bucket 中存放的位置,如果 bucket 中没有 Node 节点则直接进行 put,如果对应 bucket 已经有 Node 节点,会对链表长度进行分析,判断长度是否大于 8,如果链表长度小于 8 ,在 JDK1.7 前会使用头插法,在 JDK1.8 之后更改为尾插法。如果链表长度大于 8 会进行树化操作,把链表转换为红黑树,在红黑树上进行存储。


HashMap 为啥线程不安全


HashMap 不是一个线程安全的容器,不安全性体现在多线程并发对 HashMap 进行 put 操作上。如果有两个线程 A 和 B ,首先 A 希望插入一个键值对到 HashMap 中,在决定好桶的位置进行 put 时,此时 A 的时间片正好用完了,轮到 B 运行,B 运行后执行和 A 一样的操作,只不过 B 成功把键值对插入进去了。如果 A 和 B 插入的位置(桶)是一样的,那么线程 A 继续执行后就会覆盖 B 的记录,造成了数据不一致问题。


还有一点在于 HashMap 在扩容时,因 resize 方法会形成环,造成死循环,导致 CPU 飙高。


HashMap 是如何处理哈希碰撞的


HashMap 底层是使用位桶 + 链表实现的,位桶决定元素的插入位置,位桶是由 hash 方法决定的,当多个元素的 hash 计算得到相同的哈希值后,HashMap 会把多个 Node 元素都放在对应的位桶中,形成链表,这种处理哈希碰撞的方式被称为链地址法。


其他处理 hash 碰撞的方式还有 「开放地址法、rehash 方法、建立一个公共溢出区」这几种方法。


HashMap 是如何 get 元素的


首先会检查 table 中的元素是否为空,然后根据 hash 算出指定 key 的位置。然后检查链表的第一个元素是否为空,如果不为空,是否匹配,如果匹配,直接返回这条记录;如果匹配,再判断下一个元素的值是否为 null,为空直接返回,如果不为空,再判断是否是 TreeNode 实例,如果是 TreeNode 实例,则直接使用 TreeNode.getTreeNode 取出元素,否则执行循环,直到下一个元素为 null 位置。


HashMap 和 HashTable 有什么区别

见上


HashMap 和 HashSet 的区别

见上


HashMap 是如何扩容的


HashMap 中有两个非常重要的变量,一个是 loadFactor ,一个是 threshold ,loadFactor 表示的就是负载因子,threshold 表示的是下一次要扩容的阈值,当 threshold = loadFactor * 数组长度时,数组长度扩大位原来的两倍,来重新调整 map 的大小,并将原来的对象放入新的 bucket 数组中。


HashMap 的长度为什么是 2 的幂次方


这道题我想了几天,之前和群里小伙伴们探讨每日一题的时候,问他们为什么 length%hash == (n - 1) & hash,它们说相等的前提是 length 的长度 2 的幂次方,然后我回了一句难道 length 还能不是 2 的幂次方吗?其实是我没有搞懂因果关系,因为 HashMap 的长度是 2 的幂次方,所以使用余数来判断在桶中的下标。如果 length 的长度不是 2 的幂次方,小伙伴们可以举个例子来试试


例如长度为 9 时候,3 & (9-1) = 0,2 & (9-1) = 0 ,都在 0 上,碰撞了;


这样会增大 HashMap 碰撞的几率。


HashMap 线程安全的实现有哪些


因为 HashMap 不是一个线程安全的容器,所以并发场景下推荐使用 ConcurrentHashMap ,或者使用线程安全的 HashMap,使用 Collections 包下的线程安全的容器,比如说


Collections.synchronizedMap(new HashMap());


还可以使用 HashTable ,它也是线程安全的容器,基于 key-value 存储,经常用

HashMap 和 HashTable 做比较就是因为 HashTable 的数据结构和 HashMap 相同。


上面效率最高的就是 ConcurrentHashMap。


后记


文章并没有叙述太多关于红黑树的构造、包含添加、删除、树化等过程,一方面是自己能力还达不到,一方面是关于红黑树的描述太过于占据篇幅,红黑树又是很大的一部分内容,所以会考虑放在后面的红黑树进行讲解。


相关文章
|
搜索推荐 Java API
一道Java集合排序题,HashMap排序,面试必备
一道Java集合排序题,HashMap排序,面试必备
|
1月前
|
存储 算法 安全
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
3月前
|
存储 安全 Java
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)
这篇文章是关于Java面试的第二天笔记,涵盖了HashMap与HashTable的区别、ConcurrentHashMap的实现原理、IOC容器的实现方法、字节码的概念和作用、Java类加载器的类型、双亲委派模型、Java异常体系、GC如何判断对象可回收、线程的生命周期及状态,以及sleep、wait、join、yield的区别等十道面试题。
一天十道Java面试题----第二天(HashMap和hashTable的区别--------》sleep、wait、join)
|
3月前
|
安全 Java
【Java集合类面试十五】、说一说HashMap和HashTable的区别
HashMap和Hashtable的主要区别在于Hashtable是线程安全的,不允许null键和值,而HashMap是非线程安全的,允许null键和值。
|
6月前
|
存储 算法 Java
如果面试也能这样说HashMap,那么就不会有那么多遗憾!(中)
如果面试也能这样说HashMap,那么就不会有那么多遗憾!
46 0
|
5月前
|
存储 安全 Java
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
《ArrayList & HashMap 源码类基础面试题》面试官们最喜欢问的ArrayList & HashMap源码类初级问,你都会了?
40 0
|
6月前
|
Python
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
2024年Python最新刷爆全网的动态条形图,原来5行Python代码就能实现!,2024年最新Python面试必问的HashMap
|
6月前
|
存储 算法 Java
耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!
耗时3天写完的HashMap万字解析,争取一篇文章讲透它,面试官看了都直点头!
92 3
|
6月前
|
Java API
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
面试官上来就让手撕HashMap的7种遍历方式,当场愣住,最后只写出了3种
44 1
|
设计模式 算法 Java
面试官:JDK1.8 HashMap扩容rehash算法是如何优化的?
本文跟大家聊一聊一个常见的面试题,那就是JDK1.8 HashMap扩容rehash算法是如何优化的?