【Abstract】In order to improve the efficiency of the algorithm, the hash idea is a very useful method in the practice of the algorithm. The reasonable use of hash idea to solve the algorithm problem can effectively help us solve the algorithm problem, especially some problems are very suitable for using hash idea to solve. This article will use some examples on LeetCode to explain and illustrate some practical cases of hashing ideas in algorithm cases.
【摘要】為了提高算法的效率，哈希思想是在算法實(shí)踐中很有用的的一個(gè)方法婆殿，合理運(yùn)用哈希思想來解決算法問題，可以有效的幫助我們解決算法問題，尤其是有些問題非常適合使用哈希思想來解決。本文將借助LeetCode上的一些例子掖看，來講解和說明哈希思想在算法案例中的一些實(shí)踐案例演训。
【關(guān)鍵詞】 算法思想 LeetCode 算法效率 算法
一、引言
在日常進(jìn)行代碼編程和實(shí)際的工作中膝擂，經(jīng)常會(huì)遇到需要設(shè)計(jì)一些算法的場景，哈希表作為數(shù)據(jù)結(jié)構(gòu)中常見的一種形式，有很大的用處架馋，合理使用哈希表可以有效的幫助到我們來設(shè)計(jì)更有效率的算法狞山。一般地，在很多算法設(shè)計(jì)的時(shí)候叉寂，都會(huì)遇到動(dòng)態(tài)集合的需求萍启，需要支持插入、查找屏鳍、刪除的操作勘纯，使用哈希表來構(gòu)建，會(huì)是一種非常有效的思路钓瞭。哈希思想就是使用哈希表的手段驳遵，來解決一些實(shí)際的問題，即本文主要通過一些實(shí)踐例子來試圖講解哈希思想的運(yùn)用山涡。
二堤结、什么是哈希思想
哈希表也叫散列表，由三部分組成佳鳖，一部分是關(guān)鍵字霍殴，也叫直接尋址表，一部分是數(shù)組系吩，也叫哈希表或者散列表来庭，一部分是哈希函數(shù)，也叫散列函數(shù)穿挨，可以通過關(guān)鍵字通過散列函數(shù)在數(shù)組中查找數(shù)據(jù)月弛，這樣理想的情況就是查找時(shí)間O(1)，最差的情況會(huì)出現(xiàn)整個(gè)列表全都查找一遍科盛，時(shí)間是O(n)帽衙。但是這種最差的情況一般不會(huì)出現(xiàn)，因?yàn)楣１淼年P(guān)鍵字在構(gòu)建的時(shí)候一般盡量選擇具有唯一性的值贞绵，比如使用哈希散列算法計(jì)算出來的哈希值厉萝。哈希思想簡單總結(jié)來說，就是構(gòu)建一個(gè)關(guān)鍵字函數(shù)榨崩，然后通過哈希函數(shù)來與數(shù)組部分相關(guān)聯(lián)就可以查找數(shù)據(jù)了谴垫。
當(dāng)關(guān)鍵字?jǐn)?shù)量比較小的時(shí)候，可以使用直接尋址法母蛛，把全部的關(guān)鍵字都構(gòu)建出來翩剪，然后建立查找關(guān)系就可以了。當(dāng)關(guān)鍵字比較多的時(shí)候彩郊，可以使用開放尋址法前弯，按照需要蚪缀，動(dòng)態(tài)構(gòu)建相關(guān)的關(guān)鍵字集合，然后再建立增刪改查的關(guān)系就可以了恕出。構(gòu)建完全哈希表询枚，靜態(tài)存儲(chǔ)全部關(guān)鍵字，可以在完全哈希表中最壞情況下完成關(guān)鍵字查找剃根，這種在有些情況下也是合適的做法哩盲，具體采用何種做法前方，視具體情況而定狈醉。
當(dāng)關(guān)鍵字無法保證覆蓋全部的數(shù)據(jù)時(shí)，就會(huì)出現(xiàn)關(guān)鍵字沖突惠险，導(dǎo)致一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)數(shù)據(jù)苗傅，采用的方法很多，比如對(duì)于沖突的數(shù)據(jù)采用鏈表的方式班巩，或者紅黑樹來建立查找關(guān)系渣慕，通過一一查找來尋找數(shù)據(jù)，這種方法好處是基本可以覆蓋所有的數(shù)據(jù)抱慌，壞處是逊桦，在沖突的關(guān)鍵字上會(huì)存在數(shù)據(jù)堆積現(xiàn)象，可能需要把沖突的數(shù)據(jù)全部查找一遍才可以抑进，而且還需要另外開辟一個(gè)空間來存儲(chǔ)數(shù)據(jù)强经，增加空間消耗。當(dāng)然還有別的辦法寺渗，比如開放尋址法匿情，當(dāng)關(guān)鍵字沖突的時(shí)候，使用在散列法信殊，使用該關(guān)鍵字再生成一個(gè)新的關(guān)鍵字炬称，如果還沖突就重復(fù)再用新生成的這個(gè)關(guān)鍵字生成一個(gè)關(guān)鍵字，直到不重復(fù)為止涡拘，這種方法的優(yōu)點(diǎn)是玲躯，保證可以放下全部的數(shù)據(jù)，節(jié)省空間鳄乏，這種方法的缺點(diǎn)是不能真正地刪除數(shù)據(jù)战得，因?yàn)楹竺嫘律傻年P(guān)鍵字是可能和之前刪除的關(guān)鍵字相關(guān)的，只能標(biāo)記一下已經(jīng)刪除了恤煞。在開放尋址法中重新生成沖突的關(guān)鍵字的方法刊苍，還有鏈表法，還有比如線性探查法仲吏，直接依次探查下一個(gè)關(guān)鍵字就可以了不铆，還有比如二次探查蝌焚、雙重散列、建立公共溢出區(qū)等等方法誓斥。
隨著哈希表數(shù)據(jù)的增加只洒，可以使用裝填因子也叫裝載因子來表示當(dāng)前數(shù)據(jù)的填滿程度，裝填因子的計(jì)算方法是裝入哈希表中的關(guān)鍵字個(gè)數(shù)與當(dāng)前哈希表總的長度的比值劳坑，當(dāng)裝填因子越大的時(shí)候毕谴，填充的數(shù)據(jù)越多，空間利用率越高距芬，但是關(guān)鍵字沖突的可能性就會(huì)增加涝开，查找數(shù)據(jù)的成本可能就會(huì)增加。當(dāng)裝填因子越小的時(shí)候框仔，填充的數(shù)據(jù)越少舀武，空間利用率就越低，關(guān)鍵字沖突的概率就會(huì)減少离斩，查找數(shù)據(jù)的成本越低银舱。往往在設(shè)置裝填因子的時(shí)候，就需要根據(jù)實(shí)際情況做一些取舍和平衡來沖突的概率和空間利用率跛梗，然后根據(jù)裝填因子來決定是否增加哈希表的長度還是什么別的處理寻馏。
文本的代碼實(shí)現(xiàn)都是使用Java實(shí)現(xiàn)。
三核偿、刪除字符使頻率相同
題目描述：
給你一個(gè)下標(biāo)從0開始的字符串word诚欠，字符串只包含小寫英文字母。你需要選擇一個(gè)下標(biāo)并刪除下標(biāo)處的字符宪祥，使得word中剩余每個(gè)字母出現(xiàn)頻率相同聂薪。如果刪除一個(gè)字母后，并且恰好只刪除一個(gè)字母蝗羊，word中剩余所有字母的出現(xiàn)頻率都相同藏澳，那么返回true，否則返回false耀找。比如輸入的字符串是
aaccc翔悠，'c'的數(shù)量是3，數(shù)量減1野芒，就可以讓'a'和'c'的數(shù)量一樣蓄愁，所以返回tue。[1]
首先分析下該問題狞悲，首先我們需要遍歷一遍字符串撮抓，首先統(tǒng)計(jì)出所有字母的出現(xiàn)頻率。英文字母有26摇锋，且不考慮大小寫丹拯，只有小寫字母站超，那么我們就可以構(gòu)建一個(gè)哈希表來記錄字母的出現(xiàn)頻率，表的長度最大值也就是26了乖酬，因?yàn)殛P(guān)鍵字?jǐn)?shù)量很小死相，所以可以首先初始化出一個(gè)26長度的數(shù)組，也就是哈希表咬像，然后再去遍歷整個(gè)字符串算撮，按照26個(gè)字母的順序，來記錄頻率數(shù)據(jù)县昂，所以其實(shí)這就相當(dāng)于建立一個(gè)字母和頻率一一對(duì)應(yīng)關(guān)系的字典肮柜，這樣就可以節(jié)約內(nèi)存空間來避免保存所有的字母，因?yàn)閿?shù)組可以按照字母順序直接去讀取七芭，所以還可以節(jié)省插入時(shí)的時(shí)間消耗素挽。
然后就可以來處理上一步得到的數(shù)組了。首先如果得到的所有字母的最大數(shù)量就是1狸驳，也就是說字符串里所有的字母都不相同，那么可以直接返回為true缩赛，因?yàn)槿魏我粋€(gè)數(shù)量減1之后都可以符合條件耙箍。然后遍歷一遍這個(gè)數(shù)組，可以得到數(shù)量的最大值（下方代碼中的max酥馍，代表出現(xiàn)數(shù)量最多的次數(shù)是多少）和最小值（下方代碼中的min辩昆，代表出現(xiàn)數(shù)量最少的次數(shù)是多少），還可以得到最大數(shù)量出現(xiàn)的次數(shù)（下方代碼中的countMax旨袒，代表有多少種字母是這個(gè)最大數(shù)量max的）汁针，和最小數(shù)量出現(xiàn)的次數(shù)（下方代碼中的countMin，代表有多少種字母是這個(gè)最小數(shù)量min的）砚尽。如果判斷最大數(shù)量出現(xiàn)的次數(shù)等于全部的字符長度施无，那就代表該字符串全部的字母都相同，除非該字符串word的長度小于等于2可以返回為true必孤，否則是返回false猾骡。如果最大數(shù)量只出現(xiàn)了一次，也就是只有一種字母數(shù)量最多敷搪，那么最大的數(shù)量減去最小的數(shù)量兴想，差值為1或者0，比如abcc赡勘、abb嫂便、cdd、ab闸与、ef這樣的字符串毙替，這些都是可以返回為true的曼振，如果是abccc、abbccc蔚龙、abbb這樣的字符串就該返回false冰评。如果最大數(shù)量只出現(xiàn)了一次，也就是只有一種字母數(shù)量最多木羹，并且其他的字母都是1個(gè)甲雅，比如accccc、bffff這樣的字符串坑填，這些都是返回的true抛人，除此之外的其他的情況都是false。如果最大數(shù)量出現(xiàn)了多個(gè)脐瑰，但是最小數(shù)量的只出現(xiàn)了一個(gè)妖枚，并且這兩種加起來的數(shù)量剛好等于字符串的長度，就代表苍在，比如abbbccc绝页、effgg這樣的字符串，這些都應(yīng)該返回true寂恬，除此之外的其他情況都是false续誉，比如abbcccfff這樣的字符串就該是false。
實(shí)現(xiàn)的代碼如下：
class Solution {
public boolean equalFrequency(String word) {
int[] hash = new int[26];
int max = 0;
for (char c : word.toCharArray()) {
hash[c - 'a']++;
max = Math.max(hash[c - 'a'], max);
}
if (max == 1) return true;
int countMax = 0, countMin = 0, min = max;
for (Integer value : hash) {
if (value == 0) continue;
if (value < min) {
countMin = 1;
} else if (value == min) {
countMin++;
}
min = Math.min(value, min);
if (value == max) {
countMax++;
}
}
if (countMax == word.length()) return word.length() <= 2;
if (countMax == 1) {
return max - min == 1 || max - min == 0 || (countMin == 1 && min == 1 && max + min == word.length());
} else {
return countMin == 1 && min == 1 && ((countMax * max + countMin) == word.length());
}
}
}
以上代碼在本地執(zhí)行的時(shí)候初肉，當(dāng)輸入是s:wordgoodgoodgoodd時(shí)酷鸦，得到的結(jié)果是false計(jì)算耗時(shí)為23ms。當(dāng)輸入是s:abbbcccdddeeefff時(shí)牙咏，得到的結(jié)果是true計(jì)算耗時(shí)為24ms臼隔。在leetcode上執(zhí)行用時(shí)：0ms，計(jì)算的很快就得到了結(jié)果妄壶。因?yàn)榄h(huán)境的差異摔握，大家在比較算法的效率高低的時(shí)候，以leetcode上的為準(zhǔn)盯拱。
四盒发、串聯(lián)所有單詞的子串
題目描述：
給定一個(gè)字符串s和一個(gè)字符串?dāng)?shù)組words。words中所有字符串長度相同狡逢。s中的串聯(lián)子串是指一個(gè)包含words中所有字符串以任意順序排列連接起來的子串宁舰，比如words = ["ab","cd","ef"]，那么"abcdef"奢浑，"abefcd"蛮艰，"cdabef"，"cdefab"雀彼，"efabcd"壤蚜，和"efcdab" 都是串聯(lián)子串即寡。"acdbef"不是串聯(lián)子串，因?yàn)樗皇侨魏蝫ords排列的連接袜刷。返回所有串聯(lián)字串在s中的開始索引聪富。你可以以任意順序返回答案。[2]
方法一
看到這樣的問題時(shí)著蟹，最簡單的做法是墩蔓，首先生成word數(shù)組中的全排列，生成全排列的方法有很多萧豆，比如鄰位對(duì)換法奸披、回溯算法等等，這里不做贅述涮雷，但是無論是何種全排列方法阵面，隨著word數(shù)組中的數(shù)量增加，最后的時(shí)間復(fù)雜度都是指數(shù)級(jí)增長的洪鸭，最后有可能會(huì)花費(fèi)相當(dāng)長的時(shí)間來生成全排列样刷，如果電腦資源不夠的話，甚至?xí)墒∏涑埃瑢?duì)資源是一種極大的浪費(fèi)颂斜。所以看到這樣的問題，如何縮短時(shí)間復(fù)雜度呢拾枣？問題的關(guān)鍵就是如何處理關(guān)鍵字。
滑動(dòng)窗口也叫雙指針盒让，是我們?cè)谠O(shè)計(jì)算法的時(shí)候的一個(gè)很有用的方法梅肤。在面對(duì)需要我們處理字符串的情況下，可以設(shè)計(jì)一個(gè)窗口邑茄，窗口的大小可以是固定的姨蝴，也可以動(dòng)態(tài)變化的，之后按照一定的方向依次去掃描字符串或者數(shù)組或者其他的數(shù)據(jù)形式肺缕，然后在每次掃描之后處理窗口中出現(xiàn)的字符串或者數(shù)組或者其他的數(shù)據(jù)左医。在本問題中，首先統(tǒng)計(jì)下words中字符串出現(xiàn)的次數(shù)然后保存在wordMap中同木，當(dāng)做我們當(dāng)前要比較的哈希表浮梢，這樣在之后進(jìn)行比較的時(shí)候就不用每次都再來計(jì)算一遍wordMap了。因?yàn)閣ords中所有的字符串長度相同彤路，所以可以把單個(gè)字符串的長度記為wordLength秕硝，把words的字符數(shù)量記為n，那words中所有的字符串拼到一起洲尊，可以組成的字符串的長度是maxWordLength远豺。然后從左往右奈偏，每次開始的時(shí)候復(fù)制一份wordMap到diffMap中，作為當(dāng)前比較的哈希表躯护，依次讀取n個(gè)長度為wordLength的字符串惊来，然后判斷是否在diffMap中，如果出現(xiàn)了不存在于diffMap中的字符串棺滞，就代表該次讀取出來的字符串不符合要求裁蚁，直接開始下一輪讀取。那如何判斷該次讀取出的字符串是否存在于diffMap中呢检眯？可以把diffMap中的對(duì)應(yīng)的值減1厘擂，一直減到如果出現(xiàn)小于0的情況出現(xiàn)，就表示當(dāng)前的讀取出來的字符串不符合要求锰瘸，因?yàn)槊看巫x取出來的都是n個(gè)字符串刽严，在進(jìn)行減1操作的時(shí)候，除非全部符合diffMap的字符數(shù)避凝，否者就會(huì)出現(xiàn)某一個(gè)關(guān)鍵字減1之后小于0的情況出現(xiàn)舞萄，這樣就可以就可以簡化運(yùn)算，也就是說除非出現(xiàn)小于0的情況管削，除此之外就表示都是符合要求的倒脓。
實(shí)現(xiàn)的代碼如下，在leetcode上執(zhí)行用時(shí)：91ms含思。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words.length == 0) return result;
int wordLength = words[0].length(), maxWordLength = wordLength * words.length;
Map<String, Integer> wordMap = new HashMap<>();
for (String word : words) {
wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
}
Map<String, Integer> diffMap = new HashMap<>();
for (int i = 0; i < s.length() - maxWordLength + 1; i++) {
diffMap.clear();
diffMap.putAll(wordMap);
boolean haveIndex = true;
for (int n = 0; n < words.length; n++) {
String word = s.substring(i + n * wordLength, i + (n + 1) * wordLength);
int value = diffMap.getOrDefault(word, 0) - 1;
if (value >= 0) {
diffMap.put(word, value);
} else {
haveIndex = false;
break;
}
}
if (haveIndex) {
result.add(i);
}
}
return result;
}
}
方法二
如果仔細(xì)觀察崎弃，就會(huì)發(fā)現(xiàn)以上的算法存在一種浪費(fèi)的情況，那就是每次讀取了n個(gè)字符串出來做比較的時(shí)候含潘，會(huì)發(fā)現(xiàn)是存在重復(fù)讀取字符串來比較的饲做。基于此遏弱，可以優(yōu)化以上的算法盆均。在初始化wordMap的時(shí)候，都標(biāo)記為負(fù)數(shù)漱逸，作為哈希表泪姨。從左往右讀取，記字符串s的長度為ls饰抒，記開始讀取字符串的位置i肮砾，記words中的單個(gè)字符串長度為wordLength，words的字符串?dāng)?shù)量記為n循集，從i開始唇敞，讀取n個(gè)長度為wordLength的字符串，那就是把i~ls的字符串劃分為數(shù)個(gè)長度為wordLength的字符串，這樣疆柔，最后幾個(gè)不滿足wordLength的字符串就可以舍棄掉了咒精，因?yàn)闊o法構(gòu)成一個(gè)符合要求的字符串了。
設(shè)計(jì)好了滑動(dòng)的窗口旷档，然后就是開始移動(dòng)模叙，每次開始移動(dòng)的時(shí)候，把wordMap中的數(shù)據(jù)寫入到diffMap中初始化diffMap作為當(dāng)前的哈希表鞋屈，每次移動(dòng)一個(gè)長度為wordLength的字符串范咨，然后給diffMap中對(duì)應(yīng)的值加1，如果出現(xiàn)了等于0的情況就刪除該鍵值厂庇，如果diffMap中剛好全都被移除了渠啊，表示剛好符合要求，記錄下當(dāng)前的值权旷，除此之外表示全都不滿足要求替蛉。需要注意的是，外層循環(huán)的部分拄氯，只需要0~wordLength-1次躲查，因?yàn)閣ordLength長度的字符串才能符合要求，所以實(shí)際上的開始位置在wordLength位置上的時(shí)候译柏，就已經(jīng)在第一輪的滑動(dòng)窗口中比較過了镣煮。
最終的實(shí)現(xiàn)代碼如下，在leetcode上執(zhí)行用時(shí)：11ms鄙麦。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (words.length == 0) return result;
int wordLength = words[0].length(), maxWordLength = wordLength * words.length;
Map<String, Integer> wordMap = new HashMap<>();
for (String word : words) {
wordMap.put(word, wordMap.getOrDefault(word, 0) - 1);
}
Map<String, Integer> diffMap = new HashMap<>();
for (int i = 0; i < wordLength && i + maxWordLength <= s.length(); i++) {
diffMap.clear();
diffMap.putAll(wordMap);
for (int j = 0; i + (j + 1) * wordLength <= s.length(); j++) {
int startIndex = i + j * wordLength;
int endIndex = i + (j + 1) * wordLength;
if (j >= words.length) {
String firstWord = s.substring(startIndex - maxWordLength, endIndex - maxWordLength);
int value = diffMap.getOrDefault(firstWord, 0) - 1;
if (value == 0) {
diffMap.remove(firstWord);
} else {
diffMap.put(firstWord, value);
}
}
String nextWord = s.substring(startIndex, endIndex);
int value = diffMap.getOrDefault(nextWord, 0) + 1;
if (value != 0) {
diffMap.put(nextWord, value);
} else {
diffMap.remove(nextWord);
if (diffMap.isEmpty()) {
result.add(endIndex - maxWordLength);
}
}
}
}
return result;
}
}
可以看到相比于方法一典唇，速度提高了8倍】韪滑動(dòng)窗口往往可以和其他算法相互結(jié)合蚓聘，比如堆棧、隊(duì)列盟劫，根據(jù)實(shí)際的需要，可以幫助提高算的效率与纽。在利用哈希表來設(shè)計(jì)算的時(shí)候侣签，如果可以使用到滑動(dòng)窗口的話會(huì)非常的有用。
五急迂、直線上最多的點(diǎn)數(shù)
題目描述：
給你一個(gè)數(shù)組points影所，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一個(gè)點(diǎn)。求最多有多少個(gè)點(diǎn)在同一條直線上僚碎。[3]
看到這樣的描述猴娩，可以顯而易見的發(fā)現(xiàn)，這是一個(gè)二維平面坐標(biāo)，也就是可以使用二元一次函數(shù)來表示是卷中，也就是y=ax+b形式的函數(shù)矛双，其中的特例是x=c(c表示一個(gè)常數(shù))，二元一次方程都可以用上面的函數(shù)來表示蟆豫，用這樣的函數(shù)形式就可以表示X-Y平面上所有的直線了议忽。這樣的話就可以用兩個(gè)點(diǎn)來表示一條直線了，然后只需要判斷剩下的點(diǎn)是否在當(dāng)前這條直線上就可以了十减。那我們借此來構(gòu)建哈希函數(shù)栈幸，然后按照分桶算法來給點(diǎn)分組，然后計(jì)數(shù)帮辟，然后輸出其中最大的值即可速址。
分桶算法就是很直觀的一種哈希思想實(shí)現(xiàn)，按照關(guān)鍵詞由驹，把數(shù)據(jù)分成多組芍锚，然后對(duì)數(shù)組進(jìn)行處理，每個(gè)桶分別維護(hù)自己內(nèi)部的數(shù)據(jù)荔棉，然后管理每個(gè)桶就可以了闹炉。在本問題中因?yàn)閮牲c(diǎn)成一條直線，所以可以用[xi, yi]和[xi+1, yi+1]兩兩相減润樱，然后就可以按照y=ax+b來計(jì)算出a和b渣触，或者當(dāng)x坐標(biāo)都一樣的時(shí)候就可以按照x=c來計(jì)算出c，對(duì)于y=ax+b的形式壹若，首先按照a分成一組嗅钻，然后在這一組數(shù)據(jù)中再按照b再進(jìn)行一次劃分，細(xì)劃分出新的桶來店展，另外對(duì)于x=c的形式养篓，把c作為關(guān)鍵字劃分出數(shù)據(jù)來當(dāng)做一個(gè)桶。以a赂蕴、b柳弄、c作為哈希表的關(guān)鍵字分別計(jì)算，這樣的話就可以把數(shù)據(jù)分到一個(gè)個(gè)的桶中概说，然后再去計(jì)數(shù)有多少點(diǎn)是一條直接上的就可以了碧注。
以下是代碼實(shí)現(xiàn)，在leetcode上執(zhí)行用時(shí): 29ms糖赔。
class Solution {
public int maxPoints(int[][] points) {
if (points.length <= 2) return points.length;
int result = 0;
Map<Float, Map<Float, Set<int[]>>> map = new HashMap<>();
Map<Integer, Set<int[]>> xMap = new HashMap<>();
for (int i = 0; i < points.length - 1; i++) {
for (int f = i + 1; f < points.length; f++) {
float dx = (float) points[i][0] - points[f][0];
float dy = (float) points[i][1] - points[f][1];
float pi = dy / dx;
float b = points[i][1] - pi * points[i][0];
Set<int[]> value = null;
if (dx == 0) {
value = xMap.computeIfAbsent(points[i][0], k -> new HashSet<>());
}
if (value == null) {
Map<Float, Set<int[]>> bMap = map.computeIfAbsent(pi, k -> new HashMap<>());
value = bMap.computeIfAbsent(b, k -> new HashSet<>());
}
value.add(points[i]);
value.add(points[f]);
result = Math.max(value.size(), result);
}
}
return result;
}
}
總結(jié)
通過以上的了例子來講解說明萍丐，在實(shí)際中如何使用哈希表來設(shè)計(jì)高效的算法。在實(shí)際的操作做放典，關(guān)鍵字逝变、哈希表基茵、哈希函數(shù)，有很多種的設(shè)計(jì)方式壳影，按照自己的需要選擇合適的就可以了拱层。其中關(guān)于關(guān)鍵字函數(shù)的設(shè)計(jì)有很多種，比如直接尋址法态贤、平方取中法舱呻、折疊法、隨機(jī)數(shù)法等悠汽。在實(shí)際的查找過程中箱吕，還可以和其他的算法相互結(jié)合來優(yōu)化算法的效率，比如差分算法柿冲、分桶算法茬高、二叉樹、平衡樹假抄、鏈表怎栽、隊(duì)列、前綴和等等宿饱。在數(shù)據(jù)量較大的情況下熏瞄，尤其在現(xiàn)實(shí)的實(shí)際使用場景中，關(guān)鍵字沖突有可能頻繁地出現(xiàn)谬以，在沖突出現(xiàn)的時(shí)候强饮，可以使用二叉樹、紅黑樹为黎、隊(duì)列等等方式來保存數(shù)據(jù)邮丰，但是如果出現(xiàn)最差的情況，就可能出現(xiàn)關(guān)鍵字全部都一樣铭乾，導(dǎo)致所有的數(shù)據(jù)都堆積在一起剪廉，降低查詢的效率。這也是在工業(yè)上設(shè)計(jì)哈希函數(shù)的時(shí)候要注意的問題炕檩，要對(duì)極差情況斗蒋，攻擊者可以使用特定的方式，來讓哈希表出現(xiàn)最差的情況笛质，從而拖慢速度吹泡，從而發(fā)起攻擊。
如何設(shè)計(jì)合理的哈希函數(shù)经瓷，往往都是根據(jù)具體的情況來分析。但總的原則來說就是希望關(guān)鍵字盡量的唯一不會(huì)出現(xiàn)重復(fù)沖突洞难，還有就是盡量地讓數(shù)據(jù)保持平衡舆吮，把數(shù)據(jù)盡量的散列開來，不要讓某個(gè)或者某些關(guān)鍵字出現(xiàn)大量的數(shù)據(jù)堆積，從而拖慢速度色冀。在實(shí)際應(yīng)用中潭袱，哈希表往往是動(dòng)態(tài)擴(kuò)容的，當(dāng)裝填因子漸漸變大的時(shí)候锋恬，如何進(jìn)行動(dòng)態(tài)擴(kuò)容也是會(huì)在實(shí)際運(yùn)用中可能需要面對(duì)的問題屯换。一般地可以在裝填因子達(dá)到某個(gè)閾值之后，就去申請(qǐng)一個(gè)新的更大的哈希表來保存數(shù)據(jù)与学，然后把數(shù)據(jù)遷移過去彤悔。當(dāng)然也可以在裝填因子變得太小的時(shí)候，縮小哈希表索守，從而節(jié)省空間晕窑，但是否需要這么做，要根據(jù)具體的信息來決定卵佛，比如這種裝填因子是否只是短期內(nèi)的波動(dòng)杨赤，如果頻繁地更新哈希表，也會(huì)導(dǎo)致效率下降截汪，比如波峰可能只有一段時(shí)間內(nèi)疾牲，超過一段時(shí)間之后，就恢復(fù)成可接受的裝填因子了衙解。這些信息都可能會(huì)決定是否需要?jiǎng)討B(tài)縮表或者動(dòng)態(tài)擴(kuò)表阳柔。如果一次性的完成動(dòng)態(tài)縮表或者擴(kuò)表，就可能對(duì)當(dāng)前正在進(jìn)行的操作造成效率降低的問題丢郊】可以先申請(qǐng)新的哈希表，把新的數(shù)據(jù)寫入到新的哈希表中枫匾，然后分批把舊的數(shù)據(jù)寫入到新的哈希表來完成縮表或者擴(kuò)表架诞，對(duì)于這個(gè)時(shí)候的查詢和刪除來說，就需要先去在新的哈希表操作干茉，然后再去舊的哈希表操作谴忧，這樣既可以降低動(dòng)態(tài)改變哈希表的影響，也可以完成動(dòng)態(tài)改變哈希表角虫。所以操作的復(fù)雜度沾谓、時(shí)間復(fù)雜度、空間復(fù)雜度戳鹅，就需要做出權(quán)衡均驶，如果可以全部顧及那自然是最好的，否則就需要選擇一個(gè)對(duì)自己最好的選擇枫虏。
本文中只是講了比較簡單一些的例子妇穴，在實(shí)際運(yùn)用中爬虱，會(huì)比上面的例子管理的數(shù)據(jù)龐大得多，但是基本的哈希思想是不變的腾它，就是創(chuàng)建一個(gè)哈希表跑筝，然后來建立快速的查找關(guān)系，尤其在大量的數(shù)據(jù)面前瞒滴，是可以收獲到很好的效果的曲梗。比如安全加密、數(shù)據(jù)校驗(yàn)妓忍、LRU緩存淘汰算法虏两、word中的拼寫檢查等等，這些都會(huì)用到哈希思想单默。還有在大型系統(tǒng)中的負(fù)載均衡碘举，如何快速地管理系統(tǒng)中的服務(wù)器并找到對(duì)應(yīng)的IP地址，就可以建立一個(gè)哈希表來增刪改查從而達(dá)到負(fù)載均衡的目的搁廓。還有比如數(shù)據(jù)分片引颈，管理大型日志庫，如何查找日志庫中查詢頻率最高的關(guān)鍵字境蜕，如何判斷圖片是否在圖庫之中等等蝙场。還有分布式的存儲(chǔ)、布谷鳥哈希表等等粱年，這里不多做贅述售滤，這些的應(yīng)用都會(huì)很常見。合理使用哈希思想確實(shí)可以幫助我們有效地提高算法效率台诗。
參考文獻(xiàn)
[1] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein：算法導(dǎo)論[M].殷建平完箩，徐云，王剛拉队，劉曉光弊知，蘇明，鄒恒明粱快，王宏志.
機(jī)械工業(yè)出版社秩彤，2012-12
