{"id":61529,"date":"2024-10-13T11:46:38","date_gmt":"2024-10-13T03:46:38","guid":{"rendered":"https:\/\/server.hk\/cnblog\/61529\/"},"modified":"2024-10-13T11:46:38","modified_gmt":"2024-10-13T03:46:38","slug":"hash%e8%a1%a8%e3%80%81%e5%bf%ab%e6%8e%92%e8%88%87%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be%ef%bc%9a%e5%85%a9%e6%95%b8%e4%b9%8b%e5%92%8c","status":"publish","type":"post","link":"https:\/\/server.hk\/cnblog\/61529\/","title":{"rendered":"Hash\u8868\u3001\u5feb\u6392\u8207\u4e8c\u5206\u67e5\u627e\uff1a\u5169\u6578\u4e4b\u548c"},"content":{"rendered":"

Hash\u8868\u3001\u5feb\u6392\u8207\u4e8c\u5206\u67e5\u627e\uff1a\u5169\u6578\u4e4b\u548c<\/h1>\n

\u5728\u8a08\u7b97\u6a5f\u79d1\u5b78\u4e2d\uff0c\u6578\u64da\u7d50\u69cb\u548c\u7b97\u6cd5\u662f\u89e3\u6c7a\u554f\u984c\u7684\u57fa\u790e\u3002\u672c\u6587\u5c07\u63a2\u8a0e\u4e09\u500b\u91cd\u8981\u7684\u6982\u5ff5\uff1aHash\u8868\u3001\u5feb\u901f\u6392\u5e8f\uff08\u5feb\u6392\uff09\u548c\u4e8c\u5206\u67e5\u627e\uff0c\u4e26\u5c07\u5b83\u5011\u61c9\u7528\u65bc\u89e3\u6c7a\u300c\u5169\u6578\u4e4b\u548c\u300d\u7684\u554f\u984c\u3002<\/p>\n

Hash\u8868\u7684\u6982\u5ff5<\/h2>\n

Hash\u8868\u662f\u4e00\u7a2e\u4ee5\u9375\u503c\u5c0d\u5f62\u5f0f\u5b58\u5132\u6578\u64da\u7684\u6578\u64da\u7d50\u69cb\u3002\u5b83\u901a\u904e\u4e00\u500b\u54c8\u5e0c\u51fd\u6578\u5c07\u9375\u6620\u5c04\u5230\u8868\u4e2d\u7684\u4e00\u500b\u4f4d\u7f6e\uff0c\u5f9e\u800c\u5be6\u73fe\u5feb\u901f\u7684\u67e5\u627e\u3001\u63d2\u5165\u548c\u522a\u9664\u64cd\u4f5c\u3002Hash\u8868\u7684\u5e73\u5747\u6642\u9593\u8907\u96dc\u5ea6\u70baO(1)\uff0c\u9019\u4f7f\u5f97\u5b83\u5728\u8655\u7406\u5927\u91cf\u6578\u64da\u6642\u975e\u5e38\u9ad8\u6548\u3002<\/p>\n

Hash\u8868\u7684\u5be6\u73fe<\/h3>\n

\u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5be6\u73feHash\u8868\u7684\u7c21\u55ae\u7bc4\u4f8b\uff1a<\/p>\n

\nclass HashTable:\n    def __init__(self):\n        self.table = {}\n\n    def insert(self, key, value):\n        self.table[key] = value\n\n    def get(self, key):\n        return self.table.get(key, None)\n<\/code><\/pre>\n
\u5feb\u901f\u6392\u5e8f\uff08\u5feb\u6392\uff09<\/h2>\n
\u5feb\u901f\u6392\u5e8f\u662f\u4e00\u7a2e\u9ad8\u6548\u7684\u6392\u5e8f\u7b97\u6cd5\uff0c\u5e73\u5747\u6642\u9593\u8907\u96dc\u5ea6\u70baO(n log n)\u3002\u5b83\u7684\u57fa\u672c\u601d\u60f3\u662f\u9078\u64c7\u4e00\u500b\u300c\u6a1e\u8ef8\u300d\u5143\u7d20\uff0c\u5c07\u6578\u7d44\u5206\u70ba\u5169\u90e8\u5206\uff1a\u5c0f\u65bc\u6a1e\u8ef8\u7684\u5143\u7d20\u548c\u5927\u65bc\u6a1e\u8ef8\u7684\u5143\u7d20\uff0c\u7136\u5f8c\u5c0d\u9019\u5169\u90e8\u5206\u5206\u5225\u9032\u884c\u6392\u5e8f\u3002<\/p>\n
\u5feb\u6392\u7684\u5be6\u73fe<\/h3>\n
\u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5be6\u73fe\u5feb\u901f\u6392\u5e8f\u7684\u7bc4\u4f8b\uff1a<\/p>\n
\ndef quicksort(arr):\n    if len(arr) <= 1:\n        return arr\n    pivot = arr[len(arr) \/\/ 2]\n    left = [x for x in arr if x  pivot]\n    return quicksort(left) + middle + quicksort(right)\n<\/code><\/pre>\n
\u4e8c\u5206\u67e5\u627e<\/h2>\n
\u4e8c\u5206\u67e5\u627e\u662f\u4e00\u7a2e\u9ad8\u6548\u7684\u67e5\u627e\u7b97\u6cd5\uff0c\u9069\u7528\u65bc\u5df2\u6392\u5e8f\u7684\u6578\u7d44\u3002\u5b83\u7684\u57fa\u672c\u601d\u60f3\u662f\u5c07\u6578\u7d44\u5206\u70ba\u5169\u534a\uff0c\u7136\u5f8c\u6839\u64da\u4e2d\u9593\u5143\u7d20\u8207\u76ee\u6a19\u503c\u7684\u6bd4\u8f03\u7d50\u679c\u4f86\u6c7a\u5b9a\u67e5\u627e\u7684\u7bc4\u570d\u3002\u5176\u6642\u9593\u8907\u96dc\u5ea6\u70baO(log n)\u3002<\/p>\n
\u4e8c\u5206\u67e5\u627e\u7684\u5be6\u73fe<\/h3>\n
\u4ee5\u4e0b\u662f\u4f7f\u7528Python\u5be6\u73fe\u4e8c\u5206\u67e5\u627e\u7684\u7bc4\u4f8b\uff1a<\/p>\n
\ndef binary_search(arr, target):\n    low = 0\n    high = len(arr) - 1\n    while low <= high:\n        mid = (low + high) \/\/ 2\n        if arr[mid]  target:\n            high = mid - 1\n        else:\n            return mid\n    return -1\n<\/code><\/pre>\n
\u5169\u6578\u4e4b\u548c\u554f\u984c<\/h2>\n
\u300c\u5169\u6578\u4e4b\u548c\u300d\u554f\u984c\u662f\u6307\u5728\u4e00\u500b\u6574\u6578\u6578\u7d44\u4e2d\uff0c\u627e\u51fa\u5169\u500b\u6578\u5b57\uff0c\u4f7f\u5b83\u5011\u7684\u548c\u7b49\u65bc\u4e00\u500b\u7279\u5b9a\u7684\u76ee\u6a19\u503c\u3002\u9019\u500b\u554f\u984c\u53ef\u4ee5\u4f7f\u7528Hash\u8868\u3001\u5feb\u901f\u6392\u5e8f\u548c\u4e8c\u5206\u67e5\u627e\u4f86\u89e3\u6c7a\u3002<\/p>\n
\u4f7f\u7528Hash\u8868\u89e3\u6c7a\u5169\u6578\u4e4b\u548c<\/h3>\n
\u4f7f\u7528Hash\u8868\u7684\u89e3\u6cd5\u53ef\u4ee5\u5728O(n)\u7684\u6642\u9593\u5167\u627e\u5230\u89e3\uff1a<\/p>\n
\ndef two_sum_hash(nums, target):\n    hash_table = HashTable()\n    for i, num in enumerate(nums):\n        complement = target - num\n        if hash_table.get(complement) is not None:\n            return (hash_table.get(complement), i)\n        hash_table.insert(num, i)\n    return None\n<\/code><\/pre>\n
\u4f7f\u7528\u5feb\u6392\u548c\u4e8c\u5206\u67e5\u627e\u89e3\u6c7a\u5169\u6578\u4e4b\u548c<\/h3>\n
\u9996\u5148\u5c0d\u6578\u7d44\u9032\u884c\u6392\u5e8f\uff0c\u7136\u5f8c\u4f7f\u7528\u4e8c\u5206\u67e5\u627e\u4f86\u67e5\u627e\u76ee\u6a19\u503c\u7684\u88dc\u6578\uff1a<\/p>\n
\ndef two_sum_quick_binary(nums, target):\n    nums_sorted = quicksort(nums)\n    for i in range(len(nums_sorted)):\n        complement = target - nums_sorted[i]\n        if binary_search(nums_sorted, complement) != -1:\n            return (nums_sorted[i], complement)\n    return None\n<\/code><\/pre>\n
\u7e3d\u7d50<\/h2>\n
Hash\u8868\u3001\u5feb\u901f\u6392\u5e8f\u548c\u4e8c\u5206\u67e5\u627e\u662f\u89e3\u6c7a\u300c\u5169\u6578\u4e4b\u548c\u300d\u554f\u984c\u7684\u6709\u6548\u5de5\u5177\u3002Hash\u8868\u63d0\u4f9b\u4e86\u5feb\u901f\u7684\u67e5\u627e\u80fd\u529b\uff0c\u800c\u5feb\u901f\u6392\u5e8f\u548c\u4e8c\u5206\u67e5\u627e\u5247\u5728\u5df2\u6392\u5e8f\u6578\u7d44\u4e2d\u63d0\u4f9b\u4e86\u9ad8\u6548\u7684\u67e5\u627e\u65b9\u5f0f\u3002\u9019\u4e9b\u7b97\u6cd5\u548c\u6578\u64da\u7d50\u69cb\u5728\u8a08\u7b97\u6a5f\u79d1\u5b78\u4e2d\u5177\u6709\u91cd\u8981\u7684\u61c9\u7528\u50f9\u503c\u3002<\/p>\n
\u5982\u679c\u60a8\u5c0d\u65bc\u9ad8\u6548\u7684\u6578\u64da\u8655\u7406\u548c\u5b58\u5132\u6709\u8208\u8da3\uff0c\u8003\u616e\u4f7f\u7528\u9999\u6e2fVPS<\/a>\u4f86\u642d\u5efa\u60a8\u7684\u958b\u767c\u74b0\u5883\uff0c\u9032\u4e00\u6b65\u63a2\u7d22\u9019\u4e9b\u6280\u8853\u7684\u61c9\u7528\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u63a2\u7d22Hash\u8868\u3001\u5feb\u901f\u6392\u5e8f\u8207\u4e8c\u5206\u67e5\u627e\u5728\u89e3\u6c7a\u300c\u5169\u6578\u4e4b\u548c\u300d\u554f\u984c\u4e2d\u7684\u61c9\u7528\uff0c\u63d0\u5347\u7b97\u6cd5\u6548\u7387\u8207\u7de8\u7a0b\u6280\u5de7\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[101],"tags":[],"class_list":["post-61529","post","type-post","status-publish","format-standard","hentry","category-database"],"_links":{"self":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/61529","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/comments?post=61529"}],"version-history":[{"count":1,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/61529\/revisions"}],"predecessor-version":[{"id":61530,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/posts\/61529\/revisions\/61530"}],"wp:attachment":[{"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/media?parent=61529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/categories?post=61529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/server.hk\/cnblog\/wp-json\/wp\/v2\/tags?post=61529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}