面试官想问的HashMap,都在这一篇里面了!

java1234

共 3712字,需浏览 8分钟

 ·

2020-08-21 09:38

点击上方蓝色字体,选择“标星公众号”

优质文章,第一时间送达

66套java从入门到精通实战课程分享

一、HashMap的数据结构

HashMap map=new HashMap();
map.put("1","Kobe");

这两行代码表示数据已经在HashMap中存储完成。而这也引发了一个问题,数据如何才能在HashMap中高效地存储?

从这个问题出发,我们首先应该了解HashMap的底层数据结构。

HashMap:数组+链表[单向链表]+红黑树 JDK1.8
我们都知道的是HashMap是存储键值对(key,value)的容器,那么从上图来看在每个小格子中应当放入key还是value或者都存放呢?

如果大家看过源码就会知道,这里采用了一种面向对象的思想,将【key,value】封装起来

class Node{
  private String key;
  private String value
}

由此可知,每一个小格子就是一个new Node,而如果要将他们具体实现出来,只需要在Node的基础上稍加改动即可。

Node[] table=new Node[24]; //表示数组


class Node{
  private String key; //表示单项链表
  private String value
  Node next;
}


class TreeNode entends Node{ //红黑树的伪码表示
  parent;
  left;
  right;
}


二、hash函数和碰撞

当我们获取数据后,要将其存入到HashMap中,就需要确定key,value组成的Node对象在数组索引下标中的位置。
如果想要获取位置,就需要:

  1. 数组长度 length

  2. 得到一个整型数 [0 ---- length-1]

(1)

我们首先可能想到用Random.nextInt(length);但是这样以来就会产生两个问题:

  1. 随机重复的可能性太大

  2. 查找时候没有依据

(2)

鉴于这样的情况,hashCode就登场了:

         1、得到整型数

  1. int hash = key.hashCode() ——> 32位的01组成的整数
    如果我们用一个例子来表示:“1”.hashCode 有可能会超过存储范围

  2. 2、控制这个整型数的范围

  3. 这时就需要控制整形的hash值的范围:hash%length = 需要的范围

但即便是这样,也会产生一定的问题。在hash = key.hashCode();中,如果key的值是31,47之类的数,在模16后(hash%16)得到的结果都是1,这样Node对象去到同一个位置的可能性会比较大,存储的资源就会大大被浪费。

要使index的结果尽可能不重复,就需要换一种计算形式:hash & length-1

得到的结果同样是在0~15之间,这与取模运算得到的结果是一样的。

但即便是这样,不同的hash值也有可能会产生相同的index:
这时就需要把原本hash值的低16位和高16位进行异或运算:

hash函数:将key.hashCode() 高16位和低16位进行一个异或运算,这样得出的最终hash值,最后几位重复的可能性就比原来低了很多。

hash碰撞

在 hash&(n-1) 中,index结果如果重复了,就表示碰撞了。

op2:length-1 ——> 01111这种形式,如果不是这种形式,则无论op1的末尾值无论是1还是0最后计算的结果都会是0,这样就增加了重复的概率。

index实际上取决于op1,因为op2除了第一位之外,其他几位都是1,这也意味着数组的大小必须是10000-1=0111(2的幂次方

三、put的过程

当我们new出来一个HashMap,我们需要去put,也就是向其中存入数据。而在put的时候,需要求出key值的hash( hash(key) ),这里的hash是为了在之后确定位置时使用。在完成hash函数之后,并且维护几个变量,就可以开始具体的put过程。

  1. 检查Node数组有没有初始化,如果没有初始化,那么就需要对它进行初始化。

if ((tab = table) == null || (n = tab.length) == 0)
  n = (tab = resize()).length;


resize()方法初始化

newCap = DEFAULT_INITIAL_CAPACITY; //默认数组大小16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //16*0.75=12  扩容标准


Node newTab = (Node[])new Node[newCap]; //数组初始化


  1. 根据hash函数得到的hash结果,计算Node节点的下标的位置,并开始存入数据。

假如计算出来的Node节点的下标位置是1,判断1这个位置原来有没有Node节点。如果没有,那么就直接创建Node对象,放到数组该位置。如果1这个位置由元素,就分为三种情况:
(1)key值相同,直接替换value值
(2)key值不相同,按链表的方式进行存储
(3)key值不相同,按红黑树的方式存储

else {
  Node e; K k;
  //key值相同,直接替换value值
  if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
  e=p;
  //key值不相同,按链表的方式进行存储
  else if (p instanceof TreeNode)
    e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
  else {
    //key值不相同,按链表的方式进行存储 ————> 循环遍历当前链表,直到找到当前链表的最后一个节点,next==null,将new出来的Node放到最后节点的后面
    for (int binCount = 0; ; ++binCount){
      if ((e = p.next) == null){
        p.next = newNode(hash, key, value, null);
        //但凡新增加一个节点,就检查长度有没有超过8
        if (binCount >= TREEIFY_THRESHOLD - 1)
          //链表转红黑树
          treeifyBin(tab, hash);
        break;
      }
      if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
      break;
    p = e;
    }
  }
  if (e != null) {
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue null)
      e.value = value;
    afterNodeAccess(e);
    return oldValue;
  }
}


