【数据结构】哈希

大佬教程收集整理的这篇文章主要介绍了【数据结构】哈希，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

　　我们经常会在一堆数据中搜索我们需要的数据元素，用于搜索的数据集合称为搜索结构。常见的查找方法有：从前往后依次遍历，二分查找，平衡二叉树，B树等。今天，我们看一种更高效的查找方法。

@H_197_2@

哈希查找

　　在线性表，二叉搜索树，AVL树等结构中，元素在存储结构中的位置与元素的关键码之间不存在直接的对应关系。我们知道在数据结构中搜索一个元素需要进行一系列的关键码比较，因此搜索的效率取决于搜索过程中比较的次数。如果我们可以不比较或者减少比较次数，那么效率就会大大提高了。

我们可以建立一个确定的函数关系：addr=Hash(key)

• 在插入时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放；
• 在搜索时，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功；
• 这种方式称之为散列方法，在散列方法中使用的转换函数叫着散列函数（哈希函数），构造出来的结构叫散列表，也可以称为哈希表。
• 对于两个数据元素的关键字，可能通过函数计算出一个相同的值，将这种现象称为哈希冲突或哈希碰撞。

@H_197_2@

哈希冲突

对于哈希冲突，我们肯定是要尽量减少的，因此哈希函数就至关重要了，我们要求哈希函数计算出来的地址能均匀分布在整个空间中，同时应该比较简单。常见的哈希函数方法：

1. 直接定址法：取关键字的某个线性函数为散列地址：Hash(key)=A*key+B，需要事先知道关键字的分布情况，适合查找比较小且连续的情况。
2. 除留余数法：Hash(key)=key%p，设哈希表地址中最大地址为m，这个p值应该是最近或等于m的质数。
3. 平方取中法：取将关键字平方后的中间三位数字作为散列地址。
4. 折叠法：将关键字从左到右分割成相等的几部分，然后叠加求和，并按散列列表表长，取后几位作为散列地址。
5. 随机数法：选择一个随机函数，取关键字的随机函数值为它的哈希地址。
6. 数学分析法。

虽然这些方法可以减少哈希冲突，但终究还是避免不了，因此，我们还是要选择好的解决冲突溢出的方法：
闭散列法：

1. 线性探查：如果产生冲突，依次查看其后的下一个位置，如果发现空位置插入新元素，这种方法的缺点是容易造成线性堆积。
2. 二次探查：在表中寻找下一个空位置的公式为：Hi=H0+2*i+1
3. 双散列法：使用双散列方法，需要两个散列函数。若设表的长度为m = TableSize，则在表中寻找下一个位置的公式为：j = H0 = Hash(key)，p = ReHash(key)； j = (j+p)%m; p是小于m且与m互质的整数。

不管使用哪种方法，当表中的元素较多的时候，就越容易发生冲突，因此，我们定义一个载荷因子：载荷因子=填入表中的元素个数/散列表的长度；当载荷因子达到一定数时，就需要对哈希表增大容量了。

开散列法：又叫链地址法，在这一篇博客中介绍。

闭散列：
- 在删除元素时，不能简单的置为空，需要改变成另一种状态，否则后面的元素可能会因为置成空而找不到；
- 插入的数据达到一定数量，需要增加容量，其时间成本较高；
- 有可能会造成空间浪费严重；
- 其实现简单，在一定条件下，利用完美的哈希函数，查找效率会很高

开散列：
- 使用了指针，删除数据时会比较方便，减少了内存损失；
- 动态分配节点，不会造成内存浪费；
- 查找时没有闭散列效率高。

@H_197_2@

//静态实现
#pragma once
#include <iostream>
using namespace std;

#define MAX_SIZE 10
typedef enum State { EXIST,deletE,EMPTY };
template <class K>
struct Elem
{
    K _key;
    State _state;
};

template <class K,bool IsLine = true>
class HashTable
{
public:
    HashTable()
        : _size(0)
    {
        for (size_t i = 0; i < MAX_SIZE; i++)
            _hashTable[i]._state = EMPTY;
    }

    bool Insert(const K& key)
    {
        if (_size * 10 / MAX_SIZE > 7)
            return false;

        size_t addr = HashFunc(key);
        size_t i = 1;
        while (_hashTable[addr]._state != EMPTY)
        {
            if (_hashTable[addr]._state == EXIST && key == _hashTable[addr]._key)
                return false;

            if (IsLinE)
                Linecheck(addr);//线性探测
            else
                Secondcheck(addr,i++);//二次探查
        }
        _hashTable[addr]._key = key;
        _hashTable[addr]._state = EXIST;
        _size++;
        return true;
    }

    bool delete(const K& key)
    {
        int ret = Find(key);
        if (ret == -1)
            return false;//不存在

        _size--;
        _hashTable[ret]._state = deletE;
        return true;
    }

    int Find(const K& key)
    {
        size_t addr = HashFunc(key);
        size_t i = 1;
        while (_hashTable[addr]._state != EMPTY)
        {
            if (_hashTable[addr]._state == EXIST && _hashTable[addr]._key == key)
                return addr;

            if (IsLinE)
                Linecheck(addr);
            else
                Secondcheck(addr,i++);
        }
        return -1;
    }

    size_t Size()const
    {
        return _size;
    }

    bool Empty()const
    {
        return 0 == _size;
    }
private:
    size_t HashFunc(const K& key)
    {
        return key % MAX_SIZE;
    }

    void Linecheck(size_t& addr)
    {
        ++addr;
        if (addr >= MAX_SIZE)
            addr = 0;
    }

