数据结构与算法

数据结构

哈希表(Hash Table)

哈希表的大小一般为质数。

哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。

冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：

链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中。

开放地址法：当发现哈希值 hhh 处产生冲突时，根据某种策略，从 hhh 出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 h+1,h+2,h+3,…h+1,h+2,h+3,\ldotsh+1,h+2,h+3,… 这些整数对应的位置。

再哈希法：当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。

扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突

class MyHashSet {
private:
    vector<list<int>> data;
    static const int base = 769;
    static int hash(int key) {
        return key%base;
    }
public:
    MyHashSet(): data(base) {}
  
    void add(int key) {
        int h = hash(key);
        for(auto it = data[h].begin(); it != data[h].end(); it++){
            if(*(it) == key) return;    // 在链表中存在此数值
        }
        data[h].push_back(key);
    }
  
    void remove(int key) {
        int h = hash(key);
         for(auto it = data[h].begin(); it != data[h].end(); it++){
            if(*(it) == key){
                data[h].erase(it);
                return;
            }
         }
    }
  
    bool contains(int key) {
         int h = hash(key);
         for(auto it = data[h].begin(); it != data[h].end(); it++){
            if(*(it) == key){
                return true;
            }
         }
         return false;
    }
};

哈希映射(Hash Map)

和哈希表类似，只是哈希映射中存储的是键值对。通过key生成hash值。

class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key%base;
    }
public:
    MyHashMap(): data(base) {}
  
    void put(int key, int value) {
        int h = hash(key);

```cpp
class MyHashMap {
private:
    vector<list<pair<int, int>>> data;
    static const int base = 769;
    static int hash(int key) {
        return key%base;
    }
    
public:
    MyHashMap(): data(base) {

    }
    
    void put(int key, int value) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                (*it).second = value;
                return;
            }
        }
        data[h].push_back(make_pair(key, value));
    }
    
    int get(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                return (*it).second;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int h = hash(key);
        for (auto it = data[h].begin(); it != data[h].end(); it++) {
            if ((*it).first == key) {
                data[h].erase(it);
                return;
            }
        }
    }
};

哈希集合(Hash set)

集合(set)是一个有序的集合（不含重复值）通过红黑树实现。

Hash set是通过hash的方式存储的set，因此它是无序的