devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】哈希表（6000字超详细）

作者：很楠不爱3 | 2024-04-11 13:18:13

赞

踩

哈希表

  欢迎来到南方有乔木的博客！！！

博主主页：点击点击！戳一戳！！

博主名:南方有乔木呀

博主简介：

一名在校大学生，正在努力学习Java语言编程。穷且意坚，不坠青云之志，希望能在编程的世界里找到属于自己的光。

跪谢帅气or美丽的朋友们能够帮我点赞! 请对文中内容请多多指教！！！

40b20882f0e44752b5a0b3f4765d6a1b.gif

目录

一.什么哈希表

二.什么是哈希冲突

三.如何减少哈希冲突

四.处理冲突的方法

五.负载因子

六.HashCode转为合法下标

七.哈希表的实现

1.成员变量

 2.成员方法

 （2）.get()方法

（3）.remove()方法

 八.实现哈希表全代码

一.什么是哈希表

哈希表概念：

哈希表是构造出来的一种可以快速查找的存储结构。

哈希存储的基本思想是以关键字为自变量，通过一定的函数关系（称为散列函数或者哈希函数），计算出对应的函数值，以这个值作为数据元素的地址，将该数据元素存到相应的地址单元中去。

查找时，再根据关键字采用计算哈希值的方式计算出相应的哈希地址，再到相应的存储单元去取需要的元素即可。

哈希表示意图：

哈希表的优势：

在顺序结构和平衡树中，元素关键码与它的存储位置之间没有对应映射关系，在查找时需要多次比较，而哈希表可以通过哈希函数建立元素关键码与存储位置之间的对应关系，查找时经过哈希函数的计算，可以算出元素对应的存储位置，直接到存储位置取出要查找的元素，不需要像顺序结构或者平衡树那样多次比较。

插入元素：

根据元素关键码，以哈希函数计算出元素的存储位置，将元素存放到该位置。

搜索元素：

根据元素的关键码计算存储位置，按计算出来的位置去查找，如果该位置中有对应的元素，查找成功

二.什么是哈希冲突

哈希冲突：

对于两个元素，e1!=e2,但Hash(e1)=Hash(e2),就会产生哈希冲突，简单点说，就是两个不同的元素经过哈希函数的计算，计算除了相同的存储地址，这样的情况成为哈希冲突

为何要避免哈希冲突：

哈希表需要尽量将元素均匀的放入到每个存储位置中去，但是如果两个元素的关键码值相等，那么就会放到同一个元素中，如果这种情况很多，就会出现一个存储位置出现很多元素的情况。这样不利于查找。

如何避免哈希冲突：

理论上如果哈希桶的数量多余要存储的位置，那么哈希冲突是可以避免的，但是实际中，我们认为要存储的元素是很多的，无穷的，哈希桶的数量是有限的，创建一个哈希桶也是需要耗费资源的，因此，实际中哈希冲突是不可避免的，因此，可以设计一些方法尽可能减少哈希冲突。

三.如何减少哈希冲突

设计良好的哈希函数可以减少或者避免哈希冲突

下面只介绍两种常用哈希函数设计的方法：

1.直接地址法

取关键字的某个线性函数值作为哈希地址，

比如：

H(key)=a*key+b  （a,b）都是常数

优点：直接地址法优点是哈希函数简单，不同的关键字不会产生冲突，，但是关键字集合往往是比哈希地址的结合大，因此，该方法会需要很多哈希桶，而且关键字集合往往离散，所有产生的哈希表会造成空间的巨大浪费，实际中不适用。

2.除留余数法

概念：

以一个略小于哈希地址集合个数的质数p，让关键字的关键码取它的余数作为哈希地址：

H(key)=key%p,(p是质数，p<=m,m是集合地址个数)

四.处理冲突的方法

如果发生了哈希冲突，怎么处理呢？

有闭散列和开散列两个方法，闭散列也称开放地址法，开散列也称连地址法

