哈希表的数据结构与实现详解

哈希表的数据结构与实现详解 | 极客日志

除法散列法又名除留余数法，顾名思义，假如哈希表的大小为 M，那么通过 Key 除以 M 的余数作为余数来作为映射位置的下标，也就可得哈希函数：h(Key)=Key%M。

当我们使用除法散列法时，要尽量避免 M 为某些值，如 2 的幂，10 的幂等（如果我们大家在这里认真地去发现的话，不难会发现 Key%2^x，本质上就相当于保留 Key 的后 x 位（2 进制），如果后 x 位一样的值，由此计算出来的哈希值就是一模一样的了），这样会造成冲突。比如：63 和 31 这两个值，假如 M 是 16（2^4，保留二进制的后 4 位），那么这样的话，计算出来的哈希值均为 15，63 的二进制后 8 位是 00111111（二进制 1111 的十进制是 15），31 的二进制后 8 位是 00011111。如果是 10^x 的话，结果那就会更明显了，保留的都是十进制的后 x 位，如：112 和 12312 这两个值，假如 M 为 10^2，那么计算出来的哈希值均为 12。

当使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个质数。

需要说明的是，除留余数法在实践中也是八仙过海，各显神通，Java 的 HashMap 采用除法散列法时就是用 2 的整数次幂去做的哈希表的大小 M 的，这样玩的话，它并没有像我们上述所讲的那样，采用取模运算，而是直接采用位运算的方法，位运算相当于取模运算来说效率会显得更高一些。但它不是单纯地去取哪几位，比如 M 是 2^16，本质上最终得到的是数字二进制的后 16 位，但是通过我们前面所讲解过的知识可知，这样是不行的，Java 自然也知道这一点，因此为了避免这种情况，它没有将二进制的后 16 位作为哈希表，而是又求了 Key 的前 16 位，然后将这两个值进行异或操作，最后将这个异或的结果作为了哈希值。

也就是说这里打破了那个最后几位相同的不足，我们映射出来的值还是在 [0, 2^16] 范围之内，但是这里尽量要让 Key 所有的位都参与运算，这样映射出来的哈希值就会显得更均匀一些，我们上面建议 M 取不太接近 2 的整数次幂的一个质数的理论是大多数的数据结构的书籍中写的理论，但在实践中，灵活运用，抓住本质。

OK，回到我们这里的 C++ 中来，我们上面是采用这个除法散列法去作为哈希函数的，通过前面方法的实现步骤我们可以得知，不同的值是极有可能映射到表中的同一个位置的，但是，我们一个位置上只能存储一个数据，这就引发了哈希冲突，目前为止，有 2 种解决方法，这个我们稍后再讲，这里先将哈希函数这一部分讲完。（后面的三种方法以及刚刚讲解的这种方法我们只需简单了解一下即可，不要求大家重点掌握）

enum State//写一个枚举来标记空间中存储值的状态。
{
    EXIST,//这个位置有值，也就是这个位置已经有数据了。
    EMPTY,//这个位置没有元素。
    DELETE//这个位置原来是有元素存在的，被删除了，因此，这个位置就没有元素了。
};

template<class K,class V>//这里用模板，因为我们前面讲过 unordered_set 和 unordered_map 的使用，它们两个的底层用的就是哈希表，因此存放数据的那个变量我们这里暂时使用成 pair 类类型的变量。
struct HashData 
{
    pair<K, V> _kv;
    State _state = EMPTY;//建立好一块空间后，它的内部是没有存储我们想要的那个数据的，因此默认为空 (EMPTY)
    HashData(const pair<K, V>& kv) :_kv(kv) { }
};