    void Secondcheck(size_t& addr,size_t i)
    {
        addr = addr + ((i << 1) + 1);
        if (addr >= MAX_SIZE)
            addr %= MAX_SIZE;
    }
private:
    Elem<K> _hashTable[MAX_SIZE];
    size_t _size;
};

void test()
{
    int arr[] = { 12,22,33,9,29,55 };
    HashTable<int> ht;
    if (ht.Empty())
    {
        for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        {
            ht.Insert(arr[i]);
        }
        cout << ht.Size() << endl;
        ht.delete(22);
        ht.Insert(33);
        cout << ht.Size() << endl;
    }
}

上面的代码写的是一个静态的哈希表，用数组创建，它有以下三个缺陷：

1. 不能动态的增加元素
2. 字符串的增加和查找
3. 除留余数法素数的问题

这三个问题怎么解决呢？

• 第一个，我们可以改为动态的增加的开辟空间，当载荷因子达到0.7时，我们就扩大容量；
• 第二个，关于字符串转换成整型的算法有很多，感兴趣的同学可以在网上搜；
• 第三个，我们可以创建一个素数表，将常用的素数放入其中，通过函数获取素数。

以下是动态的代码实现：

#pragma once
#include <iostream>
#include <vector>
#include <String>
using namespace std;
// 获得素数
const int _PrimeSize = 28;
static const unsigned long _PrimeList[_PrimeSize] =
{
    53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul
};

size_t GetNextPrime(size_t num)
{
    for (size_t i = 0; i < _PrimeSize; i++)
    {
        if (_PrimeList[i]>num)
            return _PrimeList[i];
    }
    return _PrimeList[_PrimeSize - 1];
}

//字符串转整型
static size_t BKDRHash(const char * str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    size_t ret = (hash & 0x7FFFFFFF);
    return ret;
}

template <class K>
class KeyToIntDef
{
public:
    size_t operator()(const K& key)
    {
        return key;
    }
};
class StringToInt
{
public:
    size_t operator()(const String& key)
    {
        return BKDRHash(key.c_str());
    }
};

typedef enum State { EXIST,EMPTY };

template <class K>
struct Elem
{
    K _key;
    State _state;
};

template <class K,class KeyToInt,bool IsLine = true>
class HashTable
{
public:
    HashTable(size_t capacity = 4)
    {
        capacity = GetNextPrime(capacity);
        _hashTable.resize(capacity);

        for (size_t i = 0; i < capacity; i++)
            _hashTable[i]._state = EMPTY;
        _size = 0;
        _capacity = capacity;
    }

    bool Insert(const K& key)
    {
        checkCapacity();

        size_t addr = HashFunc(key);
        size_t i = 1;

        while (_hashTable[addr]._state != EMPTY)
        {
            if (_hashTable[addr]._key == key && _hashTable[addr]._state == EXIST)
                return false;

            if (IsLinE)
                Linecheck(addr);
            else
                Secondcheck(addr,i++);
        }
        _hashTable[addr]._state = EXIST;
        _hashTable[addr]._key = key;
        _size++;
        return true;
    }

    bool delete(const K& key)
    {
        int ret = Find(key);
        if (ret == -1)
            return false;//不存在

        _size--;
        _hashTable[ret]._state = deletE;
        return true;
    }

    int Find(const K& key)
    {
        size_t addr = HashFunc(key);
        size_t i = 1;
        while (_hashTable[addr]._state != EMPTY)
        {
            if (_hashTable[addr]._state == EXIST && _hashTable[addr]._key == key)
                return addr;

            if (IsLinE)
                Linecheck(addr);
            else
                Secondcheck(addr,i++);
        }
        return -1;
    }

    size_t Size()const
    {
        return _size;
    }

    bool Empty()const
    {
        return 0 == _size;
    }

    ~HashTable()
    {
        _hashTable.~vector();
        _size = 0;
        _capacity = 0;
    }
private:
    void checkCapacity()
    {
        if (_size * 10 / _capacity >= 7)
        {
            size_t newCapacity = GetNextPrime(_capacity);
            HashTable<K,KeyToInt> newHt(newCapacity);
            for (size_t i = 0; i < _capacity; i++)
            {
                if (_hashTable[i]._state == EXIST)
                    newHt.Insert(_hashTable[i]._key);
            }
            _capacity = newCapacity;
            Swap(newHt);
        }
    }

    void Swap(HashTable<K,KeyToInt>& ht)
    {
        swap(_hashTable,ht._hashTablE);
        swap(_capacity,ht._capacity);
        swap(_size,ht._sizE);
    }

    size_t HashFunc(const K& key)
    {
        return KeyToInt()(key) % _capacity;
    }

    void Linecheck(size_t& addr)
    {
        ++addr;
        if (addr >= _capacity)
            addr = 0;
    }

    void Secondcheck(size_t& addr,size_t i)
    {
        addr = addr + ((i << 1) + 1);
        if (addr >= _capacity)
            addr %= _capacity;
    }
private:
    @H_206_616@vector<Elem<K>> _hashTable;
    size_t _size;
    size_t _capacity;
};

void test()
{
    HashTable<String,StringToInt> ht1;
    ht1.Insert("111");
    ht1.Insert("222");
    ht1.Insert("333");
    ht1.Insert("abc");
    ht1.Insert("你好");
    cout << ht1.Size() << endl;

    if (ht1.Find("111") != -1)
        cout << "找到了" << endl;
    else
        cout << "没有找到" << endl;
    ht1.delete("333");
    cout << ht1.Size() << endl;
}

大佬总结

以上是大佬教程为你收集整理的【数据结构】哈希全部内容，希望文章能够帮你解决【数据结构】哈希所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。