使用哈希字符串进行快速文本数据处理

• 下载源代码 - 3.04 Kb

引言

字符串被认为是产生大量嵌套循环的原因。字符串的比较、搜索和排序被认为是耗时的操作。对文本数据进行索引是一个好的步骤，但是将搜索键设置为字符串会导致搜索算法性能下降。

在本文中，我们介绍了一种抽象字符串与哈希码的 ADT。比较将不再使用字节比较进行。字母表中的每个单词将被分配一个可逆的哈希码。

哈希函数

哈希函数旨在用单个代码表示一组数据。代码可能会重叠，因此好的哈希函数旨在最大限度地减少代码之间的重叠。使用哈希的系统还应管理溢出问题。我们在这里表示的可以称为哈希。但是，它是可逆的并且保证唯一性。实际上，它管理着文本数据的编号系统。

考虑单词“baby”，计算哈希码就像从二进制到十进制编号系统进行转换一样简单。在这种情况下，我们从第 26 个编号系统转换为十进制，其中 26 是英文字母的数量。

("baba")₂₆=0x26⁰+1x26¹+0x26²+1x26³=(17626)₁₀

("babb")₂₆=1x26⁰+1x26¹+0x26²+1x26³=(17627)₁₀

这意味着“baba”小于“babb”。比较是用数字完成的。不再需要嵌套循环进行比较。

hashedstring 类

class hashedstring

{

public:
    hashedstring():_pdata(0), _hashkey(0), _size(0){}
    hashedstring(const hashedstring& hstr):_pdata(strdup(hstr._pdata)), _
        hashkey(hstr._hashkey), _size(hstr._size){}
    hashedstring(const char* pdata):_pdata(strdup(pdata)), 
        _hashkey(0), _size(strlen(pdata))
    {
        _computehashkey();
    }
   
    hashedstring operator+(const hashedstring& s) const 
    {
        hashedstring rtn=*this;
        strcat(rtn._pdata, s._pdata);
        rtn._hashkey+=_hashkey*pow(26, s._size);
        rtn._size+=s._size;
        return rtn;
    }

 
    hashedstring operator+=(const hashedstring& s)
    { 
        strcat(_pdata, s._pdata);
        _hashkey=_hashkey*pow(26, s._size)+s._hashkey;
        _size+=s._size;
        return *this;
    }
    
    hashedstring operator=(const hashedstring& s) 
    {
        clear();
        _pdata=strdup(s._pdata);
        _hashkey+=s._hashkey;
        _size=s._size;
        return *this;
    }

 
    void clear()
    {
        if(_pdata)
            delete []_pdata;
        _pdata=0;
        _size=0;
        _hashkey=0;
    }

 
    ~hashedstring(){}
    
    operator const double() const {return _hashkey;}
    
    
protected:
    

    double _computehashkey()
    {
        unsigned int i=0;
        _hashkey=0;
        for(i=_size-1; i!=-1; i--)
            _hashkey+=(tolower(_pdata[i])-'a')*pow(26, _size-1-i);
        return _hashkey;
    }
    
    char* _pdata;
    double _hashkey;
    unsigned int _size;

};

结论

维护字母表编号系统可以提供更快的字符串处理。计算哈希码，一个离线过程，应该添加到巨大的文本数据的索引中。然后系统将享受快速的比较、搜索和排序例程。

    
    hashedstring s1("baby");
    hashedstring s2("babybaba");
    hashedstring s3("babybabb");
    
    vprint(s1);
    
    s1+="baba";
    
    vprint(s1);
    vprint(s2);
    vprint(s3);
    
    vprint(s1<s2);
    vprint(s2<s3);
    vprint(s2==s3);
    
    vprint(s1==s2);

结果

    s1= 17626
    s1= 8054676578
    s2= 8054676578
    s3= 8054676579
    s1<s2= 0
    s2<s3= 1
    s2==s3= 0
    s1==s2= 1