HashMap原理浅析及相关知识

一、初识Hashmap

作为集合Map的主要实现类；线程不安全的，效率高；存储null的key和value。

二、HashMap在Jdk7中实现原理

1、HashMap map = new HashMap()

实例化之后会在底层创建长度是16的一维数组Entry[] table。

2、map.put(key1,value1)

调用Key1所在类的hashCode()计算key1哈希值，得到Entry数组中存放的位置                   ---比较存放位置


    如果此位置为空，此时key1-value1添加成功                                   *情况1，添加成功*


    此位置不为空（以为此位置存在一个或多个数据（以链表形式存在）），比较key1和已存在的数据的哈希值：  --比较哈希值


        如果key1的哈希值与存在数据哈希值都不相同，此时key1-value1添加成功         *情况2，添加成功*


        如果key1的哈希值与某一存在数据（key2，value2）相同，继续调用key1类的equals（key2）方法   --equals比较


            如果equals()返回false，此时key1-value1添加成功                   *情况3，添加成功* 


            如果equals()返回true，此时value1替换value2                      *情况4，更新原有key的值*


      情况2和情况3状态下，key1-value1和原来的数据以链表方式存储。


      添加过程中会涉及扩容，超出临界值(存放位置非空)时扩容。默认扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

三、HashMap在Jdk8之后实现原理

1、HashMap map = new HashMap()

底层没创建一个长度为16的数组，而是在首次调用put()方法时，底层创建长度为16的数组。

2、map.put(key1,value1)

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {

    Node<K,V>[] tab; Node<K,V> p; int n, i;

    if ((tab = table) == null || (n = tab.length) == 0)

        n = (tab = resize()).length;//首次put，创建长度为16的数组

    if ((p = tab[i = (n - 1) & hash]) == null)// 需要插入数据位置为空。注：[i = (n - 1) & hash]找到当前key应插入的位置

        tab[i] = newNode(hash, key, value, null); //*情况1*

    else {

        Node<K,V> e; K k;

        if (p.hash == hash &&

            ((k = p.key) == key || (key != null && key.equals(k))))//*情况4*

            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);//*情况2、3*

                    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))))//*情况4*

                    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;

    if (++size > threshold)

        resize();

    afterNodeInsertion(evict);

    return null;

}

3、map.entrySet()

返回一个Set集合

public Set<Map.Entry<K,V>> entrySet() {

    Set<Map.Entry<K,V>> es;

    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;

}

4、map.get(ket)

返回key对应的value值。

public V get(Object key) {

    Node<K,V> e;

    return (e = getNode(hash(key), key)) == null ? null : e.value;

}

5、常见参数：

DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16

DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75

threshold：扩容的临界值，=容量*填充因子：16 * 0.75 => 12

TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8

MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64

四、涉及的基础知识

位运算符用来对二进制位进行操作，Java中提供了如下表所示的位运算符：位运算符中，除 ～ 以外，其余均为二元运算符。

操作数只能为整型和字符型数据。

C语言中六种位运算符：

<<左移

>>右移

| 按位或

& 按位与

~取反

^ 按位异或

左移符号<<：向左移动若干位，高位丢弃，低位补零，对于左移N位，就等于乘以2^n

带符号右移操作>>：向右移动若干位，低位进行丢弃，高位按照符号位进行填补，对于正数做右移操作时，高位补充0；负数进行右移时，高位补充1

不带符号的右移操作>>>：与右移操作类似，高位补零，低位丢弃，正数符合规律，负数不符合规律

键(key)经过hash函数得到的结果作为地址去存放当前的键值对(key-value)(这个是hashmap的存值方式)，但是却发现该地址已经有人先来了，一山不容二虎，就会产生冲突。这个冲突就是hash冲突了。

简单来说：两个不同对象的hashCode相同，这种现象称为hash冲突。

HashMap的Put方法在第2、3情况添加前会产生哈希冲突，HashMap采用的链地址法（将所有哈希地址相同的都链接在同一个链表中 ，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况）解决哈希冲突。

五、相关面试问题

1、HashMap原理？

见上

2、HashMap初始化时阈值默认为12(加载因子为0.75)，会使HashMap提前进行扩容，那为什么不在HashMap满的时候再进行扩容？

若加载因子越大,填满的元素越多,好处是,空间利用率高了,但冲突的机会加大了.链表长度会越来越长,查找效率降低。
反之,加载因子越小,填满的元素越少,好处是冲突的机会减小了,但空间浪费多了.表中的数据将过于稀疏（很多空间还没用，就开始扩容了）
冲突的机会越大,则查找的成本越高. 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷.
这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
如果机器内存足够，并且想要提高查询速度的话可以将加载因子设置小一点；相反如果机器内存紧张，并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它，让它取默认值0.75就好了。

