一、hash中的Key和value的區別
hash中的Key和value本意是鑰匙和值的意思,在應用中通常被用作鍵值對,例如在map、json中等。在鍵值對中,key是關鍵字,value是值,例如:{“firstName”:?“Brett”,?“lastName”:?“McLaughlin”}。在這個json中,firstName和lastName是key,分別對應的value是Brett和McLaughlin。
哈希表基本概念
哈希表(Hash Table):也叫散列表,是根據關鍵碼值(Key-Value)而直接進行訪問的數據結構,也就是我們常用到的map。
哈希函數:也稱為是散列函數,是Hash表的映射函數,它可以把任意長度的輸入變換成固定長度的輸出,該輸出就是哈希值。哈希函數能使對一個數據序列的訪問過程變得更加迅速有效,通過哈希函數數據元素能夠被很快的進行定位。
若關鍵字為k,則其值存放在f(k)的存儲位置上。由此,不需比較便可直接取得所查記錄。稱這個對應關系f為哈希函數,按這個思想建立的表為哈希表。
設所有可能出現的關鍵字集合記為U(簡稱全集)。實際發生(即實際存儲)的關鍵字集合記為K(|K|比|U|小得多)。
散列方法是使用函數h將U映射到表T[0..m-1]的下標上(m=O(|U|))。這樣以U中關鍵字為自變量,以h為函數的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。
其中:
① h:U→{0,1,2,…,m-1} ,通常稱h為哈希函數(Hash Function)。哈希函數h的作用是壓縮待處理的下標范圍,使待處理的|U|個值減少到m個值,從而降低空間開銷。
② T為哈希表(Hash Table)。
③ h(Ki)(Ki∈U)是關鍵字為Ki結點存儲地址(亦稱散列值或散列地址)。
④ 將結點按其關鍵字的哈希地址存儲到哈希表中的過程稱為散列(Hashing)
延伸閱讀:
二、哈希沖突
1)沖突
兩個不同的關鍵字,由于散列函數值相同,因而被映射到同一表位置上。該現象稱為沖突(Collision)或碰撞。發生沖突的兩個關鍵字稱為該散列函數的同義詞(Synonym)。
2)安全避免沖突的條件
最理想的解決沖突的方法是安全避免沖突。要做到這一點必須滿足兩個條件:
①其一是|U|≤m
②其二是選擇合適的散列函數。
這只適用于|U|較小,且關鍵字均事先已知的情況,此時經過精心設計散列函數h有可能完全避免沖突。
3)沖突不可能完全避免
通常情況下,h是一個壓縮映像。雖然|K|≤m,但|U|>m,故無論怎樣設計h,也不可能完全避免沖突。因此,只能在設計h時盡可能使沖突最少。同時還需要確定解決沖突的方法,使發生沖突的同義詞能夠存儲到表中。
4)影響沖突的因素
沖突的頻繁程度除了與h相關外,還與表的填滿程度相關。
設m和n分別表示表長和表中填入的結點數,則將α=n/m定義為散列表的裝填因子(Load Factor)。α越大,表越滿,沖突的機會也越大。通常取α≤1。