什么樣的“東西”可以稱之為哈希表？其實就是經(jīng)常想不起來卻刻在 DNA 里的知識點
數(shù)據(jù)結構三要素：
1,數(shù)據(jù)的邏輯結構：邏輯結構顧名思義就是邏輯上的結構，比如我們知道一棵二叉樹的非葉子節(jié)點會有左右與左右兩個子樹的樹根相連力试。
2,數(shù)據(jù)的物理結構：物理結構就是數(shù)據(jù)結構真正的存儲方式毛仪，二叉樹我們一般通過二叉鏈表存取，但是也能用數(shù)組存取对粪。這就是說一個邏輯結構可以對應不同的物理結構右冻。
3,數(shù)據(jù)的運算：就是可有對這個數(shù)據(jù)結構進行哪些操作，比如可以對二叉樹進行遍歷操作著拭，這就是一種運算纱扭。
把任意結構，任意長度的輸入儡遮，快速的映射成一個固定長度的輸出乳蛾，這個過程就叫哈希，實現(xiàn)這個功能的東西就叫哈希函數(shù)。
哈希函數(shù)需要滿足兩個性質(zhì):
對于相同的輸入肃叶，必須有相同的輸出忆首；
對于不同的輸入，允許有相同的輸出被环。
哈希表是解決查找問題的糙及，hashcode值就是你要找的數(shù)據(jù)所在的位置(下標)，那個位置的值是value
數(shù)組：數(shù)組就是一塊連續(xù)的內(nèi)存空間筛欢。這個空間可以放在棧上浸锨，可以放在堆上。因為知道元素的大小版姑，再根據(jù)下標可以計算到元素在這塊連續(xù)的內(nèi)存中的位置柱搜。接著你就可以將你的元素保存到這塊連續(xù)的內(nèi)存的某個位置。這塊連續(xù)的內(nèi)存不可能無限的大剥险，所以要根據(jù)實際的情況來決定數(shù)組需要多大聪蘸。并且數(shù)組進行擴充的話，有可能會出現(xiàn)內(nèi)存拷貝的現(xiàn)象表制。健爬。因為你沒辦法知道你申請的那塊連續(xù)的內(nèi)存空間的后面的內(nèi)存有沒有人使用。
哈希表（HashSet）：哈希表也稱散列表么介。原理就是通過哈希函數(shù)（下面使用hash()代替）計算元素的哈希值娜遵。計算出來的哈希值是32位的。當然壤短，我們可以把這32位的哈希值看成一個無符號的32位整形（下面使用uint32）设拟。最后，我們再創(chuàng)建一個key類型的數(shù)組（假設大小為8）久脯。這時候纳胧，假設我們要添加一個元素，我們就使用 hash(key)%8 計算出元素應該存儲在數(shù)組中的位置（hash(key)%8的范圍是0-7帘撰，不會使數(shù)組越界）跑慕。這時，key就與數(shù)組之間建立了一個映射關系骡和。當然相赁，不同的key計算（hash(key)%8）出來的結果（數(shù)組的下標）有可能是一樣的。例如先前這個位置已經(jīng)有元素存儲了慰于，現(xiàn)在又有個元素映射到這個位置钮科，我們怎么辦？這種情況我們稱為哈希沖突婆赠，解決的方式有2種绵脯。 第1種為鏈式存儲法佳励，也就是數(shù)組的每個元素都是一個鏈表，來記錄映射到該下標的所有元素蛆挫。 第2種為二度哈希赃承，也就是使用哈希后加上一定的計算，在當前的位置下再計算另一個位置出來悴侵。當然瞧剖，無論哪種，接下來的查找都是線性的可免。哈希表一般都是HashSet<TKey>抓于，可以看到只有key，一般都用于存儲元素浇借，并且可以快速的查找元素在集合中是否存在捉撮。字典（Dictionary）：字典也是散列表的一種，跟上面說的哈希表唯一不同的就是妇垢。哈希表使用hash(key)%8得到數(shù)組存儲位置后巾遭，它存儲的是key。闯估。而字典存儲的是value灼舍，僅此區(qū)別而已。所以字典是Dictionary<TKey,TValue>睬愤。片仿。他的作用就是可以根據(jù)key快速的查找到value。
https://zhuanlan.zhihu.com/p/78107140
https://zhuanlan.zhihu.com/p/52440208