template<class K>//我们这个仿函数的作用是将 Key 转化成整数类型，而通过我们前面的学习，我们得知这个 Key 有很多种类型的可能，因此这里使用模板。
struct HashFunc 
{
    size_t operator()(const K& key) 
    {
        return (size_t)key;//直接将其转化成整数类型，这里我们只是进行模拟实现的操作，不需要实现的就和库中的一模一样，因此这里我们就简单点，一笔带过就好了。
    }
};
//string 做 Key 的场景我们是比较常见的，因此，我们在这里考虑把 string 给特化一下。
template<>
struct HashFunc<string>//当我们将 HashFunc 当作第三个模板参数给哈希表，若 string 作为 Key 传过来并且调用这个仿函数进行整形转换操作时，调用的不是上面的那个 operator()，而是接下来的这个 operator()。
{
    size_t operator()(const string& key) 
    {
        //字符串转换成整形操作，我们这里有多种方法可以选择，如：可以将这个字符串的各个字符的 ascii 码相加起来，但是直接相加的话，类似"abcd"和"bcda"这样的字符串计算出的整数值是相同的，这里我们可以使用 BKDR(计算机领域的一位大佬) 哈希的思路，用上一次计算所得的结果去乘以一个质数，这个质数一般取 31，131 等效果会比较更好 (这里我们取 131 作为那个质数)。
        size_t amount = 0;
        for (auto ch : key) 
        {
            amount *= 131;
            amount += ch;
        }
        return amount;
    }
};

template<class K,class V,class Hash=HashFunc<K>,class KeyOfT,class Pred=equal_to<K>,class Alloc=allocator<K>>
class HashTable 
{
public:
    HashTable() 
    {
        //通过我们前面所讲述过的知识可以得知，在使用哈希表时，我们是要将一个个数据全部存放到哈希表中，既然是存放，那么就得有空间，因此我们在刚刚建好一个哈希表的对象后，就要立马创建好相应的空间出来，因此我们在构造函数中要写一个开创空间的步骤。
        _tables.resize(__stl_next_prime(_tables.size() + 1));//开创一个质数大小的空间，从质数表中去取要开创空间的大小，用 resize 函数去开创，至于为什么要传"size()+1"而不是"size()"我们后面会讲到。
    }
private:
    vector<HashData<K, V>> _tables;//哈希表的各个操作都是基于底层封装的那个顺序表实现的。
    size_t _n = 0;//记录存储的数据个数。
};

