概述
哈希表是非常常用的一种数据结构和算法
其o(1)的查询时间复杂度让它可以傲视大部分其他算法
这里是一些常见的数据结构的查询复杂度
冒泡o(n)
二分法o(logn) [已经排序的数据]
数组o(1)
基本原理
哈希表的主要原理就是hash值的计算
hash vlaue =f(key)
其中f() 可以视为o(1)复杂度 (通过 映射hashvalue 和内存地址,就可以在o(1)时间内完成查询)
当然 hash函数要保证hash值的不重复, (为了性能,还要考虑分布的连续性等)
具体Hash函数是怎么实现的之后再介绍,
总体来说数组和Hash都可以达到o(1)的复杂度
相比Hash来说, 在数据量很大的情况下,数组需要消耗大量的内存空间
应用场景一
由于Hash值可以保证不重复
考虑下面一个场景 select * from user where username='Mark'
由于username 是一个255字节的字符串,这样的查询明显是非常缓慢的
考虑给UserName计算一个hash值, 那么就可以把查询替换成 select * from user where hashvalue=12356
这样查询就在一个4字节的整形字段中进行了 (当然 你也可以设计为8字节或者别的, 取决于你用的hash算法)