你要的hashMap解读来了

　　最近快到金三银四了，不少小伙伴又开始忙忙碌碌找工作了，我也是，秉着为自己也为大家，整理了下hashMap的知识点，希望能对你有所帮助！
　　这里主要是对jdk1.7和jdk1.8的分析  JDK1.7 hashMap结构图
　　img  1.7 hashMap变量初始容量16  负载因子0.75  数组节点类型是  Entry  put函数过程 public V put(K key, V value) {             // 容量为空 则初始化         if (table == EMPTY_TABLE) {             inflateTable(threshold);         }         // key为null 则进行put key为null的操作         if (key == null)             return putForNullKey(value);             // 求hash值 根据hashCode 再进行一些位运算 降低hash冲突的概率         int hash = hash(key);             // 根据元素hash值 求索引         int i = indexFor(hash, table.length);         for (Entry e = table[i]; e != null; e = e.next) {             Object k;             // 如果元素hash值和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;     } hash函数过程hash冲突的解决办法：
　　开放定址法
　　再哈希法
　　链地址法（拉链法,hashMap使用）       /**      * Retrieve object hash code and applies a supplemental hash function to the      * result hash, which defends against poor quality hash functions.  This is      * critical because HashMap uses power-of-two length hash tables, that      * otherwise encounter collisions for hashCodes that do not differ      * in lower bits. Note: Null keys always map to hash 0, thus index 0.      */     final int hash(Object k) {         int h = hashSeed;         if (0 != h && k instanceof String) {             return sun.misc.Hashing.stringHash32((String) k);         }          h ^= k.hashCode();          // This function ensures that hashCodes that differ only by         // constant multiples at each bit position have a bounded         // number of collisions (approximately 8 at default load factor).         h ^= (h >>> 20) ^ (h >>> 12);         return h ^ (h >>> 7) ^ (h >>> 4);     }  求索引位置 indexFor函数// jdk1.7  求索引位置函数    static int indexFor(int h, int length) {         // assert Integer.bitCount(length) == 1 : ＂length must be a non-zero power of 2＂;         return h & (length-1);     } 扩容过程1.addEntry函数    /**      * Adds a new entry with the specified key, value and hash code to      * the specified bucket.  It is the responsibility of this      * method to resize the table if appropriate.      * 添加元素      * Subclass overrides this to alter the behavior of put method.      */     void addEntry(int hash, K key, V value, int bucketIndex) {         // 当前容量大于等于负载数 且当前位置首个元素不为空         if ((size >= threshold) && (null != table[bucketIndex])) {             // 扩容为原来的两倍             resize(2 * table.length);             hash = (null != key) ? hash(key) : 0;             bucketIndex = indexFor(hash, table.length);         }          createEntry(hash, key, value, bucketIndex);     } 2.resize函数    /**      * Rehashes the contents of this map into a new array with a      * larger capacity.  This method is called automatically when the      * number of keys in this map reaches its threshold.      *      * If current capacity is MAXIMUM_CAPACITY, this method does not      * resize the map, but sets threshold to Integer.MAX_VALUE.      * This has the effect of preventing future calls.      *      * @param newCapacity the new capacity, MUST be a power of two;      *        must be greater than current capacity unless current      *        capacity is MAXIMUM_CAPACITY (in which case value      *        is irrelevant).      */     void resize(int newCapacity) {         Entry[] oldTable = table;         int oldCapacity = oldTable.length;         if (oldCapacity == MAXIMUM_CAPACITY) {             threshold = Integer.MAX_VALUE;             return;         }            // 创建新数组         Entry[] newTable = new Entry[newCapacity];                  // 元素重新求索引位置 元素从旧数组移到新数组上         transfer(newTable, initHashSeedAsNeeded(newCapacity));         table = newTable;                  // 设置新的负载数         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);     }      /**      * Transfers all entries from current table to newTable.      */     void transfer(Entry[] newTable, boolean rehash) {         int newCapacity = newTable.length;         for (Entry e : table) {             while(null != e) {                 Entry next = e.next;                 if (rehash) {                     e.hash = null == e.key ? 0 : hash(e.key);                 }                 int i = indexFor(e.hash, newCapacity);                 e.next = newTable[i];                 newTable[i] = e;                 e = next;             }         }     } 移除    /**      * Removes the mapping for the specified key from this map if present.      *      * @param  key key whose mapping is to be removed from the map      * @return the previous value associated with key, or      *         null if there was no mapping for key.      *         (A null return can also indicate that the map      *         previously associated null with key.)      */     public V remove(Object key) {                  // 移除key对应的元素 并返回entry         Entry e = removeEntryForKey(key);         return (e == null ? null : e.value);     }              /**      * Removes and returns the entry associated with the specified key      * in the HashMap.  Returns null if the HashMap contains no mapping      * for this key.      */     final Entry removeEntryForKey(Object key) {         if (size == 0) {             return null;         }         int hash = (key == null) ? 0 : hash(key);                  // 根据元素hash值求索引         int i = indexFor(hash, table.length);                  // 桶的首个节点         Entry prev = table[i];         Entry e = prev;          while (e != null) {             Entry next = e.next;             Object k;                          // 判断元素是否和移除的元素key和hash值相同 ，相同则进行移除操作             if (e.hash == hash &&                 ((k = e.key) == key || (key != null && key.equals(k)))) {                 modCount++;                 size--;                                  // 如果 桶的首个元素和被移除的元素相同 则将next 置为桶的首个元素                 if (prev == e)                     table[i] = next;                 else                     prev.next = next;                 e.recordRemoval(this);                 return e;             }             prev = e;             e = next;         }          return e;     } get函数（根据key获取entry）public V get(Object key) {     if (key == null)         return getForNullKey();     Entry entry = getEntry(key);      return null == entry ? null : entry.getValue(); }  final Entry getEntry(Object key) {     if (size == 0) {         return null;     }      int hash = (key == null) ? 0 : hash(key);          // 遍历索引上的链表     for (Entry e = table[indexFor(hash, table.length)];          e != null;          e = e.next) {         Object k;         // hash值相同 key也相等 则返回entry元素         if (e.hash == hash &&             ((k = e.key) == key || (key != null && key.equals(k))))             return e;     }     return null; } 缩容
　　无  JDK1.8 hashMap1.8 hashMap 变量初始容量16  负载因子0.75  数组节点类型是  Node  TREEIFY_THRESHOLD 链表节点数大于 TREEIFY_THRESHOLD 转变为红黑树 image-20230202205319483  put函数过程    /**      * 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;         // 数组为空 或长度为0 初始化数组         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;                          // 如果put的元素为桶的首个节点，e赋值             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);                                                  // 链表长度大于 TREEIFY_THRESHOLD 链表转红黑树                         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;                 }             }                          // 统一处理，value值             if (e != null) { // existing mapping for key                 V oldValue = e.value;                 if (!onlyIfAbsent || oldValue == null)                     e.value = value;                 afterNodeAccess(e);                 return oldValue;             }         }         ++modCount;         // size大于负载*容量时，扩容         if (++size > threshold)             // 扩容             resize();         afterNodeInsertion(evict);         return null;     } hash函數    static final int hash(Object key) {         int h;                  // hashCode值 与 hashCode值右移16位做异或 得出来的值 高低位特征都有保留 扰动效果更好         return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);     } 扩容过程 函数resize final Node[] resize() {         Node[] 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;             }             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);         }         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[] newTab = (Node[])new Node[newCap];         table = newTab;         if (oldTab != null) {             for (int j = 0; j < oldCap; ++j) {                 Node e;                 if ((e = oldTab[j]) != null) {                     oldTab[j] = null;                     if (e.next == null)                         newTab[e.hash & (newCap - 1)] = e;                     else if (e instanceof TreeNode)                         ((TreeNode)e).split(this, newTab, j, oldCap);                     else { // preserve order                         Node loHead = null, loTail = null;                         Node hiHead = null, hiTail = null;                         Node next;                         do {                             next = e.next;                             if ((e.hash & oldCap) == 0) {                                 if (loTail == null)                                     loHead = e;                                 else                                     loTail.next = e;                                 loTail = e;                             }                             else {                                 if (hiTail == null)                                     hiHead = e;                                 else                                     hiTail.next = e;                                 hiTail = e;                             }                         } while ((e = next) != null);                         if (loTail != null) {                             loTail.next = null;                             newTab[j] = loHead;                         }                         if (hiTail != null) {                             hiTail.next = null;                             newTab[j + oldCap] = hiHead;                         }                     }                 }             }         }         return newTab;     }
　　1.8的resize和1.7最大不同就是，元素重新求索引位置，不是单纯求 hash & (length-1),而是看元素key的hash值在newCap-1 的高位是1还是0，如果是1 元素索引位置+oldCap，如果是0元素索引位置保持不变。  get函数（和1.7类似）    final Node getNode(int hash, Object key) {         Node[] tab; Node first, e; int n; K k;         if ((tab = table) != null && (n = tab.length) > 0 &&             (first = tab[(n - 1) & hash]) != null) {             if (first.hash == hash && // always check first node                 ((k = first.key) == key || (key != null && key.equals(k))))                 return first;             if ((e = first.next) != null) {                 if (first instanceof TreeNode)                     return ((TreeNode)first).getTreeNode(hash, key);                 do {                     if (e.hash == hash &&                         ((k = e.key) == key || (key != null && key.equals(k))))                         return e;                 } while ((e = e.next) != null);             }         }         return null;     } 缩容
　　注意当链表长度小于6时，红黑树会变为链表  面试考点JDK1.7，hashMap使用头插法为什么会造成死循环？ void transfer(Entry[] newTable, boolean rehash) {         int newCapacity = newTable.length;         for (Entry e : table) {             while(null != e) {                 // 第一处                 Entry next = e.next;                 if (rehash) {                     e.hash = null == e.key ? 0 : hash(e.key);                 }                 int i = indexFor(e.hash, newCapacity);                 e.next = newTable[i];                 newTable[i] = e;                 e = next;             }         }     }
　　原因是 多线程并发扩容时，假设A,B两个线程，当A线程执行完 第一处 ，时间片耗尽，线程B按照头插法，完成了完整扩容，此时链表相对于原来是逆序，A线程再继续顺序执行，会造成指针混乱，于是出现死循环。 为什么容量是2的指数幂？
　　有两点，更好的得到新索引和 搭配数组的length-1 可以使 hash%(length) == hash & (length-1) 作用相等  更好的得到新索引，打个比方 容量如果一开始时 8 ，后面扩容成16 从二进制上看只有最高位不同（length最高位后面都是0），所以在扩容的时候，需要重新用元素的hash值和length-1求余 实际上只有最高位不同，其他位不变，修改的数据少了，提高了代码的执行效率（1.7这样写，但是没利用到，但是1.8利用了这个特点）  image-20230201115404578  如果扩容不是2的指数幂，那么扩容后的长度低位不会那么均匀，（试想下，如果低位有0的话，是不是每个hash值在这个位置都是0，大大提高了hash冲突的概率，是2的指数幂低位，length-1 低位全是1）  也能更好的降低hash冲突的概率  搭配数组的length-1 可以使 hash%(length) == hash & (length-1) 作用相等  如果使用自定义对象作为hashMap的key 为什么一定需要重写hashCode和equals方法？
　　因为hashMap插入元素,会用到hashCode计算hash值 ，如果没有重写的话，默认使用Object的实现，即对象的内存地址 HashMapKey k1 = new HashMapKey(1); HashMapKey k2 = new HashMapKey(1); HashMap map = new HashMap<>(); map.put(k1, ＂test＂); System.out.println(＂map.get(k2) : ＂ + map.get(k2));
　　上面的例子，如果沒有重写hashCode的话，k1和k2元素肯定不在数组的同一个位置上，因为hashCode使用的是内存地址，所以 map.get(k2)=null
　　那为什么要重写equals呢？
　　因为获取元素需要用到equals方法  HashMapKey k1 = new HashMapKey(1); HashMapKey k2 = new HashMapKey(1); HashMap map = new HashMap<>(); map.put(k1, ＂test＂); System.out.println(＂map.get(k2) : ＂ + map.get(k2));
　　还是上面的例子，k1和k2，不管有没有重写hashCode 都有可能hash值相等（不同元素的hash可能相等），假设k1和k2的hash值相等，当根据key获取元素时,不但会判断元素的hash值还会判断key之间是否equals，如果没有重写equals方法（equals默认对象的内存地址）,k1和k2的内存地址肯定不相同，所以 map.get(k2)=null
　　总结：使用自定义对象作为hashMap的key 一定需要重写hashCode和equals方法，set集合比较，去重时（先比较hash，hash相同在比较equals），所以一样需要重写。  HashMap线程不安全的体现：JDK1.7 HashMap线程不安全体现在：死循环、数据丢失  JDK1.8 HashMap线程不安全体现在：数据覆盖  思考问题
　　谈谈你理解的 HashMap，讲讲其中的 get put 过程。 1.8 做了什么优化？ 是线程安全的嘛？ 不安全会导致哪些问题？ 如何解决？有没有线程安全的并发容器？ ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？  引用
　　https://crossoverjie.top/2018/07/23/java-senior/ConcurrentHashMap/#HashMap
　　有问题，欢迎私信我哦