哈希索引原理讲解（浅谈查找---哈希查找）

哈希索引原理讲解（浅谈查找---哈希查找）二是二分查找:这个萌蠢的查找思想 是选择排序的基础 不过这里空白太小 我写不下 容我后面再说.也简单的介绍了两种查找的方法:一是遍历查找:也叫顺序查找 思路为 遍历整个列表，逐个进行记录的关键字与给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录。如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。

在上一篇综述中 我给出了排序是为了更快的查找这个观点.也介绍了查找的一些典型应用场景如:

1.判断一个给定值 是否在一个数组

2.mysql 的查询优化

3.再到给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，找出a、b文件共同的url.

也简单的介绍了两种查找的方法:

一是遍历查找:

也叫顺序查找 思路为 遍历整个列表，逐个进行记录的关键字与给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录。如果直到最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找失败。

这个萌蠢的查找思想 是选择排序的基础 不过这里空白太小 我写不下 容我后面再说.

二是二分查找:

也叫折半查找 思路为 在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到找到为止。

二分查找 要求查找的数列是有序的. 于是 又引入了一个问题 如何排序? ---- 不过同样的 这里空白太小 我写不下.

费马老爷子

还有其他的诸如 索引查找 二叉树查找 哈希查找等方法 这里我讲讲哈希查找 其他的查找方法 如果您有兴趣了解-----那等我有兴趣写就可以了.....

就你皮

哈希(hash) 翻译过来叫散列.定义一个函数 F = f(ꭓ) 对于不同的 ꭓ 得到不同的 f(ꭓ) [标:不完全一定 会有不同的ꭓ 得到相同的f(ꭓ)情况 术语叫哈希碰撞] 查找的时候 将要查找的key 也按照定义好的哈希函数转换 得到一个哈希值 然后用这个哈希值 直接去哈希表中取 取出则为找出key 取不出即为查找的key不存在.

来看看哈希思想的几个应用:

面试题一:

判断 8 是否存在数组[1 3 5 7 11 13 17]中.

普通青年

但是这种方式 每查找一次 都要整个的遍历一次.来看看下面的方法:

文艺青年

可以看到 只要 hash 表建立成功后 每次判断一个数是不是在数组中 只需要直接执行 arrHashObject[key] 就可以得到结果了.效率大大提高.

面试题二:

当 usertype=1 时 userTypeName 为 student

当 usertype=2 时 userTypeName 为 teacher

当 usertype=3 时 userTypeName 为 admin

请用代码描述.

普通青年

但是这种写法 当条件增多的情况 简直就是灾难.我们可以使用哈希的思想 写得文艺一点:

文艺青年

增加角色 只需配置这个哈希表 避免了繁琐的 if-else.

面试题三:

需要对存储大量的 URL 并需要根据URL 进行搜索查找.

普通青年: 使用 B-Tree来存储 URL 会有如下查询:

select id from url where url = 'http://www.mysql.com';

文艺青年: 删除原来 URL 上的索引 新增一个被索引的 url_crc列 使用 CRC32做哈希 就可以使用下面的方式查询:

select id from url where url = 'http://www.mysql.com' and url_crc = CRC32('http://www.mysql.com');

性能 biu 的一下就上去了 占的空间还不大.

还有在 APP 开发中 我们通常使用 token 来模拟 session 以判断是否用户登录. 大概思路是: 将 将 token 存入到 redis 中. 然后直接使用 Redis->get(token) 看值是否为空来判断是否登录...

有同学要问了 哈希查找这么好 那有缺点没有?