MySQL 中的HASH详解

目录

HASH表结构
HASH冲突
办理方法
链地点法
开放地点法
创建公共溢出区

---

MySQL中的哈希索引（Hash Index）是一种特殊的数据库索引类型，它利用哈希表（Hash Table）的数据结构来存储索引项。哈希表通过哈希函数（Hash Function）将索引列的值转化为一个固定长度的哈希码（Hash Code），然后用这个哈希码作为索引项在表中定位数据纪录的位置。这种方式使得对于等值查询（例如 WHERE column = value）可以大概非常快速，抱负环境下接近O(1)的时间复杂度。

HASH表结构

哈希表的底子结构设计告急包罗以下几个关键构成部门：

• 哈希函数（Hash Function）： 哈希函数是哈希表的核心，它的作用是将输入的键转换为一个确定的索引值，这个索引值用于决定数据在表中的存储位置。抱负的哈希函数应能均匀分布差别的键值，淘汰冲突，并且计算速度快。常用的哈希函数有直接定址法、除留余数法、平方取中法、折叠法、随机数法等。
  
• 数组（Bucket Array）： 哈希表通常由一个较大的数组构成，数组的每个元素称为一个“桶”（Bucket）。哈希函数计算出的索引值就是数组的下标，指向存放相应键值对的位置。
  
• 冲突办理策略（Collision Resolution Strategy）： 当两个或多个差别的键经过哈希函数计算后得到相同的索引值，就会发生冲突。办理冲突的方法有多种：
  
  
  
  • 开放寻址法：在数组中探求下一个可用的位置（例如线性探测、二次探测、双重散列等）。
    
  • 链地点法：在每个桶内利用链表或别的动态数据结构存储具有相同哈希值的元素。
    
  • 再哈希法：利用第二个哈希函数来探求下一个槽位。
    
  • 创建公共溢出区：为全部冲突的元素分配一个公共的地区。
    
  
  
• 装载因子（Load Factor）： 装载因子定义为哈希表中已填入的元素数目与表总容量的比例。一个合适的装载因子可以均衡查找效率与空间利用率，过高会导致冲突增多，查找效率降落。
  
• 动态调解（Resizing）： 为了维持高效的查找性能，当装载因子到达某个预设阈值时，哈希表会自动调解大小，通常是扩大数组长度并重新哈希全部元素。这一过程称为重哈希（Rehashing）。
  

   装载因子（Load Factor）
  装载因子是衡量哈希表中元素填充程度的一个告急指标，计算公式为：[ \text{装载因子} = \frac{\text{哈希表中现实存储的元素数目}}{\text{哈希表的容量}} ]，大概更简便地表示为 ( \alpha = \frac{n}{m} )，其中 ( n ) 是哈希表中元素的数目，( m ) 是哈希表的容量（即桶的数目）。
  装载因子反映了哈希表的饱和度。较小的装载因子意味着哈希表有更多的空闲空间，可以淘汰哈希冲突，提高查找效率，但同时也会浪费更多的存储空间；相反，较大的装载因子虽然提高了空间利用率，但会增长冲突概率，低沉操作效率，特殊是在冲突较多时，查找、插入和删除操作大概退化为链表遍历或线性查找，时间复杂度大概变为O(n)。
  动态调解
  为了均衡存储效率和查询效率，哈希表通常会采用动态调解机制，即根据装载因子的变革自动调解哈希表的大小。告急涉及以下两个方面：
  

• 扩容（Resizing Up）： 当装载因子到达或超过一个预设的阈值（好比0.7或0.8），表明哈希表已较为拥挤，冲突增多，性能大概开始降落。此时，哈希表会自动进行扩容操作。扩容通常涉及以下步调：
  
  
  
  • 新建一个更大的数组，其容量通常是原容量的两倍或更高倍数。
    
  • 将原有数组中的全部元素通过哈希函数重新映射到新数组中。因为容量变大，之前冲突的元素大概在新数组中找到不冲突的位置。
    
  • 更新哈希表的容量和装载因子阈值。
    
  
  
• 缩容（Resizing Down）： 少数环境下，如果哈希表中的元素数目明显淘汰，为了节省空间，也可以思量缩容。缩容的决定较为复杂，因为它涉及到效率和空间利用的权衡，而且频繁缩容大概导致不须要的性能开销。因此，现实应用中，缩容的触发条件往往设置得比较保守，大概根本不实行自动缩容，仅在须要时手动干预。
  

  动态调解机制确保了哈希表在差别负载下的高效运行，是实现高效哈希表的关键技术之一。通过适时调解哈希表的大小，可以在保证查询效率的同时，合理利用内存资源。
  HASH冲突

哈希冲突（Hash Collision或Hash Collision），也称为哈希碰撞，是指在利用哈希函数将数据（如关键字key）映射到哈希表或哈希结构中的索引位置时，两个或多个差别的数据经过哈希处理处罚后得到相同的哈希值，从而导致它们被映射到同一个索引位置的现象。由于哈希函数的输出范围通常是有限的，而输入数据的范围大概是无限的，因此在现实应用中，特殊是在较大的数据会合，哈希冲突几乎是不可避免的。
例：如下图我们依次将这些数对 12取余，将这些数添加到对应的关键字里，但是当我们添加16时，我们发现，16和4在散列表的位置冲突了，我们必须给16安排到别的位置去。

办理方法

办理哈希冲突的常用方法包罗：
链地点法

链地点法（Separate Chaining）：每个哈希表的槽位（bucket）存储一个链表，全部映射到该槽位的元素都放入这个链表中。这样，纵然多个键值对映射到同一索引，也可以通过遍历链表来找到对应的值。
   例如：
  

  开放地点法

线性探测（Linear Probing）: 发生冲突时，从发生冲突的桶开始，序次检查下一个桶，直到找到一个空桶为止。如果到达表末端还没找到空位，则大概须要循环回表头继续探测（称为“闭合”或“循环”探测）。这种方法简朴，但大概导致数据在表中的聚集，影响查找效率。
   例如：
  

  二次探测（Quadratic Probing）: 探测序列是按照1^2, -1^2, 2^2, -2^2, ...这样的平方数隔断进行，即每次探测步长逐步增长。这种探测方式试图淘汰聚集现象，提高查找效率。
   例如：
  

  双重散列（Double Hashing）: 利用两个差别的哈希函数H1和H2，当H1(key)导致冲突时，利用H2(key)来决定步长，即每次探测的位置是H1(key) + i * H2(key)，其中i是递增的探查序列。这种方法可以更有效地分散冲突，淘汰聚集。
创建公共溢出区

当哈希表的全部槽都被填满时，可以将额外的元素放入一个单独的溢出区或链表中。这种方法简朴，但是查找效率较低，因为大概须要检查两个地区。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。