python內(nèi)置類(lèi)型有一個(gè)字典類(lèi)型(dict)和兩個(gè)兩個(gè)集合類(lèi)型（set and frozenset）
。在創(chuàng)建空字典和很小字典是吧兔，初始分配的存儲(chǔ)區(qū)可容納8個(gè)元素磷仰。
。如果虛妄自定義的對(duì)象也能座位dict或者set等的關(guān)鍵碼境蔼，定義一個(gè)hash方法灶平。
hash字典最主要是要解決hash沖突。
hash沖突是肯定存在的箍土，消除沖突的方法分為兩類(lèi)：
內(nèi)消除方法 （基本存儲(chǔ)區(qū)內(nèi)部解決沖突問(wèn)題）
外消除方法 （基本存儲(chǔ)區(qū)外部解決沖突問(wèn)題）
基本要求
保證當(dāng)前這次存入數(shù)據(jù)項(xiàng)的工作能
正常完成;保證字典的
基本存儲(chǔ)性質(zhì)逢享。
解決沖突的方法
- 開(kāi)地址法
內(nèi)消除的基本方法
。在準(zhǔn)備插入數(shù)據(jù)并發(fā)現(xiàn)沖突時(shí)吴藻，設(shè)法在基本存儲(chǔ)區(qū)（順序表）里為需要插入的數(shù)據(jù)項(xiàng)另行安排一個(gè)位置
.....多種方法瞒爬，沒(méi)有全部列出來(lái)
探查方法
-
線(xiàn)性探測(cè)
缺點(diǎn)：隨著表中數(shù)據(jù)的增加，產(chǎn)生沖突的可能性也不斷增長(zhǎng)
數(shù)據(jù)在表中逐漸堆積成段，使線(xiàn)性探查序列變得越來(lái)越長(zhǎng)
-
雙散列探測(cè)
位置檢查以不同方式跳躍進(jìn)行侧但，有可能減少關(guān)鍵碼堆積的發(fā)生矢空。
1、 數(shù)據(jù)的存儲(chǔ)和訪(fǎng)問(wèn)是計(jì)算機(jī)最基本的功能禀横。
2屁药、數(shù)據(jù)訪(fǎng)問(wèn)的基本方式基于存儲(chǔ)位置。
3燕侠、字典的實(shí)現(xiàn)可以使用線(xiàn)性結(jié)構(gòu)者祖、樹(shù)形結(jié)構(gòu)或者其他各種結(jié)構(gòu)。使用：順序表绢彤，二叉樹(shù)或者其他樹(shù)形結(jié)構(gòu)。
線(xiàn)性表 連續(xù)表 散列表
4蜓耻、字典分類(lèi)
靜態(tài)字典：內(nèi)容和結(jié)構(gòu)不變茫舶，只有檢索。
動(dòng)態(tài)字典：動(dòng)態(tài)變化 刹淌，還有插入和刪除饶氏。
5、平均檢索長(zhǎng)度 ASL
在一次完整檢索過(guò)程中比較關(guān)鍵碼的平均次數(shù)有勾。Average Search Length
6疹启、字典功能
1）作為一種數(shù)據(jù)結(jié)構(gòu)，支持在字典里存儲(chǔ)一批數(shù)據(jù)項(xiàng)蔼卡；
2）提供支持?jǐn)?shù)據(jù)檢索的功能喊崖，設(shè)法維護(hù)從關(guān)鍵碼找到相關(guān)數(shù)據(jù)的聯(lián)系信息。
【1】線(xiàn)性表字典
單鏈表 雇逞，雙鏈表
荤懂。任意排序，插入在表頭插入是O(1)操作塘砸，檢索和刪除需要掃描整個(gè)表节仿，是O(n)操作
。如果表中的數(shù)據(jù)項(xiàng)按關(guān)鍵碼升序或者降序排列掉蔬，插入需要檢索正確位置廊宪，O(n)
刪除和檢索同需要順序掃描檢查，平均檢查半個(gè)表女轿，為O(n)操作
箭启。易于實(shí)現(xiàn)，結(jié)構(gòu)簡(jiǎn)單
但是檢索效率低谈喳，插入册烈、刪除的效率也很低
【2】散列表字典 (python采用的散列表技術(shù))
。散列表
。散列表實(shí)現(xiàn)字典
1）選定一個(gè)整數(shù)的下標(biāo)范圍赏僧，建立一個(gè)包括相應(yīng)元素位置范圍的順序表
2）映射h h為散列函數(shù)大猛，哈希函數(shù) 雜湊函數(shù)
常用的哈希函數(shù)：除余法，基數(shù)轉(zhuǎn)換法
