好放难取更难删：以查询121为例，先对121取模找到他应该存放的位置：20；2.发现索引为20的位置的元素并不是121，继续向后查询(从20这个位置开始向后遍历)直到找到121为止，21这个位置就找到了121，存在。以查询20为例，先对20取模，得到查询的位置索引为20，从索引20位置开始向后遍历数组，不断找20这个元素，走到数组结尾还没找到，说明不存在。观察发现，当元素不存在时就变成遍历数组查找了，效率比较低。

b.再哈希/二次探测：再对冲突的key值取模

c.闭散列总结：闭散列方式最大的问题就在于，若整个哈希表冲突比较严重，此时查找元素的过程就相当于遍历数组，查找效率退化为O(N)。

2）开散列(冲突位置变为链表)

当发生冲突时，就让冲突位置变为链表（既简单又实用）

所谓的开散列方案就是把单纯的数组变为数组+链表的方式，当发生哈希碰撞时就将对应冲突位置的元素转换为链表，之后的查询和删除操作都是针对这个单个链表来进行处理。

eg:

线性探测法（闭散列）。等概率平均查找：平均查找长度=这六个元素在哈希表中查找的总次数/6。

拓展：若转为开散列查找呢？

3.开散列下冲突严重时(导致链表过长)的优化

1）整个哈希表进行扩容

假设以前%7（数组长度为7），现在就扩容为原数组的一倍，现在%14（数组长度变为14），就可以大大降低冲突的概率，减少链表长度（C++中）。

2）单个链表转为哈希表或者变为搜索树

单个链表长度过长，查询效率就会变为链表的遍历O(N)，就针对这单个链表进行转换处理：可以把单个链表转为哈希表或者变为搜索树（JDK8的HashMap就采用此方案，当某个链表的长度>8且整个哈希表元素个数>64，把此链表转为RBTree【源码解读处有】）(java)

4.负载因子

1.负载因子越大，发生哈希冲突的概率越大，数组长度就会偏小，但节省空间

2.负载因子越小，发生哈希冲突的概率越小，数组长度就会偏大，但浪费空间

3.负载因子取多大，要根据当前系统需求做实验得知，JDKHashMap的负载因子是0.75。【不同情况下负载因子可能不同，阿里内部对于负载因子建议取值为10，允许每个链表的平均长度为10以内，可以接收】。

4.当元素个数/负载因子>=数组长度，此时我们认为冲突比较严重，需要进行扩容，即假设此时HashMap的哈希表长度为16，当元素个数超过12就会发生扩容。

负载因子就是在空间和时间上求平衡（即它不是固定的，是一个可以动态变化的）

%err:发生哈希碰撞概率，prime:建议的负载因子取值

四、实现哈希表

1.添加一个键值对


/**
 * 基于开散列方案下的哈希表实现
 */
public class MyHashMap {
 
    private class Node{
        //对key求哈希运算
        int key;
        int value;
        //发生哈希碰撞时转链表就用next属性存储它的下一个节点
        Node next;
 
        public Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }
    //当前哈希表中实际存储元素的个数
    private int size;
    //默认哈希表的长度
    //也有的教科书将每个哈希表的数组元素称为哈希桶
    private static final int DEFAULT_CAPACITY=16;
    //默认负载因子
    private static final double LOAD_FACTOR=0.75;
    //取模数，用于取到key的索引
    private int M;
    //实际存储数据的数组：Node数组
    private Node[] data;
    public MyHashMap(){
        this(DEFAULT_CAPACITY);
    }
    public MyHashMap(int initCap) {
        this.data=new Node[initCap];//可以从外部传入
        this.M=initCap;//initCap:长度//数组长度赋给取模数(对数组长度取模)
    }
    public int hash(int key){//哈希方法
        return Math.abs(key)%M;//对key直接做绝对值对M取模
    }
 
