【数据结构】哈希

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

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

哈希查找

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

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

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

哈希冲突

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

  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互质的整数。

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

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

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

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

//静态实现
#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:
    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;
}

猜你在找的数据结构相关文章

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test