HashMap学习笔记

一、常见有关HashMap面试题汇总

1. 什么时候会使用HashMap？他有什么特点？
2. 你知道HashMap的工作原理吗？
3. 你知道get和put的原理吗？equals()和hashCode()的都有什么作用？
4. 你知道hash的实现吗？为什么要这样实现？
5. 如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？

2.我们能否让HashMap同步？

3.什么是HashSet？

4.“你用过HashMap吗？” “什么是HashMap？你为什么用到它？”

5.HashSet与HashMap的区别？

6.关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法？

7.如果两个键的hashcode相同，你如何获取值对象？

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

9.你了解重新调整HashMap大小存在什么问题吗？

10.为什么String, Interger这样的wrapper类适合作为键？

11.我们可以使用自定义的对象作为键吗？

12.我们可以使用CocurrentHashMap来代替Hashtable吗？

13.hashmap的存储过程？

14.hashMap扩容问题？

15.什么是hash，什么是碰撞，什么是equals ？

16.如何减少碰撞？

17.HashMap的复杂度

18.为什么HashMap是线程不安全的，实际会如何体现？

19.能否让HashMap实现线程安全，如何做？

19.为什么HashTable的默认大小和HashMap不一样？

20.对key进行Hash计算

21.几个常用的哈希码的算法

22.hashmap默认的初始长度是多少，为什么这么规定

23.高并发下，为什么HashMap会出现死锁

24.java8中hashmap结构有什么优化

HashMap的底层实现原理

一、概述

Java8以前为数组+链表，Java8以后为数组+链表+红黑树

这样的：

HashMap实现Map接口，以key-value形式存在，数组的存储对象就是Entry（包含Key和Value）。在HashMap中，会根据hash算法来计算key-value的存储位置来快速存取。

在HashMap中允许最多一条Entry的Key为Null（多条会覆盖），允许多条Entry的value值为null。

（HashMap与HashTable的区别：

1、HashMap没有考虑线程同步，为线程不安全，HashTable使用了synchronized关键字，为线程安全。

2、HashMap允许Null值作为Key，HashTable不允许。

）

二、源码分析

1、HashMap构造函数

HashMap一共提供四个构造函数。其中最重要的两个参数为：初始容量（initialCapacity）和负载因子（loadFactor）

这两个参数是影响HashMap性能的重要参数。其中容量表示哈希表中桶的数量（table数组的大小），初始容量是创建HashMap时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到的多满的一种尺度，衡量空间的使用程度，负载因子越大表示散列表的装填程度越高。负载因子越大时空间的利用越高但是查找的效率越低，系统默认的负载因子大小为0.75，是时间和空间成本的一种折中。

2、HashMap快速存取

put()函数的大致思路：

①对key的hashcode（）做hash，再计算index

②没有发生碰撞就直接放到bucket里面

③发生碰撞，以链表形式插入bucket中

④碰撞导致链表过长，链表转换为红黑树

⑤key对应已经存在节点，新的value替换oldvalue，返回oldvalue（保证key唯一）

⑥如果bucket满了(超过load factor*current capacity)，就要resize。

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算index，如果对应index处没有节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> 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<K,V>)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) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

理解了put（），get（）方法的原理就比较容易了。

首先把输入的key做一次hash

index=hash(“key”)

根据index值寻找entry，hashmap存储并不是key和value分开存储的，而是以key-value存在的entry这时可能发生冲突，需要顺着链表的头结点一个一个向下寻找。

public V get(Object key) {
        // 若为null，调用getForNullKey方法返回相对应的value
        if (key == null)
            // 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null
            return getForNullKey();  

        // 根据该 key 的 hashCode 值计算它的 hash 码 
        int hash = hash(key.hashCode());
        // 找出 table 数组中对应的桶
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //若搜索的key与查找的key相同，则返回相对应的value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

当get（）返回值为Null时有两种情况

1、value为null

2、key不存在

2、hashmap默认初始长度的奥秘

首先明确，hashmap的默认初识长度是16，并且每次自动扩充或者手动初始化时，长度必须是2的幂。这是为了服务于从key映射到index的hash算法。

从key映射HashMap数组的对应位置，会用到Hash函数

index=Hash（“key”）

如何实现一个尽量分布均匀的Hash函数呢

我们通过key的HashCode值来做某种运算。（想要对hashcode有所了解，参考Java中== equals hashcode 区别）

是不是把key的HashCode值和HashMap值做取模运算呢？

index=HashCode(Key)%Length    ?

不是这样的，取模的方式简单，但是效率也很低。为了实现高效的Hash算法，HashMap的发明者采用了位运算的方式。

index= HashCode（key）&（Length-1）

（计算示例下图所示）这种方式的好处是，不但效果等同于取模，而且大大提升了性能。

为什么必须是16或者是2的幂？

长度是16或者其他2的幂时，Length-1的值所有二进制位都是一。

假如Length = 10

这样看似乎没有问题

我们来尝试一个新的HashCode

再换一个

当长度为10时，有些index出现的几率会更大，而有些index永远不会出现 （比如0111）！

显然不符合均匀分布的原则

在设计Hash函数时，目前的table的长度是2的幂，而在计算下标index的时候，设计者认为这样很容易发生碰撞。思考一下当Length-1为15（0x1111）时，其实真正生效的只有低4位的有效位（1111），因此设计者综合考虑，把高16bit和低16bit异或一下，即减少了开销，也不会造成因为高位没有参与下标的计算（table长度比较小时），从而引起的碰撞。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这个函数的大致作用是：高16bit不变，低16bit做了一个异或。

演示过程如下

Java8以前是用链表解决冲突的，产生碰撞情况下进行get()时，两步的时间复杂度是O（1）+O（n），当碰撞很厉害时n很大，显然会影响速度。而Java8后利用红黑树替换链表复杂度变成了O（1）+O（logn），性能得到提升。

貌似已经很长了，但是HashMap还有很多的奥秘，以及关于HashMap很多的面试题需要深入研究。

希望发现有错误的帮忙予以指正

好好学习才能拿得到offer啊~加油

下一篇 关于高并发下HashMap 以及ConcurrentHashMap 的学习

参考：理解HashMap

Java基础之HashMap