HashMap原理

参考链接1：https://zhuanlan.zhihu.com/p/28501879，特别好讲解源码
参考连接2：https://blog.csdn.net/suifeng629/article/details/82179996
讲的面试时候怎么答的
参考链接3：https://blog.csdn.net/vking_wang/article/details/14166593

6、HashMap的实现原理

• 关于hashCode
  1.hashCode是在散列存储结构中确定对象的存储地址的，是查找变得更加快捷，如HashMap、HashTable等
  2.如果两个对象相同，即A.equals(B) 返回true，那么A B的hashCode值一定要相等。
  3.如果对象的equals()方法被重写，那么hashCode也要被重写
  4.如果两个对象的hashCode值相等，并不一定代表两个对象相等（equals方法返回true）,只是代表两个对象存储在同一个篮子里。
  补充：
  1、hashCode值是用来查找的
  在内存中有这样的位置
  0 1 2 3 4 5 6 7
  有个类，类中有个成员变量ID，我们要把这个类的对象存放在以上8个位置之一，如果不用hashCode任意存放，那么下次查找的时候需要遍历。
  但如果用hashcode那就会使效率提高很多。
  定义ID%8为对象的hashCode值，将对象存放在hashCode值的位置处。例如ID为9，9%8=1，存放在1位置，13%8=5，存放在5位置。这样以后查找的时候可以通过ID%8来查找该对象的位置。
  2、如果两个对象的hashCode值相等，可以判断存放到同一个“桶”中，再通过equals判断是否同一个对象。
  重写equals，为什么还要重写hashCode?
  要再某个桶中找东西，需要先找到那个桶。

• 关于equals
  1.equals和==
  ==：基本数据类型，判断值是否相等；引用类型，引用的是否是内存中的同一个对象。
  equals()：==不允许覆盖，可以重写equals()，达到对象内容是否相同的目的
  2.object类的equals()方法的比较规则：如果两个对象的类型一致，并且内容一致，则返回true,这些类有：
  java.io.file,
  java.util.Date,
  java.lang.string,
  包装类（Integer,Double等）
  String s1=new String("abc");
  String s2=new String("abc");
  System.out.println(s1==s2);
  System.out.println(s1.equals(s2));
  运行结果为false true

- HashMap
HashMap是基于哈希表的非同步实现。
哈希表

image.png

实现原理：基于hashing原理，通过put()和get()来实现数据的存储。当我们把key-value传给put()方法时，调用key的hashCode()方法获取HashCode值，找到存储位置,即“桶”位置。当获取对象时，先找到bucket位置，再通过键对象的equals()方法找到正确的键值对，然后返回值Entry对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。

HashMap里面定义了一个内部类，Entry,包括key,value和next.

transient Entry[] table;

Map里面的内容保存在Entry里面。
HashMap在存储时，先找到bucket位置，即下面的index.

// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

HashMap的put()方法
疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？
　　这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value); //null总是放在数组的第一个链表中
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        //遍历链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果key在链表中已存在，则替换为新value
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
    //如果size超过threshold，则扩充table大小。再散列
    if (size++ >= threshold)
            resize(2 * table.length);
}

补充：当然HashMap里面也包含一些优化方面的实现，这里也说一下。比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？HashMap里面设置一个因子，随着map的size越来越大，Entry[]会以一定的规则加长长度。

HashMap的get()方法

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
        e != null;
        e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。
存取总结
归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

HashMap的扩容
当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

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

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？

当单个“bucket”中的元素个数超过8时，将转为红黑树结构

image.png