哈希表(也稱為哈希表)是壹種可以根據鍵值直接訪問的數據結構。換句話說,它通過將鍵值映射到表中的某個位置來訪問記錄,從而加快搜索速度。這種映射函數稱為哈希函數,存儲記錄的數組稱為哈希表。
給定壹個表m,有壹個函數f(key)。對於任何給定的鍵值,如果在將包含該鍵的表中記錄的地址代入函數後可以獲得,則表m稱為哈希表,函數f(key)是哈希函數。
平均而言,具有最快搜索速度並能適應插入和刪除的數據結構是哈希表。
哈希表的特征
1,快速訪問。
由於哈希表具有哈希函數,所有指定的鍵都可以映射到壹個地址,因此在訪問某個鍵對應的值(Value)時,完全不需要逐個搜索,可以直接跳轉到該地址。因此,當我們對哈希表進行添加、刪除、修改、搜索等操作時,速度非常快。
2.需要額外空間
首先,哈希表實際上是不滿足的。如果哈希表剛好滿了,那壹定是巧合。而且當哈希表中元素的利用率越來越高時,性能就會下降,所以壹般會選擇擴展來解決這個問題。
此外,如果存在沖突,它還需要額外的空間來存儲它們,例如鏈地址方法,它不僅需要額外的空間,而且還需要使用其他數據結構。有壹個很常用的詞來表達這種特征,它被稱為“空間換時間”。在大多數情況下,為了實現更好的性能,我們通常會考慮犧牲壹些空間來使算法更快。
3.混亂
哈希表的另壹個明顯特征是無序。為了更快地訪問元素,哈希表直接根據哈希函數找到存儲地址,這樣我們的訪問速度可以更快,但沒有辦法處理有序訪問。
4.可能會發生碰撞。
沒有壹個完美的哈希函數,總是會發生沖突,因此需要解決沖突,這也使哈希表變得更加復雜。通常,在不同高級語言的實現中,沖突的解決方案不壹定相同。