字符串哈希原理及相关技术

一、字符串哈希值

字符串哈希可以将字符串映射成唯一的哈希值，哈希值可以用于字符串的快速查找、去重等操作。字符串哈希值的计算可以采用不同的算法，常见的有BKDR哈希、DJB哈希、AP哈希等，这些哈希算法都能够将一个字符串转化为一个整数。

unsigned int BKDRHash(char *str)
{
    unsigned int hash = 0;
    unsigned int seed = 131; // 31, 131, 1313, 13131, 131313, ...
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

上面是BKDR哈希的简单实现，seed值可以根据实际应用场景来选择。

二、字符串哈希值映射到数组下标

字符串的哈希值通常是一个比较大的整数，如何将哈希值映射到数组下标呢？通常采用的方法是将哈希值取模操作，即 hash % M，其中 M 通常是一个素数，这样可以有效减小哈希冲突的概率。

三、字符串哈希算法

字符串哈希算法是将一个字符串转化为哈希值的过程，常用的算法有BKDR哈希、DJB哈希、AP哈希等，每种算法的单次哈希时间和哈希冲突率不同，选择合适的算法需要考虑实际应用场景的需要。

四、字符串哈希冲突

哈希冲突是指不同的键值或数据在哈希表中映射到相同的位置的情况。哈希冲突可能导致重复数据的插入，甚至引起哈希表崩溃。解决哈希冲突的方法包括开放寻址法和链表法，其中链表法是比较常用的解决哈希冲突的方法。

五、字符串哈希和kmp

KMP算法是一种常用的字符串匹配算法，它的匹配时间复杂度为O(n+m)，其中n和m分别为原字符串和子串的长度。为了实现KMP算法，通常需要对字符串进行哈希操作，然后按照哈希值进行匹配。

int KMP(char *s, char *p)
{
    int m = strlen(p), n = strlen(s);
    int *next = new int[m];
    getNext(next, p);
    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (j == -1 || s[i] == p[j])
        {
            i++; j++;
        }
        else j = next[j];
    }
    delete[] next;
    if (j == m) return i - j;
    else return -1;
}

六、字符串哈希值算法

字符串哈希值算法需要满足以下条件：

1. 相同的字符串哈希值相同；

2. 不同的字符串哈希值应尽可能不同，以避免哈希冲突。

七、字符串哈希值会重复吗

由于哈希算法的原理，字符串哈希值存在重复的情况，特别是对于长度较短的字符串，重复的概率较高。在实际应用中，需要采用不同的哈希算法或者增加哈希表的大小来降低哈希冲突的概率。

八、字符串哈希取模

字符串哈希取模是将哈希值映射到数组下标，一般采用hash % M的方式，其中M一般是一个素数，这样可以有效减小哈希冲突的概率。不同的取模方式可以影响哈希冲突的情况，需要根据实际场景调整M的取值。

九、字符串哈希查找

字符串哈希查找是指根据哈希值查找对应的字符串，通常需要将字符串哈希值存储在哈希表中，以便于快速查找。在使用字符串哈希查找时，需要保证哈希表的大小足够大，并且哈希冲突的概率较低，否则会影响查找效率。

十、字符串哈希碰撞概率

字符串哈希碰撞概率是指不同的字符串映射到同一个哈希值的概率，通常由哈希算法和哈希表大小两个因素决定。在实际应用中，需要根据具体场景选择合适的哈希算法和哈希表大小，以确保碰撞概率足够小。

代码示例

下面是一个使用哈希表实现字符串查找的示例代码：

class HashTable
{
public:
    HashTable(int size = 1000);
    ~HashTable();
    void insert(char *str);
    bool search(char *str);
private:
    int getSize();
    void rehash();
private:
    vector table;
    int currentSize;
};
int HashTable::getSize()
{
    return table.size();
}
HashTable::HashTable(int size)
{
    currentSize = 0;
    table.resize(size);
}
HashTable::~HashTable()
{
    table.clear();
}
void HashTable::insert(char *str)
{
    int pos;
    for (int i=0; i getSize()) rehash();
            return;
        }
    }
}
bool HashTable::search(char *str)
{
    int pos;
    for (int i=0; i<3; i++)
    {
        pos = (BKDRHash(str) + i) % getSize();
        if (table[pos] == str) return true;
        if (table[pos].empty()) return false;
    }
    return false;
}
void HashTable::rehash()
{
    vector temp = table;
    table.resize(getSize() * 2);
    for (int i=0; i<temp.size(); i++)
    {
        if (!temp[i].empty()) insert(&temp[i][0]);
    }
}