手撕HashMap（1.7）

思路

本质其实就是数组+链表，我们的数组主要查询速度很快，我们每次放入元素，会验证它的位置是否冲突->如果该位置没人，我们就会进入addEntry方法，创建一个当前空节点（比如当前i位置），是一个空节点，然后我们再将赋值的新节点平替当前i位置节点，然后next为空节点；

插入：

如果当前位置有节点，也就是不为空，就会得到它的next，比如上面的i位置，它现在是有值的，但是它的next就是之前的空节点所以当前位置节点下一位置为null，然后我们验证hash值比较，发现key、hash值都不等（毕竟是空节点）->然后我们就会再次进入addEntry方法，一样的思路，空节点会后置，此时插入成功

 那么，哈希冲突是怎么解决的呢？

这里设置的很巧妙，其实我上述已经说了，当两个相同key插入时，后插入的发现已经有值了，就会对它的next进行操作，对比它的hash以及key，next为空所以插入，从而有效达到哈希冲突的解决；

如果key不相同，说明它的位置肯定就不一样，位置的判断——>用key的hash值然后位运算与数组长度与运算获得

后续操作与上述一样

public V put(K key, V value) {
		if (key == null)
			return putForNullKey(value);
		int hash = myHash(key);
		int i = indexForTable(hash, CAPACITY);
 
		for (MyEntry<K, V> e = table[i]; e != null; e = e.next) {
			if (e.hash == hash && (e.key == key || e.key.equals(key))) {
				V old = e.value;
				e.value = value;
				return old;
			}
		}
 
		addEntry(hash, key, value, i);
 
		return null;
	}

 得到位置：

根据key得到hash值，然后进行高位运算

为什么要进行高位运算？

这里体现出了HashMap的容量为什么是2的n次幂

因为hash值时整数->高位位运算得到一个很大的值，这样就保证了我们后面hash&数组-1的低位是有效的，保证了位置都在数组范围内；

模运算不是也可以吗？

如果用(hash % capicity)当然也能得到相同的结果，但是因为位运算的效率更高，所以当然要选择与运算，当然这是不一定的

(30条消息) HashMap中的hash()函数以及如何通过哈希值确定下标_KKKLxxx的博客-CSDN博客_hashmap如何计算下标

(30条消息) Java 位运算和普通运算，效率比较_Magicflowersbloom的博客-CSDN博客_位运算为什么效率高

  /**
     * 6.计算机key的hash值
     */
    private int MyHash(K key) {
        if (key == null) {
            return 0;
        }
        int h = key.hashCode();
        h = h ^ (h >>> 16);
 
        return h;
    }

/**
     * 2.1插入key！=null的value到哈希表中
     * 计算插入位置：hash&
     */
    private int indexForTable(int hash, int CAPACITY) {
        //hash值与数组长度进行位运算得到下标
        return hash & (CAPACITY - 1);
    }

扩容机制：

我们来说说源码的扩容，当hashmap中的元素个数超过数组大小 * loadFactor（负载因子）时，就会进行数组扩容，loadFactor的默认值（DEFAULT_LOAD_FACTOR）是0.75这是一个折中的取值，也就是说，默认情况下数组大小为16，那么当hashmap中的元素个数超过16*0.75 = 12 （阈值或者边界值的时候）就把数组的大小扩展为2 * 16 = 32，然后重新计算出每个元素在数组中的位置，而这是一个非常耗性能的操作，所以我们最好能够提前预知并设置元素的个数。

流程：

hashMap首先会创建一个两倍大的新数组，然后我们会将原数组中的值放在我们的新数组中——>这时候需要重新hash——>(因为我们的位置是：hash&（数组.length-1）)，数组长度发生变化所以，肯定是要重新哈希的；——>这里一个很重要的点：

节点迁移1.7使用的头插法，不过多线程下会发送并发死链的现象，1.8采用的尾插法

以下代码的do-while很细节：

先得到原哈希表（数组）里的每个元素e，然后得到它的下一个元素next，不管怎么样是e,e.next还是怎么着，他们的hashcode肯定是一样的，那么重新hash肯定也是一样的

那么我们对e重新hash确定位置，位置为i，此时新哈希表newtable当前位置肯定是null，我们将这个值赋予e.next，e.next=null，这样的目的和插入addEntry方法一样，就是为了让e的下一个节点为null，然后新哈希表当前位置i为e（newtable[i]=e）,然后将Entry链上下一个值给到e（e=next）——>此时e就是第二个节点了，一直循环至e！=null

private void resize() {
		CAPACITY= CAPACITY* 2;
		MyEntry[] newtable = new MyEntry[CAPACITY];
		for (Entry<K, V> entry : table) {
			MyEntry<K, V> e = entry; // 取得旧Entry数组的每个元素
			if (e != null) {
				entry = null;// 释放旧Entry数组的对象引用（循环后，旧的Entry数组不再引用任何对象）
				do {
					MyEntry<K, V> next = e.next;
					int i = indexForTable(e.hash, capacity); // 重新计算每个元素在数组中的位置
					e.next = newtable[i]; 
					newtable[i] = e; // 将元素放在数组上
					e = next; // 访问下一个Entry链上的元素
				} while (e != null);
			}
		}
		table = newtable;
	}

