散列表
散列表是一種數(shù)據(jù)結(jié)構(gòu)。通過key value進(jìn)行存儲(chǔ)姜凄。你可以先看下上面百度百科的解釋，注意其中這幾個(gè)關(guān)鍵字散列函數(shù)趾访，沖突态秧。
這樣一個(gè)需求
假如你是水果的銷售人員，那么你肯定要知道每種水果的價(jià)格扼鞋，比如顧客來了說蘋果多少錢一斤申鱼，假如你有一個(gè)清單愤诱，也就是我們說的數(shù)組。
我們前面介紹了二分查找方法捐友，比如我們要查找一個(gè)數(shù)組中的元素淫半，需要的log2n。如果水果很多怎么辦匣砖，那么有的同學(xué)就說了科吭，哪有這么難，我可以記住這些水果猴鲫，確實(shí)我們也講過帶有緩存的函數(shù)对人，你可以記住那些你查找過的水果，如果不適用緩存函數(shù)那拂共，我們想像數(shù)組那樣牺弄，比如我要下標(biāo)為10的元素，我們就能立刻找到這個(gè)元素宜狐。所以我們要設(shè)法寫一個(gè)函數(shù)吧這些水果都映射到數(shù)組的下標(biāo)中势告，比如蘋果我就要存到0的地方，香蕉我要存到1的地方等等抚恒，那么我們?cè)谡姨O果的時(shí)候咱台，我們就要這個(gè)函數(shù)告訴我蘋果在數(shù)組的那個(gè)位置，我們就可以輕松的找到了蘋果的位置柑爸。
散列函數(shù)
我們通過散列函數(shù)將蘋果存放到數(shù)組下標(biāo)為七的地方吵护。大家肯定會(huì)說這個(gè)不就是字典嗎。我給一個(gè)key就得到一個(gè)value.對(duì)的字典就是散列表的一種實(shí)現(xiàn)表鳍。
用途
用于查找馅而，散列表是key -> value所以查找速度很快。
防止重復(fù)譬圣，由于一個(gè)key -> value所以是一一對(duì)應(yīng)關(guān)系
用于緩存瓮恭，一定輸入對(duì)應(yīng)一定輸出的函數(shù)，我們可以使用散列表進(jìn)行緩存厘熟。
沖突
對(duì)于編寫的散列函數(shù)來說屯蹦，我們希望能編寫出一個(gè)一一對(duì)應(yīng)的關(guān)系，但是這樣的函數(shù)太難了绳姨。于是就會(huì)出現(xiàn)了一種情況就是我的處的下標(biāo)上已經(jīng)存在了元素登澜。那么就會(huì)造成沖突。為了解決沖突我們有兩種解決方案
使用好的散列函數(shù)
key -> array 沒錯(cuò)將我們以前的value改成數(shù)組這樣就可以是一對(duì)多的關(guān)系
性能
上面的沖突給我的性能帶來了一些性能的影響飘庄，如果一個(gè)不好的散列函數(shù)的出的數(shù)組同一位置上的元素越來越多脑蠕，那么查找速度就會(huì)越來越慢，所以就會(huì)影響性能。
總結(jié)
每門編程語言都會(huì)編寫散列表的實(shí)現(xiàn)谴仙，所以你無須自己實(shí)現(xiàn)
注意使用的散列函數(shù)迂求，它會(huì)影響你的性能
注意沖突
散列表的用途
