散列表 就是哈希表衫哥。
思想是：用數(shù)組支持按照下標隨機訪問數(shù)據(jù)的特性實現(xiàn)的一種數(shù)據(jù)結(jié)構(gòu)茎刚，時間復(fù)雜度是O(1)。是數(shù)組的一種擴展撤逢。
散列表中使用散列函數(shù)把元素的鍵值映射為下標膛锭，將數(shù)據(jù)存儲在數(shù)組中對應(yīng)的下標中粮坞。
查詢元素的時候用同樣的散列函數(shù)，將鍵值轉(zhuǎn)化為數(shù)組下標初狰，從而讀取到位置莫杈。
散列函數(shù)
散列函數(shù) 是用來把Key進行散列的一個方法。
設(shè)計基本要求：
- 計算的散列值是一個非負整數(shù)
- key值相等奢入，散列后的值也相等筝闹。
- key值不相等，散列后的值不相等腥光。
著名的哈希函數(shù)算法 MD5,SHA,CRC算法也無法避免哈希沖突关顷。所以第三點要求無法達到完美的匹配。
散列沖突
哈希沖突是 計算hash值武福，兩個不同的key 得到兩個一樣的hash值议双。
常用的哈希沖突解決方案有兩類：開放尋址法與鏈表法
開放尋址法
核心思想：出現(xiàn)散列沖突，重新探測一個空閑位置將其插入艘儒。
線性探測
-
插入數(shù)據(jù)
往鏈表中插入數(shù)據(jù)聋伦，某個數(shù)據(jù)經(jīng)過散列后存儲位置被占用，從當前位置開始往后進行查找界睁，查找到空閑位置就將數(shù)據(jù)插入到空閑位置。
摘自極客時間 -
查找數(shù)據(jù)
通過散列函數(shù)求出要查找元素的鍵值對對應(yīng)的散列值兵拢，比較數(shù)組下標中的散列值是否相等于要查找的元素翻斟。相等，則是我們要查找的數(shù)據(jù)说铃，不相等則按照順訊往后依次查找访惜。遍歷到數(shù)組空閑的位置還沒有查找到需要的元素，就說明要尋找的元素沒有在散列表中
摘自極客時間 - 刪除數(shù)據(jù)
刪除數(shù)據(jù)腻扇，并不是真的把數(shù)據(jù)刪除债热，而是在數(shù)據(jù)上標記為deleted,線性探查的時候遇到標記為deleted空間不停止，繼續(xù)往下探測幼苛。 - 存在的問題
線性探測窒篱，插入的數(shù)據(jù)越多，散列沖突的可能性越大舶沿，并且空閑位置越來越少墙杯，極端情況下可能需要將整個散列表進行遍歷尋找空間。
二次探測和雙重散列
二次探測在一次探測的基礎(chǔ)上進行步長的平方括荡。
雙重散列使用的是一組散列函數(shù)高镐，先用第一個散列函數(shù)計算哈希值，如果被占用畸冲，在用第二個散列函數(shù)嫉髓，如果還被占用观腊，以此類推進行第三個第四個散列函數(shù)，直到找到空閑的存儲位置算行。
采取哪種方式的探測梧油，隨著數(shù)據(jù)量的增大，空閑位置不多的情況纱意，哈希沖突的概率就會增大婶溯。因此就需要保證散列表中存儲一定比例的空閑槽位。
解決方案：裝載因子
裝載因子 = 填入表中的元素個數(shù)/散列表的長度
裝載因子越大偷霉，空閑位置越少迄委，沖突越多，性能就會下降类少。
鏈表法
在散列表中 增加桶或者槽的概念叙身，Java中就是類似的概念。并且每個槽對應(yīng)一條鏈表硫狞，所有散列表值相同的元素信轿，我們都放到相同槽位對應(yīng)的鏈表中。
插入時間復(fù)雜度是O(1);
查找與刪除残吩，計算出hash值之后财忽，去鏈表中進行遍歷。
時間復(fù)雜度與鏈表的長度k有關(guān),也是就是O(K)泣侮。
散列均勻的散列函數(shù) k = n/m 即彪。 n代表的是散列中數(shù)據(jù)的個數(shù)，m代表散列表中槽的個數(shù)活尊。
問題
10萬條URL訪問日志隶校，按照訪問次數(shù)給URL排序？
兩個字符串數(shù)據(jù)蛹锰，每個數(shù)組大約有10萬條字符串深胳，快速查找數(shù)組中相同的字符串。
