第9章：LeetCode--算法：HASH表

哈希表（Hash table，也叫散列表），关键值K和内容的映射表，通过映射函数实现，hashtable(key，value) 进行查询的时候，就是使用哈希函数将关键码key转换为对应的数组下标，并定位到该空间获取value, 设计好了是O(1)复杂度。

遇到冲突时，两个或多个Key对应同一个Hash算出来的地址，这时用：

开放地址法Closed-Hashing/Open Addressing：顺序下移坐标直到找到下一个空闲地址时插入(空间不足，无法插入时可以放入owerflow table里)https://www.jianshu.com/p/dbe7a1ea5928
链地址法Open-Hashing：不同key但是同一个地址，用链表把所有value串起来

英语名词
键(key)：又称为关键字。唯一的标示要存储的数据，可以是数据本身或者数据的一部分。
槽(slot/bucket)：哈希表中用于保存数据的一个单元，也就是数据真正存放的容器。
哈希函数(hash function)：将键(key)映射(map)到数据应该存放的槽(slot)所在位置的函数。
哈希冲突(hash collision)：哈希函数将两个不同的键映射到同一个索引的情况。
密码领域的哈希函数：MD4 MD5 SHA-1，平方取中位数法，取余数法

C++ SDL hash_map/set https://blog.csdn.net/yousss/article/details/79541543
C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和 set封装了二叉树等.C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树
>map, 红黑树需要O(log2N)次查找:

#include <map>

#include <string>

using namespace std;

...

map<string, string> namemap;

//增加。。。

namemap["岳不群"]="华山派掌门人，人称君子剑";

namemap["张三丰"]="武当掌门人，太极拳创始人";

namemap["东方不败"]="第一高手，葵花宝典";

...

//查找。。

if(namemap.find("岳不群") != namemap.end()){

...

}

>hash_map，一次查找O(1):

4.1 hash_map和map的区别在哪里？

构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。

4.2 什么时候需要用hash_map，什么时候需要用map?
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。

https://www.jianshu.com/p/de33dc676a3f

http://c.biancheng.net/stl/string/
https://blog.csdn.net/yousss/article/details/79541543

例子： https://www.cnblogs.com/inception6-lxc/p/9263964.html

巴特西

第9章：LeetCode--算法：HASH表

最新文章

热门文章