伟大的理论

哈希表(Hash Table):通过键 key 和一个映射函数 Hash(key) 计算出对应的值 value ,把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 哈希函数(Hash Function):将哈希表中元素的关键键值映射为元素存储位置的函数。 哈希冲突(Hash Collision):不同的关键字通过同一个哈希函数可能得到同一哈希地址。 哈希表的两个核心问题是:「哈希函数的构建」 和 「哈希冲突的解决方法」。

常用的哈希函数方法有:直接定址法、除留余数法、平方取中法、基数转换法、数字分析法、折叠法、随机数法、乘积法、点积法等。 常用的哈希冲突的解决方法有两种:开放地址法和链地址法。

伟大的用法

常用的哈希冲突解决方法主要是两类:「开放地址法(Open Addressing)」 和 「链地址法(Chaining)」。

开放地址法(Open Addressing):指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时,处理冲突时需要尝试另外的单元,直到找到空的单元为止。

链地址法(Chaining):将具有相同哈希地址的元素(或记录)存储在同一个线性链表中。

最伟大的代码

// STL 容器 映射 map 的基本用法 dict
    // 映射 key-value : 理解为 数组的 index-value 随机访问 O(1) 

    int arr[100]; // 常规数组 定义
    arr[1] = 10;  // 常规数组 元素赋值
    cout << arr[1] << endl; // 常规数组 元素访问

    map<string, int> mp;  //单重有序映射: 按 key 排序, key 不可重复 (nlogn) 
    multimap<string, int> mmp; //多重有序映射: 按 key 排序, key 可重复 (nlogn)
    unordered_map<string, int> ump; // 单重无序映射,key 不可重复 O(1) ,此类型最为常用
    unordered_multimap<string, int> ummp; // 多重无序映射:key 可重复 O(1) 

    hash["zhujiayi"] = 192; // map 和 unordered_map 可用 
    hash["zhujiayi"] = 692; // map 和 unordered_map 可用 
    hash["xianghuiquan"] = 685; // map 和 unordered_map 可用 

    cout << hash["shuxin"] << endl; // map 和 unordered_map 可用 
    cout << hash["xianghuiquan"] << endl; // map 和 unordered_map 可用 
    cout << hash["zhujiayi"] << endl; // map 和 unordered_map 可用 

    pair<string, int> pr("shuxin", 675); // 对组 
    hash.insert(pr); // 插入 
    hash.insert(make_pair("zhujiayi", 692));
    hash.insert(make_pair("zhujiayi", 192));
    hash.insert(make_pair("xiahuiquan", 685));
    hash.insert(make_pair("zhuzhu", 705));
    hash.erase("shuxin"); // 删除 

    cout << hash.size() << endl; // 返回元素总数

    for (pair<string, int> pr : hash) { // 哈希的遍历和访问
        cout << pr.first << " " << pr.second << endl; // first 对应 键 key, second 对应 值 value
    }
    cout << "=======" << endl;