bool Insert(const pair<K, V>& kv)//这里我们要插入一个 HashData 类型的元素，按照道理来说，Insert 这个函数的参数应该是一个 HashData 类型的引用才对，但是我们这里的参数却是一个 pair 类型的变量，有些同学在这里会有一些疑惑，这时为什么呢？这个问题其实和我们的空间开创有关，通过我们上述的代码实现可以得知，在哈希表的实现中，我们无论是空间的开创还是对原有空间的扩容操作，我们这里都是使用 resize 这个函数在这里进行操作的，而 resize 函数的功能是将数据的个数扩大到 n 个 (n 是传过去的一个整数类型的数据，如果忘了的话可以参考前面的在章节中对 resize 这个函数的讲解)，也就是说，我们开创了一个哈希表类型的对象后，编译器不仅仅是开创了相应大小的空间，每个空间中均是存放了一个 HashData 类类型的对象作为元素，既然如此的话我们也就完全没有必要再创建一个 HashData 类类型的对象了，而是创建一个 pair 类类型的对象，将原有空间中所存储的那个 HashData 对象中的那个 pair 类类型的变量替换成我们传过来的这个 pair 类类型的对象即可。
{
    if (Find(kv.first))//我们这里实现的这个哈希表是作为 unordered_set 和 unordered_map 这两个容器的底层的，通过我们前面的学习可知，unordered_set 和 unordered_map 这两个容器是不支持重复的，因此，我们再这里要先检查一下关键字是否在该关键字，若存在的话，则说明接下来要插入的这个元素是存放的，已经存在了，不能插入到哈希表中，若不存在，则可以插入到哈希表中去。
    {
        return false;//插入失败。
    }
    //按照我们前面的思路来说，接下来的操作就该开始插入操作了，实际上在找映射的位置之前我们还需要干一件事，就是判断一下负载因子是否大于 0.7，如果分析负载因子大于 0.7 的话，就需要进行扩容操作。
    if (_n * 10 / _tables.size() >= 7)//计算一下该哈希表的负载因子是否小于 0.7，_n 是哈希表中存储的数据的个数。注：这里我们的_n 不可以除以哈希表的空间大小，只能除以 size()，借助下面第一幅图来解释一下：我们哈希表的底层结构是封装了一个 vector 类类型的对象，因此哈希表在访问元素时也是用 operator[] 去访问的，而我们前面在讲 vector 中的 operator[] 这个函数接口时，讲过说这个函数接口会判断要访问的元素下标是否是在 size() 之内，如果在的话，才会进行访问，反之，则会报错，也就是说，我们插入一个元素的范围是<size()，元素不可以插在 size() 和 capacity() 之间的空间中去，否则在调用 operator[] 成员函数时会报错 (这里我们可以不用怎么在意这个，因为我们前面在哈希表中开空间时用的是 resize() 函数去开创的，每次开创过后的 size() 和 capacity() 基本都是相同的)。
    {
        //开创空间，到质数表中去找比当前的空间大的下一个质数。
        //我们这里是对底层的那个顺序表进行扩容，我们这里的扩容和我们前面实现的传统扩容操作并不相同，不能在原来的那个顺序表中实现扩容操作，我们前面所讲过的哈希表的元素插入时是这个元素的整数形式最终映射到顺序表中的相应位置 (下标位置)，也就是说，在元素相同的情况下，哈希表的大小不同，相应的，映射到的位置不同，基于此原因，如果我们在原顺序表中进行扩容的话，后续在调整各个元素位置时，就容易出现数据丢失的情况，因此，我们这里选择再开创一个顺序表，该顺序表的大小就是扩容后的大小。
        vector<HashData<K, V>> newtables(__stl_next_prime(_tables.size() + 1));//接下来要进行的操作就是讲原顺序表中的元素全部都重新映射到刚刚新开创的这个顺序表中。
        for (auto& data : _tables) 
        {
            //通过我们前面对哈希表存储的元素方式的了解及其使用，我们可以了解到哈希表中的元素存储时并不是以一个接一个的方式去存储的，也就是说我们再获取空间中的元素时还需要去判断一下该空间中是否含有元素。
            if (data._state == EXIST) 
            {
                size_t hash0 = data._kv.first % newtables.size();//找到新空间中映射的位置。
                //通过我们前面的讲解可知，我们这里是用线性探测的方法去实现插入元素的，而我们这里所写的这个"移动"元素的操作不就相当于是往扩容后的新空间中去插入元素吗？因此，我们这里也使用线性探测的方法。
                while (_tables[hash0]._state == EXIST)//通过我们前面对线性探测的分析可知，既有可能会出现哈希冲突的这一情况，解决办法是依次往后去寻找空位置，而发生传统的原因就是因为这个元素映射的位置被别的元素给占据了，依次，我们这里选择借助循环来找到当前元素应该存储的位置，如果这个位置的_state 是 EXIST 的话，则说明当前这个位置已经被其它的元素给占据了，就需要我们继续往后去找合适的位置了。
                {
                    hash0++;
                    hash0 %= _tables.size();//为了防止当 hash0>=_tables.size() 这种情况，hash0 就是我们查找空间的下标，当 hash0 到哈希表的最后一个空间的位置时，那么它下一个要到的空间的位置就一个是该哈希表的第一个空间的位置，也就是从下标为 0 的位置依次往后走，"%"一下，就足可保证 hash0 绝对是在 [0,_tables.size()-1]; 这个范围之间活动的。
                }//除了循环的话，就说明找到空位置了，找到了合适的位置之后，下一步就是将数据放到里面了。
                newtables[hash0] = data;
                newtables[hash0]._state = EXIST;//更新该空间的_state 为 EXIST，说明该空间已经有元素了。
            }//除了这个 if 语句后，就说明"移动"好一个元素了，继续进行范围 for 的遍历操作，直到将原数组中的所有元素全部都"移动"到新的数组中。
        }//当编译器执行语句出了这个范围 for 之后，就说明我们这里已经将原数组中的所有元素全部"移动"到了新的数组中去了，程序到这里其实还没完，我们这里进行的这个扩容操作的目的是将原哈希表中的那个数组空间 (顺序表) 给扩大；但是我们前面的一系列操作是额外开创了一块扩容后的空间大小的顺序表，也就是说，"移动"完所有的元素后，哈希表中的那个数组还是没有变化，因此我们接下来要将哈希表中的那个顺序表换成我们前面开创的那个大小为扩容后的大小的顺序表，只需交换一下两个顺序表的指针即可。
        _tables.swap(newtables);//直接调用 vector 库中的那个 swap 所有函数即可，可以大幅度地提高运行效率。
    }//以上所有操作均是与扩容操作相关地，作用就是判断是否需要扩容......;我们的这个成员函数的目的其实是往哈希表中要插入一个元素，也就是说，上述的所有操作并不是我们实现的插入的核心代码，接下来的才是：
    size_t hash0 = kv.first % _tables.size();//求出当前这个元素在哈希表中被映射的位置。
    while (_tables[hash0]._state == EXIST)//解释和前面相同。
    {
        hash0++;
        hash0 %= _tables.size();
    }//说明已经找到了要存储的位置了。
    _tables[hash0]._kv = kv;
    _tables[hash0]._state = EXIST;
    ++_n;//插入一个元素后，数据个数就会增加 1。
    return true;//插入成功。
}