3、什么是哈希冲突？如何解决？

4、并发集合

以下均为java.util.concurrent - Java并发工具包中的同步集合

4.1、ConcurrentHashMap 支持完全并发的检索和更新，所希望的可调整并发的哈希表。此类遵守与 Hashtable 相同的功能规范，并且包括对应于 Hashtable 的每个方法的方法版本。不过，尽管所有操作都是线程安全的，但检索操作不必锁定，并且不支持以某种防止所有访问的方式锁定整个表。此类可以通过程序完全与 Hashtable 进行互操作，这取决于其线程安全，而与其同步细节无关。

4.2、ConcurrentSkipListMap 是基于跳表的实现，也是支持key有序排列的一个key-value数据结构，在并发情况下表现很好，是一种空间换时间的实现，ConcurrentSkipListMap是基于一种乐观锁的方式去实现高并发。

4.3、ConCurrentSkipListSet （在JavaSE 6新增的）提供的功能类似于TreeSet，能够并发的访问有序的set。因为ConcurrentSkipListSet是基于“跳跃列表（skip list）”实现的，只要多个线程没有同时修改集合的同一个部分，那么在正常读、写集合的操作中不会出现竞争现象。

4.4、CopyOnWriteArrayList 是ArrayList 的一个线程安全的变形，其中所有可变操作（添加、设置，等等）都是通过对基础数组进行一次新的复制来实现的。这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更 有效。在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用。此数组在迭代器的生存期内绝不会更改，因此不可能发生冲突，并且迭代器保证不会抛出 ConcurrentModificationException。自创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。不支持迭代器上更改元素的操作（移除、设置和添加）。这些方法将抛出 UnsupportedOperationException。

4.5、CopyOnWriteArraySet 线程安全的无序的集合，可以将它理解成线程安全的HashSet。有意思的是，CopyOnWriteArraySet和HashSet虽然都继承于共同的父类AbstractSet；但是，HashSet是通过“散列表(HashMap)”实现的，而CopyOnWriteArraySet则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。

4.6、ConcurrentLinkedQueue 是一个基于链接节点的、无界的、线程安全的队列。此队列按照 FIFO（先进先出）原则对元素进行排序，队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择，此队列不允许 null 元素。

注：ArrayList和HashMap是非并发集合，迭代时不能进行修改和删除操作

注：CopyOnWriteArrayList和CopyOnWriteArraySet，最适合于读操作通常大大超过写操作的情况

5、线程安全集合及实现原理？

5.1 早期线程安全的集合

Vector：作为Collection->List接口的古老实现类；线程安全的，效率低；底层使用Object[] elementData存储

HashTable:作为Map古老的实现类；线程安全的，效率低；不能存储null的key和value(Properties为其子类:常用来处理配置文件。key和value都是String类型)

5.2 Collections包装方法

Vector和HashTable被弃用后，它们被ArrayList和HashMap代替，但它们不是线程安全的，所以Collections工具类中提供了相应的包装方法把它们包装成线程安全的集合

List<E> synArrayList = Collections.synchronizedList(new ArrayList<E>());


Set<E> synHashSet = Collections.synchronizedSet(new HashSet<E>());


Map<K,V> synHashMap = Collections.synchronizedMap(new HashMap<K,V>());


...

5.3 java.util.concurrent包中的集合

ConcurrentHashMap和HashTable都是线程安全的集合，它们的不同主要是加锁粒度上的不同。HashTable的加锁方法是给每个方法加上synchronized关键字，这样锁住的是整个Table对象。而ConcurrentHashMap是更细粒度的加锁
在JDK1.8之前，ConcurrentHashMap加的是分段锁，也就是Segment锁，每个Segment含有整个table的一部分，这样不同分段之间的并发操作就互不影响
JDK1.8对此做了进一步的改进，它取消了Segment字段，直接在table元素上加锁，实现对每一行进行加锁，进一步减小了并发冲突的概率

CopyOnWriteArrayList和CopyOnWriteArraySet
它们是加了写锁的ArrayList和ArraySet，锁住的是整个对象，但读操作可以并发执行

除此之外还有ConcurrentSkipListMap、ConcurrentSkipListSet、ConcurrentLinkedQueue、ConcurrentLinkedDeque等，至于为什么没有ConcurrentArrayList，原因是无法设计一个通用的而且可以规避ArrayList的并发瓶颈的线程安全的集合类，只能锁住整个list，这用Collections里的包装类就能办到

6、HashMap和hashTable的区别？

HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和value

Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value

7、hashCode的作用？如何重载hashCode方法？

hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；如果两个对象相同，就是适用于equals(Java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object)方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”。

总结：再归纳一下就是hashCode是用于查找使用的，而equals是用于比较两个对象的是否相等的。