哈希表和散列表壹樣嗎如下:
“散列表(hash table)和哈希表是壹回事。通過用空間換時間的方式,將查找時間從O(n)下降到O(1),類似於python字典這種數據結構,只是鍵值是用哈希函數計算出來的。
散列表(Hash table,也叫哈希表),是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說,它通過把關鍵碼值映射到表中壹個位置來訪問記錄,以加快查找的速度。這個映射函數叫做散列函數,存放記錄的數組叫做散列表。
給定表M,存在函數f(key),對任意給定的關鍵字值key,代入函數後若能得到包含該關鍵字的記錄在表中的地址,則稱表M為哈希(Hash)表,函數f(key)為哈希(Hash)函數。
常用方法:
通過將關鍵字key映射到表中壹個位置,可以直接訪問記錄,以提高查找的速率,相比較其他的查找結構,哈希表查找的時間復雜度更低。其中用於映射的函數稱為哈希函數,哈希函數有多種,常見的哈希函數包括CRC32,MD5,SHA等。
由於哈希表的特殊性質,其在安全加密,數據校驗,唯壹標識,負載均衡等場景都有著不可替代的作用。
基本概念:
1、若關鍵字為k,則其值存放在f(k)的存儲位置上。由此,不需比較便可直接取得所查記錄。稱這個對應關系f為散列函數,按這個思想建立的表為散列表。
2、對不同的關鍵字可能得到同壹散列地址,即k1≠k2,而f(k1)==f(k2),這種現象稱為沖突(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。
綜上所述,根據散列函數f(k)和處理沖突的方法將壹組關鍵字映射到壹個有限的連續的地址集(區間)上,並以關鍵字在地址集中的“像”作為記錄在表中的存儲位置,這種表便稱為散列表,這壹映射過程稱為散列造表或散列,所得的存儲位置稱散列地址。
3、若對於關鍵字集合中的任壹個關鍵字,經散列函數映象到地址集合中任何壹個地址的概率是相等的,則稱此類散列函數為均勻散列函數(Uniform Hash function),這就是使關鍵字經過散列函數得到壹個“隨機的地址”,從而減少沖突。