if (_n * 10 / _tables.size() >= 7)//扩容 (现代写法)
{
    HashTable<K, V> newht;//再开创一个新的哈希表。
    newht._tables.resize(__stl_next_prime(_tables.size() + 1));//将新开创的这个哈希表类型的对象的空间个数用 resize() 函数扩容，扩容后该哈希表的大小就是我们想要的大小。
    //接下来，就是将原哈希表中所有的元素全部"移动"到刚刚开创的 newht 这个哈希表中去，这里我们仍然将其看成是插入到 newht 这个哈希表中。
    for (auto& data : _tables) 
    {
        if (data._state == EXIST) 
        {
            newht.Insert(data._kv);
        }
    }
    _tables.swap(newht._tables);
}

HashData<K, V>* Find(const K& key) 
{
    //我们这里在实现哈希表的这些操作时，我们是使用线性探测提供的那个哈希函数的，在前面我们讲过，整个哈希函数的实现中只能使用同一个哈希函数去实现，因此我们这里在查找某一个元素的时候，也使用线性探测的方法去查找。
    size_t hashi = key % _tables.size();//首先找到关键字为 key 的这个元素映射在哈希表中的位置 hashi，通过我们前面的讲解可以得知线性探测难免会发生哈希冲突，这样的话，就会占据别人的位置，也就是说，我们此时所求出来的那个映射的位置有可能并不是关键字为 key 的这个元素真正的存储位置，因此，我们这里从映射的这个位置开始依次往后去找，根据我们前面所讲过的知识可知，当两个不同的元素若映射到同一个位置时，那么它们实际的存储位置之间必然是没有空位置的 (不包括_state 为 DELETE 的位置)，因此可以根据这个条件去写循环。
    while (_tables[hashi]._state != EMPTY) 
    {
        if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key)//若满足 if 语句中的条件，则说明找到了，返回这块空间的地址即可。
        {
            return &_tables[hashi];
        }//没进入 if 语句里面的话，则说明没找到，则要继续线性往后去找。
        hashi++;
        hashi %= _tables.size();//我们在查找的过程中必须始终要保证查找的那个位置 (hashi) 不能越过哈希表的大小，同时，若 hashi 查找到了哈希表的最后一个位置的话，那么下一个查找的位置就要是下标为 0 的这个位置。
    }//若出了 while 循环的话，则说明整个哈希表中没有关键字为 key 的这个元素，查找失败。
    return nullptr;
}

bool Erase(const K& key) 
{
    //我们这里实现的是删除元素的操作，既然是要删除，那么首先我们得要找到这个元素才行。
    HashData<K, V>* ret = Find(key);
    if (ret == nullptr)//ret 若为空，则说明要删除的这个元素不存在。
    {
        return false;
    }
    else 
    {
        ret->_state = DELETE;//将这块空间的状态改为 DELETE，就说明这块空间中的元素被删除掉了，已经没有值了，可以存储其它元素。
        return true;
    }
}

template<class K,class V>
class HashNode 
{
public:
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv) :_kv(kv),_next(nullptr) { }
};

template<class K, class V, class Hash = HashFunc<K>, class KeyOfT, class Pred = equal_to<K>, class Alloc = allocator<K>>
class HashTable 
{
public:
    typedef HashNode<K, V> Node;
    HashTable() 
    {
        _tables.resize(__stl_next_prime(_table.size() + 1), nullptr);
    }
private:
    vector<HashNode<K, V>*> _tables;//指针数组。
    size_t _n = 0;//哈希表中存储的数据个数。
};

