哈希表
概念
hash table侄榴，key直接映射到存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)立砸，插入和查找需要的計(jì)算量跟表的大小沒關(guān)系斩狱，也就是所謂的O(1)耳高。
不同的Key會(huì)被分散到表的各個(gè)位置，相同的Key總是對(duì)應(yīng)著相同的存儲(chǔ)位置所踊。
沖突
常見的解決沖突的方式：link-list 或 open addressing
鏈表法： 如果產(chǎn)生沖突就在原地形成一個(gè)鏈表泌枪，但是這樣理論上最壞的情況，所有的key都計(jì)算為同一個(gè)位置存儲(chǔ)秕岛，那么哈希表退化成鏈表碌燕，查找和插入的復(fù)雜度都變成O(n)。
設(shè)計(jì)
在手?jǐn)]了一個(gè)簡(jiǎn)單的hashtable后瓣蛀，總結(jié)一些設(shè)計(jì)上的細(xì)節(jié)
- 基礎(chǔ)的hash函數(shù)單獨(dú)作為一個(gè)函數(shù)陆蟆，僅提供盡量隨機(jī)的索引計(jì)算
- 碰撞檢測(cè)單獨(dú)作為一個(gè)函數(shù)(要承載沖突檢測(cè)，可用索引探查惋增，查重)
類似于 bool collisiondetect(int& index, const Keytype key) - 查找接口使用基礎(chǔ)hash&碰撞檢測(cè)加對(duì)比邏輯
- key要存儲(chǔ)在元素類里面
- insert其實(shí)要用到find,哈希表的擴(kuò)容僅在insert接口觸發(fā)
