C++数据结构复习(一)一一hash散列容器

发表于 | 阅读次数

一道经典的LeetCode题

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

这里我们用的解法是用一个hash表，储存每一个数对应的下标
这大概是我第一次使用hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> mapping;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            mapping[nums[i]] = i;
        }
        for (int i = 0; i < nums.size(); i++) {
            const int gap = target - nums[i];
            if ( mapping[gap] > i) {
                result.push_back(i);
                result.push_back(mapping[gap]);
                break;
            }
        }
        return result;
    }
};

散列表的冲突处理

这里介绍一下我认为还是比较重要的冲突处理

闭散列法（开放定址法）

当插入元素的时候，一旦发生了散列冲突，就去寻找下一个空的散列地址供插入，而查找的时候逐个查找，直到碰到开放的地址查找失败。闭散列法是通过将冲突的元素以一定的模式存储在原散列的空间中。
之所以叫做闭散列法，就是因为冲突的元素没有开辟额外的存储空间，还是在原先hash表的空间范围之内。
　　(1). 线性探测法：将散列表看作是一个循环向量，若初始地址是f(key)=d，则依照顺序d、d+1、d+2…的顺序取查找，即f(key)=(f(key)+1)mod N;
　　(2). 二次探测法：基本思路和线性探测法一致，只是搜索的步长和方向更加的多样，会交替以两个方向，步长为搜索次数的平方来查找；
　　(3). 双重散列法：通常双重散列法是开放地址中最好的方法，其通过提供hash()和rehash()两个函数，前者产生冲突的时候，定制化后者rehash()重新寻址，其机制比前面两种固定格式的要灵活的多；
　　开放定址法一般用于冲突极少的情况，同时因为没有用到指针，所以对于数据的传输是友好的。

开散列法

　与前面闭散列法对应的开散列法，一般也叫作拉链法或者链地址法，通过将冲突的元素组织在链表中，采用链表遍历的方式查找。链地址法和上面的开放定址法最大的优势是解决方法直观，实现起来简单，尤其在删除元素的时候此处只是简单的链表操作，但是前面需要考虑后面可能有元素，处理会比较复杂。同事开散列法可以存储超过散列表容量个数的元素。
　　(1). 链地址法：相同散列值的记录放到同一个链表中，他们在同一个Bucket中；
SGI STL中hash table使用的是开链法进行的冲突处理。所以我们重点介绍一下：

他的结构图如下：

具体的实现我最近还会总结一下STL，有兴趣的也可以关注一下

　　(2). 公共溢出法：将所有的冲突都放到一个公共的溢出表中去，适用于冲突情况很小的时候。
　　除了使用传统的链表，还可以使用dynamic array的方式存储，分配的时候也可以预分配多个，以保证对CPU的缓存优化友好。

参考

taozj的博客