认识达内从这里开始

认真做教育专心促就业

hashmap：面试必问知识点，你了解多少？

发布：济南IT培训
来源：互联网
时间：2018-04-17 14:01

   济南IT培训的小编作为一个职场搬了几年砖的码农,不管是面试别人还是被别人面试,hashmap在面试出现的几率可以说高达90%以上!
    面试官们,如此反复的提及hashmap,它在软件开发中的重要性可见一斑.
    那么,hashmap到底是个什么鬼?
    hashmap在不同的jdk版本其实现方式也是不大一样的.
    JDK1.7:基于数组(散列桶)+链表来实现.
    transient Entry<K,V>[] table=(Entry<K,V>[])EMPTY_TABLE;static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; int hash;...}
    使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hash collision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表.
    在hashcode特别差的情况下,比如所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表.
    换句话说时间复杂度在最差情况下会退化到O(n).
    JDK1.8:基于数组(散列桶)+链表/红黑树来实现.
    transient Node<K,V>[] table;static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; ... }
    使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构.
    如果插入的key的hashcode相同,那么这些key也会被定位到Node数组的同一个格子里.
    如果同一个格子里的key不超过8个,使用链表结构存储.
    如果超过了8个,那么会调用treeifyBin函数,将链表转换为红黑树.
    那么即使hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要O(log n)的开销.
    也就是说put/get的操作的时间复杂度最差只有O(log n).
    相同点
    1. 默认初始容量都是16,默认负载因子都是0.75.数组的长度length都是2的次幂,扩容时都是2倍
    2. 通过hash计算索引的方法相同(hash & length-1)
    3. key为null的键值对都会放入table[0]中

4. 都是懒加载,初始时表为空,在插入第一个键值对时初始化

济南IT培训

    不同点
    1. 结构不同,JDK1.8增加了红黑树优化结构
    2. put方法的区别,JDK1.7中put时,添加到头节点;JDK1.8中添加到尾节点
    3. 计算hash的方法不同,JDK1.8更优化
    4. JDK1.7新链表的顺序倒置,JDK1.8新链表顺序不倒置
    jdk1.8 put操作:
    ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容;
    ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;
    ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals;
    ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤;
    ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可;
    ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容.
    篇幅有限,感兴趣的童鞋可以看看hashmap源码是如何处理这些关键点:根据key获取哈希桶数组索引位置、put方法的详细执行、扩容机制.
    下面分享一个面试常问的问题:HashMap是线程安全的么?如果不是,那如果既想用HashMap又想让它线程安全应该怎么做?
    可以有如下几种方式来回答:
    替换成Hashtable,Hashtable通过对整个表上锁实现线程安全,但是效率比较低
    使用Collections类的synchronizedMap方法包装一下.方法如下:
    public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
    返回由指定映射支持的同步(线程安全的)映射
    使用ConcurrentHashMap,它使用分段锁来保证线程安全
    前两种方式获得的线程安全的HashMap在读写数据的时候会对整个容器上锁

ConcurrentHashMap是不需要对整个容器上锁的,它只需锁住要修改的部分

更多济南IT培训相关咨询,请扫描下方二维码

济南IT培训