代码

package com.wyh;
 
import java.util.Map;
 
/**
 * @author diao 2022/6/29
 */
public class MyHashMap<K, V> {
    private int CAPACITY = 16;
    private int size = 0;
    private MyEntry[] table;
 
 
    /**
     * 1.构造HashMap
     * 传阈值CAPACITY情况
     * 初始化哈希表，设置初始一个阈值
     *
     * @param CAPACITY
     */
    public MyHashMap(int CAPACITY) {
        this.CAPACITY = CAPACITY;
        this.table = new MyEntry[CAPACITY];
    }
 
    /**
     * 默认情况
     */
    public MyHashMap() {
        this.table = new MyEntry[CAPACITY];
    }
 
    /**
     * 2.传入值
     * 传入值
     */
    public V put(K key, V value) {
        if (key == null) {
            return putForNullKey(value);
        }
 
        //1.当key不为null,计算hash值->得到下标
        int hash = MyHash(key);
        int index = indexForTable(hash, CAPACITY);
 
        //2.当表当前位置不为空说明有人了，进行插入替换该值（这里没有解决hash冲突）
        for (MyEntry<K, V> e = table[index]; e != null; e = e.next) {
 
            //3.如果哈希表上该位置hash与你key的hahs相等就赋值返回
            if (e.hash == hash && (e.key == key || e.key.equals(key))) {
                e.value = value;
                V old = value;
                return old;
            }
        }
 
        //4.当前表index位置没有元素进行插入
        addEntry(hash, key, value, index);
        return null;
    }
 
    /**
     * 2.1插入key！=null的value到哈希表中
     * 计算插入位置：hash&
     */
    private int indexForTable(int hash, int CAPACITY) {
        //hash值与数组长度进行位运算得到下标
        return hash & (CAPACITY - 1);
    }
 
 
    /**
     * 3.插入key=null的value
     * key为null传入值情况
     */
    private V putForNullKey(V value) {
        //从哈希表的一个元素开始遍历->直至找到为null的key
        for (MyEntry<K, V> e = table[0]; e != null; e = e.next) {
 
            //给当前key为空对应的value赋值
            if (e.key == null) {
                e.value = value;
                V old = value;
                return old;
            }
        }
 
        //添加新的节点
        addEntry(0, null, value, 0);
        return null;
    }
 
    /**
     * 4.给数组添加新节点
     * 因为遍历HashEntry可能key都不为空，我们可以拓展一个HashEntry
     * 比如之前传空key而哈希表又满了，hash传入0，key=null，value，i=0
     */
    private void addEntry(int hash, K key, V value, int i) {
 
        //1、这里插入的策略是直接前面第一个插入一个,并且赋值
        MyEntry<K, V> e = table[i];
        table[i] = new MyEntry<K, V>(hash, key, value, e);
 
        //2、插入后，判断HashEntry是否达到阈值
        if (size == CAPACITY) {
            //达到阈值扩容
            resize();
        }
 
        size++;
    }
 
    /**
     * 5.扩容机制
     * 重置HashEntry数组，当size达到阈值时
     */
    private void resize() {
        CAPACITY=CAPACITY*2;
 
        //1.重新创建扩容后的一个Hash表
        MyEntry[] newtable = new MyEntry[CAPACITY];
 
        //2.然后将原来的hash表赋值上去
        for (MyEntry<K,V> entry : table) {
            MyEntry<K, V> e = entry;
            if (e != null) {
                entry = null;//释放旧的哈希表的元素
                do {
                    MyEntry<K, V> next = e.next;
                    int i = indexForTable(e.hash, CAPACITY); // 重新计算每个元素在数组中的位置
                    e.next = newtable[i];
                    newtable[i] = e; // 将元素放在数组上
                    e = next; // 访问下一个Entry链上的元素
                } while (e != null);
            }
        }
    }
 
    /**
     * 6.计算机key的hash值
     */
    private int MyHash(K key) {
        if (key == null) {
            return 0;
        }
        int h = key.hashCode();
        h = h ^ (h >>> 16);
 
        return h;
    }
 
    /**
     * 7.取值
     */
    public V get(K key){
        //1.当键为空值
        if(key==null){
            return getForNullKey();
        }
 
        //2.当不为空key
        int hash = MyHash(key);
        int index = indexForTable(hash, CAPACITY);
 
        //2.2得到表当前位置，然后遍历，get值
        for (MyEntry<K,V>e=table[index];e!=null;e=e.next){
            if(e.hash==hash&&(e.key==key||e.key.equals(key))){
                return e.value;
            }
        }
        return null;
    }
 
    /**
     * 8.当key为null值取值
     * key为null，从表中的头元素寻找，直至空key为止
     */
    private V getForNullKey(){
        for(MyEntry<K,V>e=table[0];e!=null;e=e.next){
            if(e.key==null) {
                return e.value;
            }
        }
        return null;
    }
 
}
 
 
/**
 * hash表:本质是一个数组
 *
 * @param <K>：键
 * @param <V>：值
 */
class MyEntry<K, V> {
    public int hash;
    public K key;
    public V value;
    //下一个节点
    public MyEntry<K, V> next;
 
    public MyEntry(int hash, K key, V value, MyEntry<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}