HashMap

equals 方法

JAVA当中所有的类都是继承于Object这个超类的，在Object类中定义了一个equals的方法，equals的源码是这样写的：

public boolean equals(Object obj) {
    //this - s1
    //obj - s2
    return (this == obj);   //引用数据类型：当他们用（==）进行比较的时候，比较的是他们在内存中的存放地址（确切的说，是堆内存地址）。
}

可以看到，这个方法的初始默认行为是比较对象的内存地址值，一般来说，意义不大。所以，在一些类库当中这个方法被重写了，如String、Integer、Date。在这些类当中equals有其自身的实现（一般都是用来比较对象的成员变量值是否相同），而不再是比较类在堆内存中的存放地址了。
所以说，对于复合数据类型之间进行equals比较，在没有覆写equals方法的情况下，他们之间的比较还是内存中的存放位置的地址值，跟双等号（==）的结果相同；如果被复写，按照复写的要求来。

Hashcode 的作用

HashMap 的添加、获取时需要通过 key 进行 hash()得到 hashCode ，然后计算下标 ( n-1 & hash)，从而获得要找的同的位置。当发生冲突（碰撞）时，利用 key.equals() 方法去链表或树中去查找对应的节点。

Hash

Hash是散列的意思，就是把任意长度的输入，通过散列算法变换成固定长度的输出，该输出就是散列值。关于散列值，有以下几个关键结论：

• 如果散列表中存在和散列原始输入K相等的记录，那么K必定在f(K)的存储位置上
• 不同关键字经过散列算法变换后可能得到同一个散列地址，这种现象称为碰撞

• 如果两个Hash值不同（前提是同一Hash算法），那么这两个Hash值对应的原始输入必定不同

  HashCode

• HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的

• 如果两个对象equals相等，那么这两个对象的HashCode一定也相同
• 如果对象的equals方法被重写，那么对象的HashCode方法也尽量重写
• 如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置

  总结

1. hashCode() 在散列表中才有用，在其它情况下没用
2. 哈希值冲突了场景，hashCode相等，但equals不等 (equals就是内存地址，hashcode只不过是内存地址的表示)
3. hashcode：计算键的hashcode作为存储键信息的数组下标用于查找键对象的存储位置

4. equals：HashMap使用equals()判断当前的键是否与表中存在的键相同。

   • 如果两对象equals()是true,那么它们的hashCode()值一定相等，
   • 如果两对象的hashCode()值相等，它们的equals不一定相等（hash冲突啦）
   • 注：Hash冲突的四种解决办法

     HashMap

     
     数组
     数组存储区间连续，占用内存比较严重，空间复杂度很大。但数组的二分查找时间复杂度小，为O(1)；
     数组的特点是：寻址容易，插入和删除困难；
     链表
     链表存储区间离散，占用内存比较宽松，空间复杂度很小，但时间复杂度很大，达O（N）。
     链表的特点是：寻址困难，插入和删除容易。
     HashMap
     （1.7 数组+链表；1.8 数组+链表+红黑树）是用得最多的一种键值对存储的集合， 用一个数组来存储元素，但是这个数组存储的不是基本数据类型。HashMap实现巧妙的地方就在这里，数组存储的元素是一个Entry类，这个类有三个数据域，key、value（键值对），next(指向下一个Entry) 。
     特点：HashMap允许空键值，并且它是非线程安全的，所以插入、删除和定位元素会比较快。

5. HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

6. HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
7. HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null，其中HashMap最多只允许一条记录的键为Null，允许多条记录的值为Null。此外，HashMap中的映射不是有序的。
8. HashMap 的实例有两个参数影响其性能：“初始容量” 和 “加载因子”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
9. 通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。
10. HashMap 是一个最常用的Map，它根据键的HashCode 值存储数据，根据键可以直接获取它的值，具有很快的访问速度。遍历时，取得数据的顺序是完全随机的。
11. HashMap最多只允许一条记录的键为Null；允许多条记录的值为 Null。

12. HashMap不支持线程的同步（即任一时刻可以有多个线程同时写HashMap），可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。

    HashMap的时间复杂度

    HashMap在jdk1.8之后引入了红黑树的概念，表示若桶中链表元素超过8时，会自动转化成红黑树；
    若桶中元素小于等于6时，树结构还原成链表形式。
    原因：
    红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
    还有选择6和8的原因是：
    中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。
    不管插入还是查找，由key获取hash值然后定位到桶的时间复杂度都是O（1），那么真正决定时间复杂度的实际上是桶里面链表/红黑树的情况
    如果桶里面没有元素，那么直接将元素插入/或者直接返回未查找到，时间复杂度就是O（1），如果里面有元素，那么就沿着链表进行遍历，时间复杂度就是O（n），链表越短时间复杂度越低，如果是红黑树的话那就是O（logn）
    所以平均复杂度很难说，只能说在最优的情况下是O（1）

    HashMap的put方法

    大体流程：

13. 根据 key 通过哈希算法拿到一个 HashCode 结合与操作，与数组的长度-1进行运算，得到一个数组下标

14. 如果得到的数组下标位置元素为空，则将key和value封装成Entry对象（1.7为Entry对象，1.8为Node对象）并放入该位置。