简单介绍常用的两种方法：

1.开放地址法（闭散列）

概念：

当发生哈希冲突时，如果哈希表未被填满，说明哈希表中还有空位置，那么就把元素放到下一个空位置去。

寻找空位置的方法可以用线性探测法：

从冲突位置开始，依次向后查找，直到找到下一个空位置。

2.连地址法/哈希桶（开散列）

对关键码集合用哈希函数计算存储地址，把具有相同地址的关键码归到一个子集合，，每一个集合成为一个哈希桶，各个桶中的元素通过一个单链表连接，将链表的头结点存在哈希表中。哈希桶可以看将大集合中的搜索问题放到小集合中搜索。

五.负载因子

概念：

已经存在哈希表的元素数量/哈希桶数量（相除）

负载因子和冲突率是相互影响的，因此可以设定一个的负载因子阈值，负载因子超过阈值，就增加哈希桶，降低冲突率。

      由图中可以看到，负载因子的值增大，冲突率也随着增大，我们不能直接控制冲突率，可以通过影响负载因子来降低冲率，而控制负载因子，负载因子是哈希表的元素数量除哈希桶数量，我们认为哈希表要传入的数量是未知的，也可以看作无穷的，所以，通过不能降低减少哈希表元素的数量来降低负载因子的值，但我们可以通过增加哈希桶的值来降低负载因子的值，进而降低冲突率。

六.HashCode转为合法下标

在JDK的内部，要把HashCode转为合法下标必须有一个必要前提：

哈希桶的数量是2的n次方。（比如1，2，4，8，16）

取得合法下标：

z&(n-1)    n是哈希桶的数量 ，z是元素调用hashCode()后得到得关键码的值

最后会得到一个合法的下标y:

y=z&(n-1)   (原理是使用比特位的与操作，效率比较高) 

0<= y <n; n为哈希桶的数量，合法下标的区间是：[0,n-1],所以0<= y <n.

七.哈希表的实现

1.成员变量

由于哈希表一共需要两个成员变量，

1.结点型数组

2.元素个数

由于哈希桶是由链表实现的，因此需要结点类来构造链表，所以，需要可以在哈希表内部定义一个结点类。结点类有构造方法，哈希表也有构造方法，哈希表初始设置的哈希桶数量必须是2的n次方，我这里设置为16.

  1. public class MyHashMap {
  2.     
  3.     private static class Node{
  4.         private String key;
  5.         private long value;
  6.         Node next;//链表结点类需要next
  7.  
  8.         public Node(String key, long value) {
  9.             this.key = key;
  10.             this.value = value;
  11.         }
  12.         //重写Node的toString（）方法
  13.  
  14.         @Override
  15.         public String toString() {
  16.             return "Node{" +
  17.                     "key='" + key + '\'' +
  18.                     ", value=" + value +
  19.                     '}';
  20.         }
  21.     }
  22.     
  23.     private Node[]array;//结点类数组
  24.     private int size;//元素个数
  25.  
  26.     //哈希表构造方法
  27.     private Node[]array;//结点类数组
  28.     private int size;//元素个数
  29.  
  30.     public MyHashMap() {
  31.        this.array=new Node[16];//哈希桶的数量需要是2的n次方
  32.         int size=0;//初始元素数量为0
  33.     }
  34.  
  35. }

 2.成员方法

(1).put方法

要实现哈希表的put方法，实现的思路如下：

1.首先让插入元素key调用hashCode()方法，得到一个关键码,我记为z；在这里有一个必要得前提，key对象需要正确的重写hashCode（）方法

int z=key.hashCode();

2.将关键码经过比特与得到合法下标，我将合法下标记为index,在此处也有必要的前提，n是哈希桶的数量，且必须是2的幂次方

要把得到的关键码值转为合法的下标，这里介绍三种方法：

  •  a.除留余数法
  •  b.     z&（n-1）
  •  c. 将关键码的高16位比特位和低16位比特位做一次异或

