直接尋址法
U表示所有可能出現(xiàn)的key范圍寸五,K表示實際的key。如圖建一個列表逢并,下標(biāo)包含所有可能的key
缺點:
- 當(dāng)U范圍很大時弛矛,實際的K范圍很小浴麻,費內(nèi)存
- 只能處理key是 數(shù)字的情況
哈希表概念
哈希表又稱散列表得问,是一種線性表存儲結(jié)構(gòu)。在直接尋址表上做了修改软免,由一個直接尋址表和一個哈希函數(shù)組成宫纬,哈希函數(shù)h(key)返回元素的存儲下標(biāo)。
哈希表通常支持如下操作:
- insert(key,value):插入鍵值對
- get(key):得到鍵為key的value值
- delete(key):刪除鍵為key的鍵值對
哈希沖突
由于哈希表(直接尋址表)大小是有限膏萧,存儲的值總數(shù)量是無限的漓骚,對于任何哈希函數(shù),都可能出現(xiàn)兩個不同的元素映射到同一個下標(biāo)
解決哈希沖突
- 開放尋址法:如果哈希函數(shù)返回的位置已經(jīng)有值榛泛,可以向后探查新的位置來存儲該值
- 線性探查:如果位置i被占用蝌蹂,探查i+1、i+2曹锨、...
- 二次探查:如果位置i被占用孤个,探查i+12、i+22艘希、...
- 二度哈希:有n個哈希函數(shù)硼身,當(dāng)?shù)谝粋€哈希函數(shù)h1發(fā)生沖突時硅急,嘗試使用h2覆享、h3、...
- 拉鏈法:哈希表每個位置都連接一個鏈表营袜,沖突的元素將被加到對應(yīng)位置鏈表的最后
哈希表在python的應(yīng)用
python中字典和集合都是通過哈希表實現(xiàn)
比如字典:{"name":"tom","age":12,"hobby":"swimming"}
撒顿,假設(shè)h("name")=2,h("age"=1)荚板,h("hobby")=0
凤壁,哈希表的存儲為["swimming",12,"tom"]