聽說讀寫

概述

哈希表是非常常用的一種數(shù)據(jù)結(jié)構(gòu)和算法

其o(1)的查詢時間復(fù)雜度讓它可以傲視大部分其他算法

這里是一些常見的數(shù)據(jù)結(jié)構(gòu)的查詢復(fù)雜度

冒泡o(n)  

二分法o(logn)   [已經(jīng)排序的數(shù)據(jù)]

數(shù)組o(1)

基本原理

哈希表的主要原理就是hash值的計算

hash vlaue =f(key)

其中f() 可以視為o(1)復(fù)雜度   (通過 映射hashvalue 和內(nèi)存地址,就可以在o(1)時間內(nèi)完成查詢)

當(dāng)然 hash函數(shù)要保證hash值的不重復(fù), (為了性能,還要考慮分布的連續(xù)性等)

具體Hash函數(shù)是怎么實現(xiàn)的之后再介紹,

總體來說數(shù)組和Hash都可以達(dá)到o(1)的復(fù)雜度

相比Hash來說, 在數(shù)據(jù)量很大的情況下,數(shù)組需要消耗大量的內(nèi)存空間

應(yīng)用場景一

由于Hash值可以保證不重復(fù)

考慮下面一個場景 select * from  user where username='Mark'

由于username 是一個255字節(jié)的字符串,這樣的查詢明顯是非常緩慢的

考慮給UserName計算一個hash值, 那么就可以把查詢替換成   select * from user where hashvalue=12356

這樣查詢就在一個4字節(jié)的整形字段中進(jìn)行了 (當(dāng)然 你也可以設(shè)計為8字節(jié)或者別的, 取決于你用的hash算法)