學習地址：【數(shù)據(jù)結構與算法基礎-java版】? ? ? ? ? ? ? ? ??🚀數(shù)據(jù)結構--Java專欄🚀

• 筆記01【01-09】【概述、數(shù)組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節(jié)點)、循環(huán)鏈表、雙向循環(huán)鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數(shù)、隊列基數(shù)）】
• 筆記04【28-33】【樹結構(二叉樹)概述、創(chuàng)建、遍歷、查找節(jié)點、刪除節(jié)點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現(xiàn)及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(xiàn)(數(shù)據(jù)壓縮、創(chuàng)建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節(jié)點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉、雙旋轉】
• 筆記09【58-60】【計算機中數(shù)據(jù)的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數(shù)的設計、散列沖突解決方案】
• 筆記11【64-67】【圖結構概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現(xiàn)】

目? ?錄

P61 5.1 哈希表概述

1、哈希表概念

P62 5.2 散列函數(shù)的設計

P63 5.3 散列沖突的解決方案

1、開放地址法

1.1、線性探測法

1.2、二次探測法

1.3、再哈希法

2、鏈地址法

---

P61 5.1 哈希表概述

1、哈希表概念

百度百科：https://baike.baidu.com/item/%E5%93%88%E5%B8%8C%E8%A1%A8/5981869?fr=aladdin

散列表（Hash table，也叫哈希表），是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

給定表M，存在函數(shù)f(key)，對任意給定的關鍵字值key，代入函數(shù)后，若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash)表，函數(shù)f(key)為哈希(Hash)函數(shù)。

• 若關鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數(shù)，按這個思想建立的表為散列表。

• 對不同的關鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為沖突（英語：Collision）。具有相同函數(shù)值的關鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。

• 若對于關鍵字集合中的任一個關鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突。

哈希表（散列表）：關鍵字年齡，通過存儲位置（取余/減去固定值），返回相應的數(shù)據(jù)。

P62 5.2 散列函數(shù)的設計

散列函數(shù)的設計：計算簡單、分布均勻。?

直接定址法（直接、計算簡單、不好用、分布不均勻）：將關鍵字作為 下標(存儲地址)。【電話號碼，不適合！】

數(shù)字分析法：需要提前知道關鍵字。

平方取中法：數(shù)字進行平方運算，取中間1、2、3個數(shù)字。

隨機數(shù)法：存儲地址=random();

哈希表底層，使用數(shù)組。

P63 5.3 散列沖突的解決方案

散列函數(shù)：解決地址沖突問題。【數(shù)據(jù)：11、12、22、21、23】【取余法（%10）】

1、開放地址法

1.1、線性探測法

線性探測法：數(shù)據(jù)沖突，緊跟著數(shù)據(jù) 進行存儲。問題：數(shù)據(jù)聚集。

1.2、二次探測法

二次探測法：解決數(shù)據(jù)聚集問題。數(shù)據(jù)所在的位置，已有數(shù)據(jù)，根據(jù) 1^2、2^2、3^2……往后放。

1.3、再哈希法

散列函數(shù)

2、鏈地址法

鏈表：無限延伸。

總結

以上是生活随笔為你收集整理的数据结构Java10【哈希表概述、散列函数的设计、散列冲突解决方案】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。