JDK1.8-HashMap数据结构

JDK1.8-HashMap的put操作流程

JDK1.8-HashMap的put操作源码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node[] tab; Node p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
            Node e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode) 
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                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;
            }
        }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

HashMap常见面试题

1. HashMap的初始容量和扩容总是2的次方原因？

推理前提：

1.由put源码可见寻址算法为tab[i = (n - 1) & hash]，n即数组长度length；

2.按位与&运算，两个当且仅当都为1的时候结果才为1，只要有一个为0就为0； 反向推理，如果HashMap的容量为15，那么n-1转二进制1110，进行按位与运算后，如0001、1111、0101等不会存储数据，造成空间浪费，增加Hash碰撞的可能性，导致查询效率很低。

2. HashMap中modCount变量？

protected transient int modCount = 0;
//此处以forEach方法为例
public final void forEach(Consumer action) {
            Node[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
}

由put源码可见在最后会做++modCount操作，当对HashMap进行编辑(增删改)操作，modCount会记录操作次数，当对HashMap遍历时，会记录此前modCount值，将此值和实时值比较，不相等即遍历过程对集合进行编辑操作，会抛出异常ConcurrentModificationException。(字面翻译同步修改异常)

面试题

1、在日常开发中使用过的java集合类有哪些？

一般应聘者都会回答ArrayList，LinkedList，HashMap，HashSet等等。如果连这几个集合类都不知道，基本上可以pass了。

2、能描述一下HashMap的实现原理吗？

其实HashMap是典型的空间换时间的一种技术手段。如果面试者在这个问题中不能很好地阐述HashMap的实现原理，比如不知道如何解决hash冲突，不知道loadFactor这样的核心概念以及扩容机制。基本上我不会做深入考察了，可以pass了。

3、平时在使用HashMap时一般使用什么类型的元素作为Key？

面试者通常会回答，使用String或者Integer这样的类。这个时候可以继续追问为什么使用String、Integer呢？这些类有什么特点？如果面试者有很好的思考，可以回答出这些类是Immutable的，并且这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的，而且可以很好的优化比如可以缓存hash值，避免重复计算等等，那么基本上这道题算是过关了。

4、如果让你实现一个自定义的class作为HashMap的key该如何实现？

这个问题其实隐藏着几个知识点，覆写hashCode以及equals方法应该遵循的原则，在jdk文档以及《effective java》中都有明确的描述。当然这也在考察应聘者是如何自己实现一个Immutable类。如果面试者这个问题也能回答得很好，基本上可以获得一点面试官的好感了。

5、你能设计一个算法（输入是java源文件），判断一个类是否是Immutable的吗？

这道题考察面非常非常广。如果这个问题面试者回答上了，我觉得面试者的基础知识无需考察了。可以继续考察高并发与分布式架构设计了。

6、如何衡量一个hash算法的好坏，你知道的常用hash算法有哪些？

如果面试者的技术面比较宽，或者算法基础以及数论基础比较好，这个问题才可以做很好的回答。首先，hashCode()不要求唯一但是要尽可能的均匀分布，而且算法效率要尽可能的快。如果面试者能回答出一些常用的算法，比如MurMurHash（萌萌哒的名字）基本上已经可以俘获面试官了。如果面试者有编译器的背景说出了如何在编译领域使用完美哈希的场景，那就太棒了，毕竟编译原理学得好的人太少了。当然不要忘记了，还可以再考察一下java中String类的hashCode()的实现。

为什么 h = 31 * h + val[off++]; 这一行使用31 ，而不是别的数字，这是一个魔术吗？ 如果都结束了，不要忘了再问一句你知道hash攻击吗？有避免手段吗？就看面试者对各个jdk版本对HashMap的优化是否了解了。这就引出了另一个数据结构红黑树了。可以根据岗位需要继续考察rb-tree，b-tree，lsm-tree等常用数据结构以及典型应用场景。

7、HashMap是线程安全的吗？ 如果多个线程操作同一个HashMap对象会产生哪些非正常现象？

其实这已经开始考察面试者对并发知识的掌握情况了。HashMap在resize时候如果多个线程并发操作如何导致死锁的。面试者不一定知道，但是可以让面试者分析。毕竟很多类库在并发场景中不恰当使用HashMap导致过生产问题。