Hash表的基本原理及其应用

矫情吗；* 2022-12-03 05:10 145阅读 0赞

内容：Hash表的基本原理及概念，常见的Hash函数及处理冲突的方法，Hash表的应用场景

### 文章目录 ###

*  Hash表是什么？
 *  Hash表的基本原理
 *  为什么Hash表无序，且不可重复
 *  常见的Hash函数
 *   *  1. 直接定址法
     *  2. 除留余数法
     *  3. 数字分析法
     *  4. 平方取中法
     *  5.Java8中的Hash函数
 *  常见的处理冲突的方法
 *   *  1. 开放定址法
     *   *  1.1 线性探测法
         *  1.2 平方探测法
         *  1.3 再散列法
         *  1.4 伪随机法
     *  2.拉链法
 *  用上述解释实际问题
 *   *  1. 为什么HashSet感觉是有序的
     *  2. Hash表优化程序性能
     *  3. Redis中的Hash应用

# Hash表是什么？ #

Hash表也叫散列表，就是一组数据集合，像List一样，就是存储一组数据，但是它有自己独特的方式。比如在Java中，HashSet与ArrayList一样，都是Collection集合的子类。

# Hash表的基本原理 #

假设现在有一组数据

61，12，46，13，17，28，19，70

如果我们想找里面是否包含28的话，可以将其放入ArrayList中，然后从第一个开始遍历，判断每一项是否与28相等。

那有没有什么方法，不用遍历，瞬间就可以知道这个集合中是否包含28呢。使用Hash表可以解决这个问题。

假设有一个Mod，它的作用是取余

Mod(x) = x % 10

我们初始化一个大小为10数组arr，初始值都为0

此时，我们对于上面的数字，先进行取余操作，然后根据余数，将其放入对应数组下标中。如：

Mod(61) = 61%10 = 1

所以应该放在61放在arr\[1\]中。将上述所有数据放入数组中，则如下图所示

此时，如果要查询28是否在这个集合中，则只需要先对28取余，得到8，然后判断arr\[8\]是否等于28即可。这样就是就是实现了快速查找。时间复杂度仅为O(1)。

上述描述中，Mod函数被称为 **Hash函数**，也叫散列函数

假设现在又来了一个数字，为38，取余后，也得8，但是此时arr\[8\]已经被占用了。那么这种现象就称为**冲突**。

Hash表要解决的最大的两个问题就是：

1.  如何选择Hash函数，原则是：尽可能等概率，均匀分布，减少冲突
2.  如何解决冲突

# 为什么Hash表无序，且不可重复 #

为什么无序：  
对于无序，通过上面的基本原理，应该已经可以理解了。对于数据存放在数组中的什么位置，并不是按照先后顺序来得。而是由Hash函数决定的，所以取不同的Hash函数，最终数据就会有不同的顺序。对于复杂的Hash函数，用户也很难预估最终的的顺序，而且没必要

为什么不可重复：

上述例子中，Hash表中存储的是数字，但实际应用中，通常存入Hash表的数据比较复杂，比如存入Hash表的是学生信息，在计算Hash值时，不会对整个学生信息进行Hash，而是选用学生信息的关键字，求该关键字的Hash值。在Java中，一般使用hashcode作为关键字。这样的话，两条记录的关键字一定不同，若相同，则会覆盖。假设若不覆盖，而是都存下来，这样在查找的时候，就不知道该返回哪个了。

# 常见的Hash函数 #

## 1. 直接定址法 ##

直接取关键字作为Hash值，或进行线性变换后的值作为Hash值

H(key) = key  或  H(Key) = a × key + b

这种方法实现简单，不会产生冲突。但是会造成空间的极大浪费。

## 2. 除留余数法 ##

假定表长为m，取一个不大于m，且接近m的质数p，然后对p求余。

H(key) = key % p

## 3. 数字分析法 ##

分析要被散列的集合，取相对随机的部分作为散列结果。如，要散列的数据的关键字为身份证号：

412314199607207598
    // 6位地区+8位生日+4位随机数

## 4. 平方取中法 ##

将关键字平方后，取中间几位作为散列地址。具体取多少，视情况而定。这样的好处是，散列地址与关键字每位都有关系，所以分布相对比较均匀。

## 5.Java8中的Hash函数 ##

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

# 常见的处理冲突的方法 #

## 1. 开放定址法 ##

计算hash地址后，发现该地址已经被占用了，那么就找其他的，不属于它的位置，然后放进去。比如：hash函数为对8取余。那 hash(1) =1 和hash(9) = 1，假设先来后到，1先来，那么9就冲突了，那么9就可以放在其他位置，比如放在2位置。

对于放在哪个位置，又可以有下面几种方法：

### 1.1 线性探测法 ###

就是依次往后探测，直到找到一个可以存放的位置。比如，hash(9)=1, 但是1位置已经被占了，那就看看2有没有，如果2也被占了，那就看3，依次类推。

缺点是会出现大量元素在相邻的散列地址上“聚集”，造成查找效率低下

### 1.2 平方探测法 ###

探测的顺序为

0 2 , 1 2 , − 1 2 , 2 2 , − 2 2 ， ⋯ 0^2, 1^2,-1^2,2^2,-2^2，\\cdots 02,12,−12,22,−22，⋯

假设数组长度为20，目前10位置冲突了，那么往后找的时候，分别找 11,9,14,6，依次类推。

优点为可以避免堆积，缺点为不能探测Hash表上的所有位置

### 1.3 再散列法 ###

用另一个Hash函数求出探测时的增量

### 1.4 伪随机法 ###

增量使用随机数

## 2.拉链法 ##

如果Hash地址一样，那么就依次往后排，按先来后到的方式。就像这个样子。可以使用数组，也可以使用链表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]  
Jdk1.7中采用的就是拉链法

# 用上述解释实际问题 #

## 1. 为什么HashSet感觉是有序的 ##

https://blog.csdn.net/zhaohongfei\_358/article/details/108639236

## 2. Hash表优化程序性能 ##

假设目前有一个业务，需要两层或更多层for循环，在最里层需要对某个集合进行contains操作，判断是否包含。

private static void contains(Collection e, Object value) {
        int cycleNumber = 1000;
        // 双层for循环查找value值
        for (int j = 0; j < cycleNumber; j++) {
            for (int i = 0; i < cycleNumber; i++) {
                e.contains(value);
            }
        }
    }

这个时候，若传过来的Collection是HashSet或ArrayList，则执行效率会大不相同。

当Collection数据为1w时，两层for循环(1000\*1000)，所消耗的时间。若数据更大，则消耗时间则是指数级增长。

HashSet查找所耗费的时间：15ms
    ArrayrList查找所耗费的时间：11943ms

## 3. Redis中的Hash应用 ##

都说Redis快，一问为什么快。基本上都会回答，Redis是基于内存的等等。但这些都是次要的。但Redis快的根本原因是因为它的数据存储方式是Hash表。

Redis有16383个Hash槽（Hash地址）。当进行get操作时，Redis会首先对Key进行Hash，求出这个Key是存放在哪个槽中的。然后直接到那个槽中去取。这样，get操作的时间复杂度就是O(1)。所以可以做到对一个key的瞬间存取。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/50c4926da6ee4a1d9f2ece6dd68cdd99.png