作者：学Java的冬瓜
博客主页：☀冬瓜的主页🌙
专栏：【Java 数据结构与算法】
分享：曾梦想仗剑走天涯，看一看世界的繁华。——许巍《曾经的你》
主要内容：哈希方法，哈希函数，哈希表，哈希冲突，负载因子，降低哈希冲突，解决哈希冲突。

一、什么是哈希表？

• 在顺序结构和平衡树中，想要查找一个元素，必须先经过多次比较，才能找到。但是在哈希表中不一样。
• 哈希表是一种数据结构，通过哈希函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系（即这个关键码通过哈希函数计算可以得到元素的存储位置，所以速度极快），这个存储结构就是哈希表。

二、哈希函数

• 为了避免哈希冲突，有两种哈希函数方法比较普遍。

1、直接定制法

• 取关键字的某个线性函数为散列地址：Hash(Key) = A*Key + B
• 优点：简单、均匀；缺点：需要事先知道关键字的分布情况
• 使用场景：适合查找比较小且连续的情况
• 面试题：【字符串中的第一个唯一字符】

2、除留取余法

• 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p (p <= m)，将关键码转换成哈希地址。

三、哈希冲突

1、什么是负载因子？

负载因子也可称为荷载因子。

负载因子 α = 哈希表中元素个数 / 哈希表的长度

哈希表的长度没有扩容之前是定长的，当哈希表中元素的个数增加时，负载因子 α 就会变大，那么越容易出现哈希冲突，所以我们应该严格控制负载因子的大小，在 Java 中，限制了负载因子最大为 0.75，当超过了这个值，就要进行扩容哈希表，重新哈希（重新将各个元素放在新的位置上）。

2、怎么降低哈希冲突？

<1> 使用合适的哈希函数
<2> 增加散列表的长度。当负载因子越来越大时，冲突率越来越高。如果想要降低冲突率，就是要降低负载因子，那就增加散列表的长度。

3、怎么解决哈希冲突？

闭散列

• 闭散列又称开放地址法

开放地址法具体操作有以下两种：

集合：{1, 7, 4, 5, 9}

线性探测

通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素；
如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

二次探测：

首先 H0 经过 key % m 得到，然后如果冲突，就再次计算，直到算出不冲突的值。

开散列（哈希桶 重点）

• 开散列又称链地址法，哈希桶。

集合：{1, 7, 4, 5, 9}
要插入：34, 44, 84

• 插入操作：JDK1.7 之前，采用头插法；JDK1.8 开始，使用尾插法。
• 哈希表使用：数组 + 链表的形式，当链表长度超过 8 且数组长度超过 64 时，链表会变成红黑树。
• 那么就出现一个问题，当链表长度超过 8 且数组长度超过 64，二者都满足时，链表才会变成红黑树。那有没有可能链表长度很长，但数组长度不超过 64 呢？
  没有可能！因为链表长度很长时，代表哈希冲突率很高了，那要降低哈希冲突，就需要降低负载因子（Java 的系统库限制了负载因子为 0.75），负载因子和数组长度成反比，那么就是得增大数组长度，这样当链表长度超过 8，数组长度超过 64 时，链表就变成了红黑树。这样就把数组长度和链表长度联系起来了。
• 哈希表查找时间复杂度：近似 log(1)
  当链表长度比较短时，近似 O(1)
  链表长度变长时，会通过加长数组来降低冲突率，从而使链表长度降低（数组长度增长后原来的链表会被打散），也近似 O(1)
  当

  

  作者：学Java的冬瓜
  博客主页：☀冬瓜的主页🌙
  专栏：【Java 数据结构与算法】
  分享：曾梦想仗剑走天涯，看一看世界的繁华。——许巍《曾经的你》
  主要内容：哈希方法，哈希函数，哈希表，哈希冲突，负载因子，降低哈希冲突，解决哈希冲突。

  

  文章目录

  • 一、什么是哈希表？
  • 二、哈希函数
  • • 1、直接定制法
    • 2、除留取余法
  • 三、哈希冲突
  • • 1、什么是负载因子？
    • 2、怎么降低哈希冲突？
    • 3、怎么解决哈希冲突？
    • • @ 闭散列
      • @ 开散列(哈希桶 重点)

  一、什么是哈希表？

  • 在顺序结构和平衡树中，想要查找一个元素，必须先经过多次比较，才能找到。但是在哈希表中不一样。
  • 哈希表是一种数据结构，通过哈希函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系（即这个关键码通过哈希函数计算可以得到元素的存储位置，所以速度极快)，这个存储结构就是哈希表。

  二、哈希函数

  • 为了避免哈希冲突，有两种哈希函数方法比较普遍。

  1、直接定制法

  • 取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
  • 优点：简单、均匀 ；缺点：需要事先知道关键字的分布情况
  • 使用场景：适合查找比较小且连续的情况
  • 面试题：【字符串中的第一个唯一字符】

  2、除留取余法

  • 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：
    Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。

  三、哈希冲突

  1、什么是负载因子？

  负载因子也可称为荷载因子。

  负载因子 α = 哈希表中元素个数 / 哈希表的长度
  

  哈希表的长度没有扩容之前是定长的，当哈希表中元素的个数增加时，负载因子α就会变大，那么越容易出现哈希冲突，所以我们应该严格控制负载因子的大小，在 Java 中，限制了负载因子最大为 0.75，当超过了这个值，就要进行扩容哈希表，重新哈希(重新将各个元素放在新的位置上)。

  2、怎么降低哈希冲突？

  <1> 使用合适的哈希函数
  <2> 增加散列表的长度。当负载因子越来越大时，冲突率越来越高。如果想要降低冲突率，就是要降低负载因子，那就增加散列表的长度。

  

  3、怎么解决哈希冲突？

  @ 闭散列

  • 闭散列又称开放地址法

  开放地址法具体操作有以下两种：

  集合：{1，7，4，5，9}
  

  线性探测

  通过哈希函数获取待插入元素在哈希表中的位置
  如果该位置中没有元素则直接插入新元素；
  如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。

  

  二次探测：

  首先H0经过key%m得到，然后如果冲突，就再次计算，直到算出不冲突的值。

  

  @ 开散列(哈希桶 重点)

  • 开散列又称链地址法，哈希桶。

  集合：{1，7，4，5，9}
  要插入：34，44，84
  

  

  • 插入操作：JDK1.7之前，采用头插法；JDK1.8开始，使用尾插法。
  • 哈希表使用：数组+链表的形式，当链表长度超过 8且数组长度超过 64时，链表会变成红黑树。
  • 那么就出现一个问题，当链表长度超过 8且数组长度超过 64，二者都满足时，链表才会变成红黑树。那有没有可能链表长度很长，但数组长度不超过64呢？
    没有可能！因为链表长度很长时，代表哈希冲突率很高了，那要降低哈希冲突，就需要降低负载因子(Java的系统库限制了负载因子为0.75)，负载因子和数组长度成反比，那么就是得增大数组长度，这样当链表长度超过8，数组长度超过64时，链表就变成了红黑树。这样就把数组长度和链表长度联系起来了。
  • 哈希表查找时间复杂度：近似log(1)
    当链表长度比较短时，近似O(1)
    链表长度变长时，会通过加长数组来降低冲突率，从而使链表长度降低(数组长度增长后原来的链表会被打散)，也近似O(1)
    当链表长度超过8，数组长度超过64时，复杂度为O(logn)。
    其实复杂度随着数组长度变化，链表长度的变化而变化。但是可以近似看成O(1)。

  汇率网