14-算法打卡-哈希表-基本概念-第十四天

1 基本概念

1.1 哈希表

百度百科解释：

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

简单来说就是数组就是一张哈希表，哈希表的关键码其实就是索引下标，关键值其实就是关键码对应的数组元素。

哈希表的作用：快速判断某个元素是否出现在集合中。
比如我们要查询班级里面是否有叫"张三"名字的同学，如果用传统的链表需要一个节点一个节点的查找时间复杂度是O(n)，但是如果使用哈希表的话时间复杂度是O(1)。
        首先我们需要把班级里的所有学生名称都映射(hash function哈希函数)到哈希表中，在查询的时候可以直接通过索引直接查询，直接判断出是否在班级里面。

1.2 哈希函数

百度百科解释：

哈希函数指将哈希表中元素的关键键值映射为元素存储位置的函数。 

一般的线性表记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。 理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

学生名称通过哈希函数找到对应的索引下标，将数据存放到数组中。
hashcode可以把名字转化为数值；数值可能大于tableSize；所以数值与tableSize取模，保证值落在数组范围内[0, tableSize-1]。

当学生人数大于哈希表数组长度的时候，就会导致多个学生对应一个数组下标，这种场景就称之为哈希碰撞，这种问题有几种常见的处理方案。

1.3 哈希冲突(碰撞)

张三、李四都落在索引下标为2的地方，这个时候就发生了哈希冲突

1.3.1 哈希冲突-链表法

刚刚张三和李四在索引2的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到张三和李四。

数据规模(数组大小)是tableSize， 索引范围[0, tableSize-1]
链表法就是要设置适当的哈希表大小，这样既不会因为数组空值浪费，也不会因为冲突导致链表长度太长而在查找上浪费太多时间。

1.3.2 哈希冲突-线性探索

使用线性探索法，一定要保证tableSize(哈希表长度)的长度大于dataSize(数据个数)，因为我们需要依赖哈希表中的空位来处理哈希冲突的问题，例如冲突的位置，放了张三，那么就向下寻找下一个空位放置李四的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放冲突的数据。

2 总结

在Java中使用hash实现的常见的数据结构HashSet、HashMap、HashTable；当我们遇到了要快速判断一个元素是否出现在集合里的时候，就要考虑哈希法。