哈希表又稱散列表巷屿，是根據(jù)關(guān)鍵碼值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)，即通過關(guān)鍵碼將值映射到表中的某個位置來存儲和訪問墩虹，以加快查找的速度嘱巾。哈希表是字典的實現(xiàn)原理，字典通過哈希表來存儲數(shù)據(jù)诫钓，而讀取的時候也是通過哈希表來獲取對應(yīng)的值旬昭。無論哈希表中有多少數(shù)據(jù)，增刪操作的時間復(fù)雜度都為O(1),相當(dāng)于無須查找菌湃，直接定位對其操作稳懒。
哈希表的存儲方式是以數(shù)組為基礎(chǔ)，每個元素是一個鏈表慢味，鏈表上的元素的查找是根據(jù)特定的哈希算法決定的场梆，并盡量避免哈希沖突。
如何減少和希函數(shù)產(chǎn)生的沖突纯路？
- 需要將哈希函數(shù)的返回數(shù)據(jù)在哈希表中的位置盡可能的分布均勻或油，避免集中在某些數(shù)組中。
- 當(dāng)沖突產(chǎn)生時需要更快更方便的方式來解決沖突驰唬，提供再深一級的哈希碼顶岸。
- 每組中應(yīng)保持適當(dāng)?shù)逆湵韨€數(shù)，并控制出發(fā)擴容的裝填因子α = 填入鏈表中的數(shù)據(jù)個數(shù) / 鏈表的總數(shù)叫编。裝填因子一是控制擴容辖佣，二是避免哈希沖突。
哈希表解決沖突的方案：
開放定制法
三種：線性探測再散列搓逾、平方探測再散列卷谈、隨機探測再散列
（表格解釋：從前向后插入數(shù)據(jù)，如果插入位置已經(jīng)占用霞篡，發(fā)生沖突世蔗，沖突的另起一行，計算地址朗兵，直到地址可用污淋，后面沖突的繼續(xù)向下另起一行。最終結(jié)果取最上面的數(shù)據(jù)（因為是最“占座”的數(shù)據(jù)））
avatar
鏈地址法
產(chǎn)生hash沖突后在存儲數(shù)據(jù)后面加一個指針余掖，指向后面沖突的數(shù)據(jù)
上面的例子寸爆，用鏈地址法則是下面這樣：
avatar
沒找到想要的？點擊
參考HashMap 查看更多HashMap精講
