哈希表(重点)------java

目录

1.哈希表的基本概念

2.什么是哈希冲突，以及哈希冲突的解决办法？（常考，阅读源码）

2.1闭散列

2.2开散列，当发生哈希冲突时，就让冲突位置变为链表。（既简单又实用）

3.关于负载因子 

4.自己实现的哈希表（HashMap）

5. JDK中Set和Map中常见的子类（面试必考常考）

5.1.Set和Map集合有啥关系？（源码）

​5.2JDK的HashMap的源码讲解？大概的结构以及重点方法（源码阅读）​​

5.3hash方法实现：

 5.4put方法的核心流程：

1.哈希表的基本概念

根据关键码（key,value）而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。

2.什么是哈希冲突，以及哈希冲突的解决办法？（常考，阅读源码）

2.1闭散列

闭散列最大的问题在于 ：

若整个哈希表冲突比较严重，此时查找元素的过程就相当于遍历数组，查找效率退化为O（n）。

2.2开散列，当发生哈希冲突时，就让冲突位置变为链表。（既简单又实用）

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

2.3开散列和闭散列在元素查找时的对比：

问题：

 平均查找长度=这6个元素在哈希表中查找的总次数/6；

线性探测方法就是闭散列

 开散列方案下的平均查找次数：

 如果在开散列的方案下某个下标对应的冲突非常严重，单个链表的长度过长。

解决办法：

c++思路：

a.针对整个哈希表进行扩容，假设以前%7（数组长度为7），扩容为原数组的一倍，现在%14（数组长度变为14），就可大大降低冲突的概率，减少链表长度。

java思路：

b.单个链表的长度过长，查询效率就会变为链表的遍历O(n)，就针对这单链表进行转换处理，可以把单个链表再转为哈希表或者变为搜索树（JDK8中的HashMap就采用此方案，当某个链表的长度超过6且整个哈希表的元素个数大于64，把整个链表转为红黑树（RBTree））。

3.关于负载因子 

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

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

负载因子到底取多大，要根据当前你的系统需求做实验来的得知。

JDK HashMap的负载因子为0.75.

当元素个数/负载因子>=数组长度，此时我们就认为冲突比较严重，此时我们就认为冲突比较严重了，需要进行扩容或者转为红黑树(RbTree)

问题：

假设此时HashMap的哈希表长度为16。当元素个数超过12的时候，就会扩容

阿里内部，对于负载因子的建议为10，允许每个链表的平均长度为10以内，可以接受，元素个数达到160才会扩容。

负载因子就是在空间和时间上求平衡。

4.自己实现的哈希表（HashMap）

哈希表的扩容操作

  
        private void resize(){
            Node[] newData=new Node[data.length<<1];
            //新数组长度变为原来的一倍
            //现在的取模数变为新数组的长度
            this.M=newData.length;
            //遍历原数组，进行节点的搬移
            for (int i = 0; i < data.length; i++) {
                if(data[i]!=null) {
                    //对应的链表不为空
                    for(Node x=data[i];x!=null;){
                        //暂存一下后继节点的地址
                        Node next=x.next;
                        int newIndex=hash(x.key);
                        //新数组的头插
                        x.next=newData[newIndex];
                        //newData[newIndex]指向x对应的节点
                        newData[newIndex]=x;
                        //继续进行下一个节点的搬移操作
                        x=next;
                    }
                }else{
                    //当前数组i对应的索引下没有节点
                    continue;
                }
            }
            data=newData;
        }

5. JDK中Set和Map中常见的子类（面试必考常考）

5.1.Set和Map集合有啥关系？（源码）

其实Set集合下的子类就是Map集合下的子类

HashSet就是HashMap

TreeSet就是TreeMap

 

 5.2JDK的HashMap的源码讲解？大概的结构以及重点方法（源码阅读）

JDK7之前的HashMap就是基于开散列的散列表实现

JDK8之后引入了红黑树，目的是：当某个链表的长度过长时，元素的查询退化为链表的遍历，O(1)=>O(N),保证当某个链表节点过长时，树化，元素个数再多查询效率起码也是O(logN);

 JDK8:数组+链表（红黑树）

5.3hash方法实现：

高低16位都参与运算保证得到的值比较均匀。 

 俩个的计算结果一样，但是（n-1）%hash速度快 

 5.4put方法的核心流程：