字符串/超大数据的哈希（hash）高效实现_长字符串的hash策略

作者：从前慢现在也慢 | 2024-07-15 16:06:19

踩

长字符串的hash策略

C++代码中有unordered_map<>()可实现hash操作，但是在追求效率的代码中，使用会严重影响代码的执行效率。

特别当需要hash字符串的时候，可能有人会这么操作：

unordered_map<string, int> hash_map;

上述操作确实没有错误，但是当你在C++中追求高效率的时候，这种写法可能会比较耗时。这里推荐一个利用数组和双向循环链表实现哈希的方法。

通常的hash操作有字符串哈希和较大数据的哈希。

字符串哈希，通常利用移位操作。hval = (hval << 5) + (str[i] - 'a' + 1)，同时需要将 hval 进行缩放，这里一般可以对13131（较大的质数，实验发现哈希冲突较小）或者2的次方（CPU计算除法时对于2的次方速度较快）取余。
对较大的数据哈希，一般也是对13131或者2的次方取余。（这其实也就是hash table的范围）

字符串哈希


#define HASHSIZE 10
#define ull unsigned long long
 
int getHashVal(char* str) {
    int i = 0;
    ull hval = 0;
    while (str[i] != '\0') {
        hval = (hval << 5) + (str[i] - 'a' + 1);
        ++i;
    }
    // 当然这里可以直接返回hval，但是直接的返回值无法通过数组的index进行建立hash table.
    return hval % HASHSIZE; 
}

当然上述方法只适用于str全由小写字母组成的字符串哈希，对于大小写混合后者纯大写字母组成的字符串仅仅需要依据需求修改移位操作就可以。这里仅仅以纯小写字母为例进行算法说明。

(str[i] - 'a' + 1) 可以使得任何一个小写字母均可以由1~26的数字来表示，切记这里需要+1，否则你讲无法区别“a”和“aa”等。

(hval << 5) 左移5位正好可以完全表示1~26，当然也有部分剩余。

(unsigned long long) 最大可以表示64byte的数据，所以这种hash方法一般用来表示字符串长度不超过12的情况。

在这里，我们仅仅是对字符串进行了哈希操作（字符串转整形），但在实际应用中还设计哈希的冲突解决以及检索等，下面我们接着阐述后续内容。

哈希存储结构

char str[] 存储需要哈希的字符串信息。同时需要记录节点的头尾指针。


struct Node {
    char str[11];
    int value;
    Node* next;
    Node* prev;
};
 
Node hash_table[HASHSIZE];

哈希查找

这里为了解决哈希冲突，我们引入了双向循环链表（即将冲突的节点插入到循环链表中）。需要结合双向链表进行操作（具体在哈希冲突解决节中详细阐述）。

当找到str对应的字符串时返回对应节点的指针，当没有找到（哈希表中不存在）时返回空指针nullptr。


Node* findHash(char* str) {
    int hash = getHashVal(str);
    Node* find_node = hash_table[hash].next;
    while (find_node != &hash_table[hash]) {
        if (strcmp(find_node->str, str) == 0) {
            break;
        }
        find_node = find_node->next;
    }
    if (find_node == &hash_table[hash]) {
        return nullptr;
    }
    return find_node;
}

哈希冲突解决（哈希插入更新）

主要通过函数insertHash来实现插入更新，需要基于双向循环链表。

没有时需要插入新Node，当已有时进行响应的更新操作即可（当然这里需要根据自己的具体需求进行修改完善）。


void _add(Node* now, Node* prev, Node* next) {
    now->prev = prev;
    now->next = next;
    prev->next = now;
    next->prev = now;
}
void addNode(Node* now, Node* head) {
    _add(now, head, head->next);
}
void insertHash(char* str, int value) {
    int hash = getHashVal(str);
    Node* node = findHash(str);
    if (node == nullptr) {
        Node* new_node = new Node;
        strcpy(new_node->str, str);
        new_node->value = value;
        addNode(new_node, &hash_table[hash]);
    }
    else {
        node->value = value;
    }
}

以上是hash table的具体实现方法，当然在C++中可以将其封装为类，以便使用中更加方便。这里提供一种封装策略，当然这个的泛化性还需更一步改进。

Hash table 整体实现