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

  哈希表用的是数组支持按照下标随机访问数据的特性，所以哈希表其实就是数组的一种扩展，由数组演化而来。可以说，没有数组，就没有哈希表。

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

哈希函数

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

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

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

哈希冲突

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

1，开放寻址法
核心思想：如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入。那么如何重新探测新的位置呢？

2，链表法