bool Insert(const pair<K, V>& kv) 
{
    if (Find(kv.first))//解析与前面的相同。
    {
        return false;
    }
    size_t hashi = kv.first % _tables.size();//通过我们前面的讲解可知，我们链地址法是将元素元素到某一个位置上，哪怕要映射的位置是相同的，因此，我们首先要求出该元素被映射的位置。
    //我们这个链地址法这里也需要考虑扩容的问题，对于链地址这个方法，库中是当负载因子大于 1 时，才进行扩容操作，我们这里为保持一致，就选择当负载因子为 1 时，我们就开始进行扩容操作。
    if (_n / _tables.size() == 1)//开始扩容
    {
        //对于我们这里接下来要进行的这个扩容操作，相信大多数的小伙伴第一时间想到的是传统的扩容方法，毕竟它比较容易想到，既然这个传统方法大家都能想得到的话，我们就不在这里浪费时间再去写了，我们这里直接就用现代写法去写了，如果这里大家要用传统的写法去试一试的话，有一个东西大家在这里注意一下，就是销毁掉旧单链表时的那个销毁的过程是需要我们自己单独去首先的，因为_tables 里面存放的指针类型，按照我们之前所学的知识来说，编译器去销毁 vector 类类型的对象时，先自动调用 vector 的析构函数，vector 的构造函数会自动去调用 vector 中所存储的元素的析构函数，在我们这里，_tables 中存储的是指针，指针没有析构，因此这里编译在自动销毁旧单链表时，只会调用 vector 的构造函数，不会调用各个元素节点的析构函数，这样显然时不行的，久而久之，会出现一些风险，我们这里在最后需要利用 for 循环一步步将各个元素节点给释放掉如果用传统方法去实现的话。
        HashTables<K, V> newht;
        newht._tables.resize(__stl_next_prime(_tables.size() + 1));
        for (size_t i = 0; i < _tables.size(); i++)//利用 for 循环来找到每一个元素，找到这个元素之后，将其新插入到刚刚开创的新哈希表 newht 中去。
        {
            Node* cur = _tables[i];
            while (cur)//如果 cur 为空，则说明哈希表中下标为 i 的这个位置上所有的元素全部都遍历完了。
            {
                newht.Insert(cur->_kv);//将遍历到的这个元素给重新插入到 newht 中去。
                cur = cur->_next;//cur 进行往下走。
            }
        }//当我们出了 for 循环之后，就说明我们这里将原单链表中所有的元素全部都遍历完了。
        _tables.swap(newht._tables);
    }//上述操作知识扩容操作，并不是我们这里插入元素的操作，接下来，才真正是实现插入元素的操作。
    //通过我们前面对链地址法的一个演示可知，我们映射到某一个位置上时，是头插到前面，就像前面的演示中，30 这个元素插入到哈希表中，30 所映射到的位置下面原来已经链接上了一个节点 (96) 了，我们是将 30 这个元素插入到 96 这个元素的前面，并不是插入到 96 这个元素的下面，我们这里之所以选择头插，因为头插的效率是最高的，如果我们选择插入到 96 后面的话，还需要借助循环去找到相应的位置，如果某个桶特别长的话，那么循环也是需要耗费大量的时间的。
    Node* newnode = new Node(kv);//创建一个新节点，这个新节点存放要插入的这个元素。
    newnode->_next = _tables[hashi];
    _tables[hashi] = newnode;
    ++_n;
    return true;
}

if (_n / _tables.size() == 1)
{
    vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
    for (size_t i = 0; i < _tables.size(); i++)
    {
        Node* cur = _tables[i];
        while (cur)
        {
            Node* next = cur->_next;//通过我们上述的讲解可知，我们这里是要将旧表中所有的元素全部重新链接到新表中，我们这里采用的方法是直接移动旧表中的节点到新表中去，我们都知道，旧表中在同一个映射位置的所有元素在新表中的映射位置可能有所不同，也就是说，当我们链接好一个旧表中的一个元素之后，我们接下来要去链接这个位置的下一个元素，因此，我们这里需要重新定义一个指针去指向下一个要映射到新表中的元素。
            size_t hashi = cur->_kv.first % _tables.size();//找到这个元素在新表中被映射的位置。
            cur->_next = newtables[hashi];
            newtables[hashi] = cur;
            cur = next;//cur 指针指向的是要移动到新表中的节点。
        }//出了循环之后，就说明旧表中下标为 i 的这个位置中的所有映射全部都移动完了，由于旧表中存放的都是指针，因此最后将其置空，保持一个好习惯。
        _tables[i] = nullptr;
    }
    _tables.swap(newtables);
}

