数据结构与算法系列--哈希表初识

电玩女神 2022-02-22 20:50 267阅读 0赞

哈希表用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，没有数组，就没有哈希表。  
  
那么，数组与哈希表有什么不同呢?它们都可以通过下标来随机访问，但数组的下标和数组的元素值是没有关系的（和地址有关），数组的本质 [https://blog.csdn.net/chegy218/article/details/89055074][https_blog.csdn.net_chegy218_article_details_89055074]  
而**哈希表用的就是数组支持下标随机访问的特性。通过把元素的键值映射为下标，然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时，用同样的哈希函数，将键值转化数组下标，从对应的数组下标的位置取数据。**  
所以，哈希表对比数组，其将表中元素通过哈希函数与下标建立联系，产生键，通过键来随机访问表中元素。有人说这不是多此一举吗，下标可以随机访问，还要键干嘛？这是因为，有时候需要根据元素值去查找元素是否存在等操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]

## 哈希函数 ##

比如学生学号，就是一个哈希的键。由学院+专业+班级+学号组成（哈希函数），学生就是哈希值。那么，如何构造哈希函数呢？有3点基本要求：

> 1，散列函数计算得到的散列值是一个非负整数；  
> 2，如果key1 = key2，那么hash(key1) == hash(key2)；  
> 3，如果key1 != key2，那么hash(key1) ! = hash(key2)。

对比上述学号的例子，理解上述3点要求。但学号机制只是简单的哈希函数，处理数据一般不会太大。为什么要考虑数据量呢，更多因素是哈希冲突问题。在真实的情况下，要想找到一个不同的key对应的散列值都不一样的散列函数，几乎是不可能的。即便像业界著名的MD5，SHA，CRC等哈希算法，也无法避免哈希冲突。而且，因为数组的存储空间有限，也会加大散列冲突的概率。比如：Java中的HashMap。

## 哈希冲突 ##

我们常用的哈希冲突有两种解决方法：开放寻址法和链表法

**1，开放寻址法**  
核心思想：如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那么如何重新探测新的位置呢？  
![在这里插入图片描述][20190407143521649.png]

**2，链表法**  
![在这里插入图片描述][20190407143543197.png]

[https_blog.csdn.net_chegy218_article_details_89055074]: https://blog.csdn.net/chegy218/article/details/89055074
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZWd5MjE4_size_16_color_FFFFFF_t_70]: /images/20220223/0c68f9793555464c9447fc77fd281312.png
[20190407143521649.png]: /images/20220223/fb81a88ce7534e66877a447b72211947.png
[20190407143543197.png]: /images/20220223/20199c9cdaeb4aa3bf96f4584498e81b.png