    /**
     * 在当前哈希表中添加一个键值对 key=value
     * @param key
     * @param value
     */
    public int add(int key,int value){
        //1.先对key取模，得到存储的索引
        int index=hash(key);
        //2.遍历这个索引对应的链表，查看当前key是否已存在
        for(Node x=data[index];x!=null;x=x.next){//每个数组存储的时node节点，每个链表的链表头就存储在数组的索引位置
            if(x.key==key){
                //此时key已经存在，更新value
                int oldValue=x.value;
                x.value=value;
                return oldValue;
            }
        }
        //3.此时key对应的元素在当前哈希表中不存在，新建节点头插在哈希表中
//        Node head=data[index];//原先的头节点
//        Node node=new Node(key,value,head);//对于构造方法，新节点的next要等与head
        Node node=new Node(key,value,data[index]);
        data[index]=node;//最新的链表头要变为当前的node
        size++;
        //4.添加一个新元素后，查看是否需要扩容
        if(size/LOAD_FACTOR>= data.length){
            //size/LOAD_FACTOR>= data.length也可以写成LOAD_FACTOR* data.length<=size
            //TODO:哈希表的扩容： resize()；
        }
        return value;
    }
}

Test:添加元素的测试：


public static void main(String[] args) {
    MyHashMap hashMap=new MyHashMap(4);//数组长度是4
    hashMap.add(1,10);
    hashMap.add(2,20);
    hashMap.add(5,55);
    System.out.println();//在此句前面打个断点观察
}

结果：

2.查询key/value是否存在


/**
 * 查询key是否存在
 * @param key
 * @return
 */
public boolean containsKey(int key){
    int index=hash(key);
    //遍历index位置对应的链表，查看是否有节点的key值与查询的key值相等
    for(Node x=data[index];x!=null;x=x.next){
        if(x.key==key){
            return true;
        }
    }
    return false;
}
 
/**
 * 查询val是否存在
 * 由于val没有对应索引（数组是利用key对应索引存的），所以需要数组全部遍历一遍
 * @param value
 * @return
 */
public boolean containsValue(int value){
    //遍历整个哈希表
    //数组从左到右遍历
    for (int i = 0; i < size; i++) {
        //依次遍历以数组元素为节点的每个链表
        for(Node x=data[i];x!=null;x=x.next){
            if(x.value==value){
                return true;
            }
        }
    }
    return false;
}

Test：


public static void main(String[] args) {
    MyHashMap hashMap=new MyHashMap(4);//数组长度是4
    hashMap.add(1,10);
    hashMap.add(2,20);
    hashMap.add(5,55);
    System.out.println(hashMap.containsKey(1));
    System.out.println(hashMap.containsKey(100));
    System.out.println(hashMap.containsValue(10));
    System.out.println(hashMap.containsValue(0));
}

3.删除key值对应节点


/**
 * 删除哈希表中key值对应的节点
 * 返回待删除的键值对对应的value
 * @param key
 * @return
 */
public int remove(int key){
    int index=hash(key);
    //判断当前链表头节点是否是待删除节点
    Node head= data[index];
    if(head.key==key){
        int val=head.value;
        data[index]=head.next;
        head.next=head=null;//从链表中把这个节点断掉
        size--;
        return val;
    }
    //当前链表头节点不是待删除节点
    Node prev=head;
    while(prev.next!=null){
        if(prev.next.key==key){
            //prev恰好是待删除结点的前驱
            Node cur=prev.next;
            int val=cur.value;
            //删除操作
            prev.next=cur.next;
            cur.next=cur=null;
            size--;
            return val;
        }
        prev=prev.next;
    }
    //走到这此时节点不存在,抛出异常
    throw new NoSuchElementException("no such key!remove error");
}

4.扩容


/**
 * 哈希表扩容
 */