注意:链表的长度超过8,就转为红黑树;红黑树里的节点小于6,就转为链表。

四、HashMap的扩容

当数组的大小无法满足存储的需求时,就需要对HashMap进行扩容。

扩容的方法就是:创建一个新的数组,将老数组中的【链表,红黑树】迁移到新数组中。

注意:在扩容时要保证2的倍数扩容,比如16 —> 32,符合2的幂次的规律。

而在什么情况下会发生扩容呢?

假如数组大小时16,当整个数据结构中节点的数量超过 16*0.75=12 时,就会发生扩容。

//源码中的0.75就是负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;


if (++size > threshold) //扩容标准,这里的threshold就是16*0.75
  resize(); //功能:初始化/扩容


//这里的MAXIMUM_CAPACITY是2^30,如果老数组大于这个数,就不需要扩容
if (oldCap >= MAXIMUM_CAPACITY) {
  threshold = Integer.MAX_VALUE;
  return oldTab;
}
//如果没有超过,就将老数组大小向右位移一位
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
  //而这时使用的是新的数组,所以扩容标准也增加一倍,为24
  newThr = oldThr << 1;


当取得这两个参数时,就可以创建新数组:

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];


再之后就需要将老数组的节点迁移到新数组中:

  1. 循环遍历老的数组的下标

  2. 判断当前下标位置有没有元素,有元素才值得迁移

  3. 如果下标位置有元素,并且下面没有元素

  4. 如果下面有元素,并且是红黑树形式

  5. 如果下面有元素,并且是链表形式

if (oldTab != null) {
  //循环遍历老的数组的下标
  for(int j = 0;j < oldCap; ++j) {
    Node e;
    //判断当前下标位置有没有元素,有元素才值得迁移
    if ((e = oldTab[j]) != null) {
      oldTab[j] = null;
      //如果下标位置有元素,并且下面没有元素
      if (e.next == null)
        //得到Node节点再新数组下标的位置
        newTab[e.hash & (newCap - 1)] = e;
      else if (e instanceof TreeNode)
        //如果下面有元素,并且是红黑树形式
        ((TreeNode)e).split(this, newTab, j, oldCap);
        else {
          Node loHead = null, lotail = null;
          Node hiload = null,hiTail = null;
          Node next;
          //如果下面有元素,并且是链表形式
          do {
            next = e.next;
            //老数组链表中i位置的Node节点,会保存到新数组中对应的i位置
            if ((e.hash &oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
                loTail = e;
            }
            //老数组链表中i位置的Node节点,会保存到新数组中对应的i+oldCap位置 1+16=17
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j+oldCap] = hiHead;
          }
        }
    }
  }
}


五、线程安全

多线程执行操作和单线程执行操作,最终的数据不一致,这就是线程非安全。

如果想要保证线程安全,这个线程就需要原子性,可见性,有序性这三大性质。

方法:只有此线程操作完成或者异常退出,其他线程才能进来操作。可以在put的过程中加入synchronized(同步)关键字。但是这样会导致每一个线程都会有一把锁,使得效率大大降低。这时可以使用hashtable或者ConcurrentHashMap,这里不做过多延申,


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:

https://blog.csdn.net/qq_44715697/article/details/108015043



粉丝福利:108本java从入门到大神精选电子书领取

???

?长按上方锋哥微信二维码 2 秒
备注「1234」即可获取资料以及
可以进入java1234官方微信群



感谢点赞支持下哈 

浏览 22
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报