15. 如果下标元素不为空，需要分情况讨论
    a. 1.7 首先需要判断需不需要扩容，需要的话先扩容，如果不需要扩容则将Key和Value封装成Entry对象，采用头插法插入当前位置链表中。
    b. 1.8 需要先判断是红黑树Node还是链表Node

    • 如果是红黑树则需要将Key和Value封装成红黑树节点添加到红黑树中，在添加的过程中会判断是否包含节点，如果包含则更新
    • 如果是链表则先将Key和Value封装成Node节点，采用尾插法进行插入，如果插入的过程中包含此节点则更新，如果没有则插入到最后。插入完之后如果节点个数大于等于8则转为红黑树存储。
    • 插入完成之后则判断是否需要扩容，需要扩容则扩容，不需要则结束PUT方法。 ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); //将Key进行hash 得到 hashcode —> （hash(key)） }

    /**

    • Implements Map.put and related methods. *
    • @param hash hash for key
    • @param key the key
    • @param value the value to put
    • @param onlyIfAbsent if true, don’t change existing value
    • @param evict if false, the table is in creation mode.

    • @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

              boolean evict) {

      Node[] tab; Node p; int n, i; // 步骤①：tab为空则创建 if ((tab = table) == null || (n = tab.length) == 0)

       n = (tab = resize()).length;

      // 步骤②：计算index，并对null做处理 if ((p = tab[i = (n - 1) & hash]) == null) // 得到的 hashcod e与数组长度-1进行与运算 得到一个数组下标

       tab[i] = newNode(hash, key, value, null);     // 元素为空则放入

      else {

       Node<K,V> e; K k;
       // 步骤③：节点key存在，直接覆盖value
       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) {
                   //链表长度大于8转换为红黑树进行处理
                   p.next = newNode(hash, key, value, null);
                   if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                       treeifyBin(tab, hash);
                   break;
               }
               // key已经存在直接覆盖value
               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;

      // 步骤⑦：超过最大容量 就扩容 if (++size > threshold)

       resize();

      afterNodeInsertion(evict); return null; } ```

      

      HashMap的get方法

      

      HashMap的resize方法

      主要流程是把hashmap中的table变成一个2倍table的过程，最主要的也是最难的地方在于如何把已经存入到table中的数据快速、安全、准确的放到新的table表中。
      
      上面处理的情况是在老的table上第j项是一个链表结构的情况，主要流程如下

16. 新建低位链表、高位链表；

17. 遍历table[j]上的链表元素，通过链表元素的hash与table的长度判断元素是应该在高位还是低位链表；
18. 把低位链表设置在新的table的第j项，把高位链表设置在新table的（j+老table）项；

    HashMap线程不安全

    原因：resize 、put 方法没上锁（本身设计的时候就是按照不安全设计的）
    1. 多线程下扩容（resize 方法）会死循环（JDK 7 中的问题，JDK 8 进行了修复）
    2. 多线程下 put 会导致元素丢失 （多线程同时执行 put 操作时，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。）
    3. 扩容时put 和 get 并发时会导致 get 到 null（resize方法中线程 A 执行完 table = newTab 之后，线程 B 中的 table 此时也发生了变化）

HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，此实现不是同步的。jdk 1.8插入是从尾部插入造成数据覆盖，jdk 1.7是从头部插入导致数据丢失或者死循环
总结：1. 多个线程某一时刻同时操作HashMap并执行put，hash值同，需解决冲突。2. put()方法不是同步的 3. addEntry()方法不是同步的 4. resize()扩容方法不是同步的

1. （1.8）put方法不是同步的,获取位置，与设置值是两个步骤

   if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

2. （1.7）addEntry()方法不是同步的，在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失 ```java

void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }

3. 删除键值对，当多个线程同时操作同一个数组位置的时候，也都会**先取得现在状态下该位置存储的头结点，然后各自去进行计算操作**，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会**覆盖其他线程的修改**
```java
final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

1. resize()扩容方法不是同步的,addEntry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作,这个操作会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。（线程 A 执行完 table = newTab 之后，线程 B 中的 table 此时也发生了变化，此时去 get 的时候当然会 get 到 null 了，因为元素还没有转移。）而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

   final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再扩充了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的resize上限
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
   }

   HashTable

   HashTable 是 Map 接口线程安全版本的实现类，数据结构和方法实现与 HashMap 类似，不过目前基本上被弃用。
   是基于HashCode实现的（数组+链表），但它是线程安全的，无论key还是value都不能为null，所以会比HashMap效率低，而且不允许null值。
   PUT的方法和HashMap差不多，但是每个方法都是synchronized，所以Hashtable是一个线程安全的类。

   ConcurrentHashMap

   jdk1.7采用分段锁机制对整个桶数组进行了分割分段（Segment），segment继承自ReetrantLock，每一把锁只锁容器中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提供了并发访问率；
   jdk1.8 采用CAS + synchronized，是对hashtable进行优化，将锁细粒化到每个table的每个元素，来提升并发性能。jdk1.8 彻底放弃segment 而采用node，不再使用分段锁。 利用 CAS 尝试写入，失败则自旋保证成功,利用 synchronized 锁写入数据。

   TreeMap

   是基于红黑树实现的，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；

   LinkedHashMap

   LinkedHashMap是HashMap的子类，但是内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中。LinkedHashMap支持两种顺序插入顺序 、 访问顺序

2. 插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。也可以在构造时带参数，按照应用次数排序。

3. 访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。
4. 速度慢：在遍历的时候会比HashMap慢，不过有种情况例外：当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢。因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。

参考资料

• HashMap？ConcurrentHashMap？相信看完这篇没人能难住你！
• 京东一面：为什么 HashMap 是线程不安全的？
• HashMap（1.7、1.8对比）、Hashtable、ConcurrentHashMap（1.7、1.8）
• HashMap、ConcurrentHashMap(1.7和1.8的不同实现)、HashTable的区别
• HashMap有几种遍历方法
• 快速弄懂hashmap主要方法实现
• HashMap夺命14问，你能坚持到第几问？
• 讲讲HashCode的作用
• HashMap原理详解
• Map集合的五种遍历方式及Treemap方法
• hashmap实现原理浅析
• HashSet的value值为什么是个Object对象呢？