彻底弄懂HashMap

2021/02/08 08:14
阅读数 45

我们在面试中, 也会经常被问到HashMap相关的底层实现,  阿巴阿巴....

HashMap的底层实现

首先它是基于数组(存储对象的引用)加链表(存储对象)实现的

当我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时,它调用键对象的hashCode()方法来计算hashcode,让后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals()方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象

简单的模拟实现put的底层实现 jdk1.8

put(k, v){
   int code = k.hashcode(); //计算key的hashcode
   int index = code % table.length; // 存放的数组下表
   table[index] = new Entry(k, v, null); // 对应的对象
   }
      
  // 第二次插入 HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。
  table[index] = new Entry(k, v, table[index]);

  // todo 底层实现 若key相同时 返回并覆盖 否则插入链表的下一个节点
  if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
      e = p;
  if (e != null) { // existing mapping for key
     V oldValue = e.value;
     if (!onlyIfAbsent || oldValue == null)
            e.value = value;
      afterNodeAccess(e); //这个方法在hashmap没有作用, 是在linkedHashMap实现的
      return oldValue;
  }

 HashMap和Hashtable的区别

HashMap和Hashtable都实现了Map接口,但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有:线程安全性,同步(synchronization),以及速度。

  1. HashMap几乎可以等价于Hashtable,除了HashMap是非synchronized的,并可以接受null(HashMap可以接受为null的键值(key)和值(value),而Hashtable则不行)。
  2. HashMap是非synchronized,而Hashtable是synchronized,这意味着Hashtable是线程安全的,多个线程可以共享一个Hashtable;而如果没有正确的同步的话,多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap,它是HashTable的替代,比HashTable的扩展性更好。
  3. 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器,而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构(增加或者移除元素),将会抛出ConcurrentModificationException,但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为,要看JVM。这条同样也是Enumeration和Iterator的区别。
  4. 由于Hashtable是线程安全的也是synchronized,所以在单线程环境下它比HashMap要慢。如果你不需要同步,只需要单一线程,那么使用HashMap性能要好过Hashtable。
  5. HashMap不能保证随着时间的推移Map中的元素次序是不变的。

常见面试题

  •  HashMap的工作原理

HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。

  • hashcode相同会发生什么 

因为hashcode相同,所以它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中 

get时, key的hashcode相同时, 找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象

  • 减少碰撞的发生 

 当时是选择一些不可变的最为我们的key, 不可变性使得能够缓存不同键的hashcode,这将提高整个获取对象的速度,使用String,Interger这样的wrapper类作为键是非常好的选择

  • 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办 

HashMap的默认构造会指定默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置 

  •  CocurrentHashMap来代替Hashtable吗

Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性 

  • 指定hashmap的初始大小 

源码分析

无论我们如何设置初始容量,HashMap的tableSizeFor 都会将我们改成2的幂次方,也就是说,HashMap 的容量百分之百是 2的幂次方。但是,请注意:如果我们预计插入7条数据,那么我们写入7,7-1 = 6, 6经过tableSizeFor() 方法的一些列与运算, 会返回8, HashMap 会设置为 8,虽然是2的幂次方,但是,请注意,当我们放入第7条数据的时候,就会引起扩容,造成性能损失,所以,知晓了原理,我们以后在设置容量的时候还是自己算一下,比如放7条数据,我们还是都是设置成16(默认),这样就不会扩容了。

计算公式:

 “注意负载因子(即loader factor)默认为 0.75”

假如我们要插入7条数据,tableSizeFor(int cap)会将我们输入的7运算成8。

我们使用 8 * 0.75 = 6 也就是说最大阈值为6条

当我们插入第七条的时候它就扩容了,所以我们最好在指定容量的时候多预算一些

持续更新中... 欢迎大家留言补充...

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部
返回顶部
顶部