Node* Find(const K& key) 
{
    size_t hashi = key % _tables.size();//找到关键字为 key 的这个元素在表中映射的位置。
    Node* cur = _tables[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)///找到了那个关键字为 key 的元素。
        {
            return cur;
        }
        else
        {
            cur = cur->_next;
        }
    }
    return nullptr;//没找到。
}

bool Erase(const K& key) 
{
    //我们这里的操作是删除一个元素，既然是要删除元素，那么首先我们要找到这个元素，按照我们前面的惯例，我们这里完全可以通过 Find 函数去找到这个元素的位置，但是基于我们这里的链地址法的特点，我们这里是不可以用 Find 函数去找到关键字为 key 的元素，我们的链地址法中的每一个节点之间均是通过指针链家起来的，如果要删除某一个节点，就要该元素后面的所有节点全部都要重新接到该元素前面的那个接到后面，因此，我们还需要有一个指针去指向要删除的这个节点，而 Find 函数去找相应的节点。
    size_t hashi = key % _tables.size();
    Node* prev = nullptr;
    Node* cur = _tables[hashi];
    while (cur)
    {
        if (cur->_kv.first == key)
        {
            //_tables 这个数组是一个指针数组，也就是说，_tables 的每一个节点位置上存放的都是节点的地址。这里我们就要分情况考虑了。
            if (prev == nullptr)
            {
                //如果满足这个条件的话，就说明下标为 hashi 的这个位置上的第一个就是我们要找的元素，按照我们前面所讲的规则以及指针数组的性质来看的话，我们这里可以让下标为 hashi 这个位置的第二个元素成为第一个元素即可。
                _tables[hashi] = cur->_next;
            }
            else//说明 cur 指向的这个当前这个节点是中间的某个节点，让该节点后面的所有节点全部都接到 prev 节点的后面。
            {
                prev->_next = cur->_next;
            }
            delete cur;
            --_n;
            return true;
        }
        prev = cur;
        cur = cur->_next;
    }
    return false;
}

inline unsigned long __stl_next_prime(unsigned long n) 
{
    static const int __stl_num_primes = 28;
    static const unsigned long __stl_prime_list[__stl_num_primes] = 
    {
        53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291
    };
    const unsigned long* first = __stl_prime_list;
    const unsigned long* last = __stl_prime_list + __stl_num_primes;
    const unsigned long* pos = lower_bound(first, last, n);
    return pos == last ? *(last - 1) : *pos;
}

哈希表的数据结构与实现详解

1 哈希概念

1.1 直接定址法

1.2 哈希冲突

1.3 负载因子

1.4 将关键字转成整数

1.5 哈希函数

1.5.1 除法散列法 / 除留余数法

1.5.2 乘法散列法

1.5.3 全域散列法

1.5.4 其他方法

1.6 处理哈希冲突

1.6.1 开放地址法

1.6.1.1 线性探测

1.6.1.2 二次探测

1.6.2 代码实现开放地址法

1.6.2.1 扩容操作

1.6.2.2 Key 不能取模的问题

1.6.2.3 插入一个数据

1.6.2.4 查找一个数据

1.6.2.5 删除一个元素

1.6.3 链地址法

1.6.3.1 解决冲突的思路

1.6.3.2 扩容

1.6.3.3 极端场景

1.6.3.4 插入一个元素

1.6.3.5 查找一个元素

1.6.3.6 删除一个元素

1.6.4 质数表

更多推荐文章

相关免费在线工具

哈希表的数据结构与实现详解

1 哈希概念

1.1 直接定址法

1.2 哈希冲突

1.3 负载因子

1.4 将关键字转成整数

1.5 哈希函数

1.5.1 除法散列法 / 除留余数法

1.5.2 乘法散列法

1.5.3 全域散列法

1.5.4 其他方法

1.6 处理哈希冲突

1.6.1 开放地址法

1.6.1.1 线性探测

1.6.1.2 二次探测

1.6.2 代码实现开放地址法

1.6.2.1 扩容操作

1.6.2.2 Key 不能取模的问题

1.6.2.3 插入一个数据

1.6.2.4 查找一个数据

1.6.2.5 删除一个元素

1.6.3 链地址法

1.6.3.1 解决冲突的思路

1.6.3.2 扩容

1.6.3.3 极端场景

1.6.3.4 插入一个元素

1.6.3.5 查找一个元素

1.6.3.6 删除一个元素

1.6.4 质数表

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具