private void resize() {
    //新数组的长度变为原来的一倍
    Node[] newData=new Node[data.length<<1];
    //细节：原节点的key对应新数组的索引hash有变化，现在的取模数应该变为新数组的长度（如之前%4,扩容后就是%8）
    this.M= newData.length;
    //遍历原数组,进行节点的搬移
    for (int i = 0; i < data.length; i++) {
        if(data[i]!=null){
            //对应链表不为空
            //进行链表遍历
            for(Node x=data[i];x!=null;){
                //暂存i索引所在链表对应节点的next(暂存后继节点)
                Node next=x.next;
                //新数组的索引
                int newIndex=hash(x.key);
                //新数组的头插
                x.next=newData[newIndex];
                newData[newIndex]=x;
                //继续进行下一个节点的搬移操作
                x=next;
 
            }
        }else{
            //当前数组对应的i索引下没有节点，无需搬移
            continue;//else这步可以不用写
        }
    }
    //最终只需要data=newData就可以切换成新的哈希表
    data=newData;
}

对如下两行代码的解释：

x.next=newData[newIndex];
newData[newIndex]=x;

五、JDK8的HashMap

源码刨析：如何查看源码->双击shift键

JDK中Set和Map的源码分析：

1.Set和Map集合有何关系？

Set集合下的子类就是Map集合下的子类，HashSet就是HashMap,TreeSet就是TreeMap。在HashSet内部，元素都在HashMap的key存储，之所以Set是不重复的，原因是因为Set中的元素存储在了Map的key上（key不重复），所以Set不重复【Set的E就是Map的key值】。

观察Set集合的方法：

1.调用Set集合的add方法实际上就是调用Map集合的put方法，将Set集合的元素放在key上，val都是同一个空的Object对象。

2.val:

PRESENT(常量)是默认有个空元素，Set中不存在value,所以在map里面存的是空的object对象,所有的Set的value值全是这个空的Object对象。

2.JDK的HashMap源码的大体结构和重点方法

1）大体结构

a）JDK7之前的HashMap是一个基于开散列的散列表实现：数组+链表结构。

b）JDK8之后引入了红黑树：数组+链表（或红黑树），当冲突不严重就是链表，冲突严重就是红黑树。

当某个链表的长度过长时，元素的查询就会退化为链表的遍历，会趋于O(N)时间复杂度，我们把它树化，即使元素个数再多查询效率起码也是O(logN)。

2）冲突严重时，什么时候才会将变为红黑树？

若链表的长度已经>8，但是整个链表的元素个数<64，此时只是做扩容（哈希表长度变为原来的一倍），若链表的长度已经>8，并且整个链表的元素个数>64，此时就将链表转为红黑树。【详细看hashMap属性解读】

3）HashMap的属性解读(重点方法)

1.默认哈希表长度为16，a power of two:哈希表长度必须是2^N

2.HashMap的最大容量：2^30，一个HashMap最多存储2的30次方个节点

3.默认负载因子：0.75

4.⭐链表树化的阈值：是链表还是树根据这个属性判断

5.⭐解树化：当一个RBTree的节点个数小于该值时，会将其再还原为链表

6.⭐树化的另一个判断值：到底是否应该把链表变为红黑树还要看当前整个哈希表的元素个数是否超过这个值，若链表的长度已经>8，但是整个链表的元素个数<64，此时只是做扩容（哈希表长度变为原来的一倍），若链表的长度已经>8，并且整个链表的元素个数>64，此时就将链表转为红黑树。

3.JDK的HashMap中的hash方法的实现

hash=h^(h>>>16):这个不是最后索引，只是得到了一个比较均匀的hash后的整数。最终索引值=（数组长度-1）&上一步得到的hash【这里也体现了数组长度n为什么得是2^N,因为当数组长度是2^N时，最终索引值的这个&运算等价于hash%N】。

总结：

在自主实现的hash表中我们采取的时hash%n，而在此处源码中我们采用的是(n-1)&hash的与运算操作，这两者得到的值都是相同的，但是与运算运行速度更快，效率高，所以源码中采取了与运算。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/酷酷是懒虫/article/detail/890921