设为首页 加入收藏

TOP

HashMap?面试?我是谁?我在哪(一)
2019-01-10 00:08:54 】 浏览:54
Tags:HashMap 面试

现在是晚上11点了,学校屠猪馆的自习室因为太晚要关闭了。勤奋且疲惫的小鲁班也从屠猪馆出来了,正准备回宿舍洗洗睡,由于自习室位置比较偏僻所以是接收不到手机网络信号的,因此小鲁班从兜里掏出手机的时候,信息可真是炸了呀。小鲁班心想,微信群平时都没什么人聊天,今晚肯定是发生了什么大事。仔细一看,才发现原来是小鲁班的室友达摩(光头)拿到了阿里巴巴 Java 开发实习生的 Offer,此时小鲁班真替他室友感到高兴的同时,心里也难免会产生一丝丝的失落感,那是因为自己投了很多份简历,别说拿不拿得到 Offer,就连给面试邀的公司也都寥寥无几。小鲁班这会可真是受到了一万点真实暴击。不过小鲁班还是很乐观的,很快调整了心态,带上耳机,慢慢的走回了宿舍,正打算准备向他那神室友达摩取取经。

片刻后~

小鲁班:666,听说你拿到了阿里的 Offer,能透露一下面试内容和技巧吗?
达摩:嘿嘿嘿,没问题鸭,叫声爸爸我就告诉你。
小鲁班:耙耙(表面笑嘻嘻,心里MMP)
达摩:其实我也不是很记得了(请继续装),但我还是记得那么一些。如果你是面的 Java,首先当然是JAVA的基础知识:数据结构(Map / List / Set等)、设计模式、算法、线程相关、IO/NIO、序列化等等。其次是高级特征:反射机制,并发与锁,JVM(GC策略,类加载机制,内存模型)等等。
小鲁班:问这么多内容,那岂不是一个人都面试很久吗?
达摩:不是的,面试官一般都会用连环炮的方式提问的。
小鲁班:你说的连环炮是什么意思鸭?
达摩:那我举个例子:

  • 就比如问你 HashMap 是不是有序的?你回答不是有序的。
  • 那面试官就会可能继续问你,有没有有序的Map实现类呢?你如果这个时候说不知道的话,那这块问题就到此结束了。如果你说有 TreeMap 和 LinkedHashMap。
  • 那么面试官接下来就可能会问你,TreeMap 和 LinkedHashMap 是如何保证它的顺序的?如果你回答不上来,那么到此为止。如果你说 TreeMap 是通过实现 SortMap 接口,能够把它保存的键值对根据 key 排序,基于红黑树,从而保证 TreeMap 中所有键值对处于有序状态。LinkedHashMap 则是通过插入排序(就是你 put 的时候的顺序是什么,取出来的时候就是什么样子)和访问排序(改变排序把访问过的放到底部)让键值有序。
  • 那么面试官还会继续问你,你觉得它们两个哪个的有序实现比较好?如果你依然可以回答的话,那么面试官会继续问你,你觉得还有没有比它更好或者更高效的实现方式?

无穷无尽深入,直到你回答不出来或者面试官认为问题到底了。

小鲁班捏了一把汗,我去……这是魔鬼吧,那我们来试试呗(因为小鲁班刚刚在自习室才看了这章的知识,想趁机装一波逼,毕竟刚刚叫了声爸爸~~)

于是达摩 and 小鲁班就开始了对决:

1、为什么用HashMap?

  • HashMap 是一个散列桶(数组和链表),它存储的内容是键值对 key-value 映射
  • HashMap 采用了数组和链表的数据结构,能在查询和修改方便继承了数组的线性查找和链表的寻址修改
  • HashMap 是非 synchronized,所以 HashMap 很快
  • HashMap 可以接受 null 键和值,而 Hashtable 则不能(原因就是 equlas() 方法需要对象,因为 HashMap 是后出的 API 经过处理才可以)

2、HashMap 的工作原理是什么?

HashMap 是基于 hashing 的原理

我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。当我们给 put() 方法传递键和值时,我们先对键调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组的 bucket 位置来储存 Node 对象。

这里关键点在于指出,HashMap 是在 bucket 中储存键对象和值对象,作为Map.Node 。

以下是 HashMap 初始化

简化的模拟数据结构:

Node[] table = new Node[16]; // 散列桶初始化,table
class Node {
    hash; //hash值
    key; //键
    value; //值
    node next; //用于指向链表的下一层(产生冲突,用拉链法)
}

以下是具体的 put 过程(JDK1.8)

  1. 对 Key 求 Hash 值,然后再计算下标
  2. 如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的 Hash 值相同,需要放到同一个 bucket 中)
  3. 如果碰撞了,以链表的方式链接到后面
  4. 如果链表长度超过阀值(TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表
  5. 如果节点已经存在就替换旧值
  6. 如果桶满了(容量16*加载因子0.75),就需要 resize(扩容2倍后重排)

以下是具体 get 过程

考虑特殊情况:如果两个键的 hashcode 相同,你如何获取值对象?

当我们调用 get() 方法,HashMap 会使用键对象的 hashcode 找到 bucket 位置,找到 bucket 位置之后,会调用 keys.equals() 方法去找到链表中正确的节点,最终找到要找的值对象。

3、有什么方法可以减少碰撞?

扰动函数可以减少碰撞

原理是如果两个不相等的对象返回不同的 hashcode 的话,那么碰撞的几率就会小些。这就意味着存链表结构减小,这样取值的话就不会频繁调用 equal 方法,从而提高 HashMap 的性能(扰动即 Hash 方法内部的算法实现,目的是让不同对象返回不同hashcode)。

使用不可变的、声明作 final 对象,并且采用合适的 equals() 和 hashCode() 方法,将会减少碰撞的发生

不可变性使得能够缓存不同键的 hashcode,这将提高整个获取对象的速度,使用 String、Integer 这样的 wrapper 类作为键是非常好的选择。

为什么 String、Integer 这样的 wrapper 类适合作为键?

因为 String 是 final,而且已经重写了 equals() 和 hashCode() 方法了。不可变性是必要的,因为为了要计算 hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的 hashcode 的话,那么就不能从 HashMap 中找到你想要的对象。

4、HashMap 中 hash 函数怎么是实现的?

我们可以看到,在 hashmap 中要找到某个元素,需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就是 hash 算法。

前面说过,hashmap 的数据结构是数组和链表的结合,所以我们当然希望这个 hashmap 里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个。那么当我们用 hash 算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。 所以,我们首先想到的就是把 hashcode 对数组长度取模运算。这样一来,元素的分布相对来说是比较均匀的。

但是“模”运算的消耗还是比较大的,能不能找一种更快速、消耗更小的方式?我们来看看 JDK1.8 源码是怎么做的(被楼主修饰了一下)

static final int hash(Object key) {
    if (key == null){
        return 0;
    }
    int h
编程开发网
首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇一文搞清Gradle依赖 下一篇用信鸽来解释 HTTPS

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }