字符串哈希原理及相關技術

一、字符串哈希值

字符串哈希可以將字符串映射成唯一的哈希值，哈希值可以用於字符串的快速查找、去重等操作。字符串哈希值的計算可以採用不同的算法，常見的有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]);
    }
}