这里我采用b方法

int index=z&(n-1);

3. 得到合法下标以后找到对应的哈希桶，哈希桶的链表头结点就是array[index],然后开始遍历链表，如果链表中能已经存在的key,则更新value即可，如果没有存在，则插入key-value。

a. 在寻找key是否存在于链表中的时候，需要比较对象的相等性，此时需要key调用equals（）方法与当前链表的结点进行比较，对象调用equals（）方法有时需要正确的重写equals（）方法，我这里的key是String类型，直接调用即可。

key.equals(cur.key) //要插入的key与当前链表的key比较

b .插入时理论上采用头插或者尾插都可以，我这里采用头插，如果链表中原来没有对应元素，头插完成以后元素个数需要加一（size++）。

c. 插入后size++,元素个数增多，我们需要考虑降低冲突率，需要通过控制负载因子来降低冲突率。

负载因子： 哈希表中的元素个数/哈希桶的数量 

要控制负载因子，元素个数是不能控制减少的，因此，当冲突率过高时我们可以通过增加哈希桶的数量来降低负载因子的值，那么冲突率也会降低。

  1.  
  2.         //找到要放入的链表的头结点
  3.         Node head = array[index];
  4.         //开始在链表上查找
  5.         Node cur = head;
  6.  
  7.         while (cur != null) {
  8.             if (key.equals(cur.key)) {
  9.                 //如果找到已经存在则更新value
  10.                 long oldValue = cur.value;
  11.                 cur.value = value;
  12.                 return oldValue;
  13.             }
  14.             cur = cur.next;
  15.         }
  16.         //如果没有存在则插入 头插尾插都可 这里使用头插
  17.         Node node = new Node(key, value);
  18.         node.next = head;
  19.         //插入后记得更新哈希桶第一个结点
  20.         array[index] = node;
  21.         //找不到插入以后元素个数加一
  22.         size++;
  23.   //如果负载因子的值超过四分之三，那么扩容
  24.         if((1.0*size/array.length)>=0.75) {
  25.             grow();//扩容方法
  26.         }
  27.         return null;

 要控制负载因子，我们可以写一个扩容方法，当负载因子的值超过0.75（一般0.75是常用的控制阈值）时，我们就使哈希表扩容，在扩容时，依旧使哈希桶的数量为2的n次方，我们将原数组扩大两倍容量。

扩容思路：

  • a.首先将原数组扩大两倍容量;
  • b.遍历哈希表的每一个元素，每个元素的合法下标是与哈希桶数量有关的，哈希桶数量改变，每个元素都需要重新计算下标 ;
  • c.重新计算下标之后将所有元素重新放到新的哈希表中;
  1.   //扩容操作
  2.     public void grow(){
  3.         int newLength=array.length*2;//扩容的哈希桶数也需要是2的n次方
  4.         Node[]newArray=new Node[newLength];
  5.  
  6.         //每个元素的合法下标是与哈希桶数量有关的，哈希桶数量改变，每个元素都需要重新计算下标
  7.         //双层循环遍历链表中的每一个元素
  8.         for(int i=0;i<array.length;i++){
  9.  
  10.             Node head=array[i];
  11.             Node cur=head;
  12.             while(cur!=null){
  13.                 Node next=cur.next;//cur.next头插时需要修改，提前保存
  14.                 //重新算出当前结点的元素下标index
  15.                 int z = cur.key.hashCode();//到关键码
  16.  
  17.                 int index = z & (array.length - 1);//得到合法下标
  18.  
  19.                 //将原链表中的元素放入新链表
  20.                 //头插
  21.                 cur.next=newArray[index];
  22.                 newArray[index]=cur;
  23.                 cur=next;
  24.             }
  25.         }
  26.         this.array=newArray;
  27.     }

 （2）.get()方法

描述：哈希表的get()方法，查找key-value,，传入key,在哈希表中查找是否有key，找到key，返回对应的value，没找到返回null.

步骤：

  • a.让key对象调用hashCode（)方法，得到对应的关键码，将关键码转为合法下标index；
  • b.得到合法下标index后找到key所在哈希桶的头结点，遍历该链表,查找是否有key；
  • c.找到key，返回对应的value,找不到，返回空。

  1.  //哈希表 get()方法 查找key-value 找到key返回value
  2.     public Long get(String key){
  3.    //让key对象调用hashCode（)方法，得到对应的关键码，将关键码转为合法下标
  4.         int z=key.hashCode();
  5.         int index=z&(array.length-1);
  6. //得到合法下标index后找到key所在哈希桶的头结点，遍历该链表,查找是否有key
  7.         Node cur=array[index];
  8. //找到key，返回对应的value,找不到，返回空
  9.         for( ;cur!=null;cur=cur.next){
  10.             if(key.equals(cur.key)){
  11.                 return cur.value;
  12.             }
  13.         }
  14.         return null;
  15.     }

（3）.remove()方法

描述：哈希表 remove方法 ,移除 key-value  。输入key,查找哈希表中是否有key,如果有，移除key-value结点，如果没有，直接返回null

步骤：

  • a.让key对象调用hashCode（)方法，得到对应的关键码，将关键码转为合法下标index；
  • b.得到合法下标index后找到key所在哈希桶的头结点，遍历该链表,查找是否有key；
  • c.找到key所在的结点以后，删除该结点，删除时分两种情况讨论：

    1.若要删除的是头结点，删除时直接更新头结点，元素个数减一，size--。在删除之前记得先保存结点的value，以便删除后返回。

    2.若删除的不是头结点，则让前驱结点指向当前结点的后继结点即可。在删除之前记得先保存结点的value，以便删除后返回。

