哈希表¶

简介¶

哈希表又称散列表，是一种通用的数据结构，通过键值访问元素，一般一个键值只能对应一个元素。可以把哈希表理解成一种高级的数组，键值就是数组的下标，只是这个下标可以很大，甚至为其他类型。

哈希函数¶

哈希表当中最重要的就是哈希函数了。哈希表底层其实就是数组，但是我们可以通过哈希函数来将键值转化为数字。一个好的哈希函数可以更多地避免转化后的数字重复的情况。

对于最普通的键值为整数类型来考虑，首先我们需要将整数转化为非负整数，然后将其范围尽量缩小。这个操作可以使用模运算来完成。但是一般都是对一个较大的质数取模，这样子重复的概率才能尽可能地低。

对于其他的数据类型，我们则要考虑最合适的哈希函数。以下为一种整数的常见哈希函数：

int getHash(int x) {
  return (x % kMaxLength + kMaxLength) % kMaxLength;
}

取模之后相加再取模的原因是 C++ 的取模可能取出一个负数，这时候就需要相加在取模了。

冲突的处理¶

在哈希表的使用当中，一般都是一个键值对应一个哈希值的，这时候直接存到数组里面就可以了。但是，也有可能出现多个不同的键值对应了同一个哈希值，那么我们就需要进行特殊处理。

拉链法¶

也称开散列法，在每一个哈希值对应的地方都使用一个链表来进行存储，访问的时候就一个一个往后探查，直到找到对应键值为止。这是一段封装好的拉链法代码：

封装模板

const int kMaxLength = 1e6 + 7;

template <class Ty>
class Hash {
private:
  vector<pair<int, int>> vec[kMaxLength];

  int getHash(const int &x) {
    return (x % kMaxLength + kMaxLength) % kMaxLength;
  }

public:
  int &operator[](const int &x) {
    int key = getHash(x);
    for (auto &i : vec[key]) {
      if (i.first == x) {
        return i.second;
      }
    }
    vec[key].push_back(make_pair(x, 0));
    return vec[key].back().second;
  }
}

闭散列法¶

闭散列法就是直接存储在哈希表当中，如果发现了冲突就往后不停探查。代码略。

哈希表¶

简介¶

哈希函数¶

冲突的处理¶

拉链法¶

闭散列法¶

评论