因此我们需要在开始定义一个指向前驱结点的指针prev,让它始终保持在当前结点cur的前面，需要删除的结点不是头结点时直接让前驱结点指向当前结点cur的后继结点即可，最后删除后元素个数减一，size--。

  1.   //哈希表 remove方法 移除 key-value  找到移除后返回对应的value 找不到返回空
  2.     public Long remove(String key){
  3.          int z=key.hashCode();
  4.          int index=z&(array.length-1);
  5.  
  6.          Node cur=array[index];
  7.          Node prev=null;
  8.          for(;cur!=null;prev=cur,cur=cur.next){
  9.              if(key.equals(cur.key)){
  10.                  //移除结点要考虑移除的是否是头结点
  11.                  //移除之前要先保存当前结点的value
  12.                  long oldValue=cur.value;
  13.                  //要移除的是头结点
  14.                  if(prev==null ){
  15.                      array[index]=cur.next;
  16.                      size--;
  17.                      return oldValue;
  18.                  }else{
  19.                      //要移除的不是头结点
  20.                      prev=cur.next;
  21.                      size--;
  22.                      return oldValue;
  23.                  }
  24.              }
  25.          }
  26.          //全部遍历如果还是没找到说明哈希表没有需要移除的元素，直接返回空
  27.          return null;

 八.实现哈希表全代码

  1. public class MyHashMap {
  2.  
  3.     private static class Node{
  4.         
  5.         private String key;
  6.         private Long value;
  7.         Node next;
  8.         public Node(String key, long value) {
  9.             this.key = key;
  10.             this.value = value;
  11.         }
  12.         @Override
  13.         public String toString() {
  14.             return "Node{" +
  15.                     "key='" + key + '\'' +
  16.                     ", value=" + value +
  17.                     '}';
  18.         }
  19.     }
  20.  
  21.     private Node[]array;//结点类数组
  22.     private int size;//元素个数
  23.  
  24.     public MyHashMap() {
  25.        this.array=new Node[8];//哈希桶的数量需要是2的n次方
  26.         int size=0;//初始元素数量为0
  27.     }
  28.  
  29.         public Long put(String key, long value) {
  30.         //先取到key的合法下标
  31.             int z = key.hashCode();//到关键码
  32.  
  33.             int index = z & (array.length - 1);//得到合法下标
  34.  
  35.         //找到要放入的链表的头结点
  36.         Node head = array[index];
  37.         //开始在链表上查找
  38.         Node cur = head;
  39.  
  40.         while (cur != null) {
  41.             if (key.equals(cur.key)) {
  42.                 //如果找到已经存在则更新value
  43.                 long oldValue = cur.value;
  44.  
  45.                 cur.value = value;
  46.                 return oldValue;
  47.             }
  48.             cur = cur.next;
  49.         }
  50.         //如果没有存在则插入 头插尾插都可 这里使用头插
  51.         Node node = new Node(key, value);
  52.         node.next = head;
  53.         //插入后记得更新哈希桶第一个结点
  54.         array[index] = node;
  55.         //找不到插入以后元素个数加一
  56.         size++;
  57.         //如果负载因子的值超过四分之三，那么扩容
  58.         if((1.0*size/array.length)>=0.75) {
  59.             grow();
  60.         }
  61.         return null;
  62.     }
  63.     //扩容操作
  64.     public void grow(){
  65.         int newLength=array.length*2;//扩容的哈希数也需要是2的n次方
  66.         Node[]newArray=new Node[newLength];
  67.  
  68.         //每个元素的合法下标是与哈希桶数量有关的，哈希桶数量改变，每个元素都需要重新计算下标
  69.         //双层循环遍历链表中的每一个元素
  70.         for(int i=0;i<array.length;i++){
  71.  
  72.             Node head=array[i];
  73.             Node cur=head;
  74.             while(cur!=null){
  75.                 Node next=cur.next;//cur.next头插时需要修改，提前保存
  76.                 //重新算出当前结点的元素下标index
  77.                 int z = cur.key.hashCode();//到关键码
  78.  
  79.                 int index = z & (array.length - 1);//得到合法下标
  80.  
  81.                 //将原链表中的元素放入新链表
  82.                 //头插
  83.                 cur.next=newArray[index];
  84.                 newArray[index]=cur;
  85.                 cur=next;
  86.             }
  87.         }
  88.         this.array=newArray;
  89.     }
  90.  
  91.     //哈希表 get()方法 查找key-value 找到key返回value
  92.     public Long get(String key){
  93.  
  94.         int z=key.hashCode();
  95.  
  96.         int index=z&(array.length-1);
  97.         Node cur=array[index];
  98.         for( ;cur!=null;cur=cur.next){
  99.             if(key.equals(cur.key)){
  100.                 return cur.value;
  101.             }
  102.         }
  103.         return null;
  104.     }
  105.  
  106.     //哈希表 remove方法 移除 key-value  找到移除后返回对应的value 找不到返回空
  107.     public Long remove(String key){
  108.  
  109.         int z = key.hashCode();//到关键码
  110.  
  111.         int index = z & (array.length - 1);//得到合法下标
  112.  
  113.         Node cur=array[index];
  114.          Node prev=null;
  115.          for(;cur!=null;prev=cur,cur=cur.next){
  116.              if(key.equals(cur.key)){
  117.                  //移除结点要考虑移除的是否是头结点
  118.                  //移除之前要先保存当前结点的value
  119.                  long oldValue=cur.value;
  120.                  //要移除的是头结点
  121.                  if(prev==null ){
  122.                      array[index]=cur.next;
  123.                      size--;
  124.                      return oldValue;
  125.                  }else{
  126.                      //要移除的不是头结点
  127.                      prev=cur.next;
  128.                      size--;
  129.                      return oldValue;
  130.                  }
  131.              }
  132.          }
  133.          //全部遍历如果还是没找到说明哈希表没有需要移除的元素，直接返回空
  134.          return null;
  135.     }
  136.  
  137. }
  138.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/405196
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号