基于哈希表的机器学习特征哈希

基于哈希表的机器学习特征哈希

引用

CSDN

1.

https://blog.csdn.net/m0_73867959/article/details/140243737

本文详细介绍了基于哈希表的机器学习特征哈希的基础知识，包括哈希函数、哈希表的概念、特征哈希以及哈希表的C语言实现。文章内容丰富，涵盖了哈希函数的特点、常见构造方法、哈希冲突的解决方法以及哈希表的基本操作等。同时，作者还提供了详细的实现过程和代码示例，适合初学者学习和参考。

基础知识

Hash表的概念

如果想要查找一个数据，二叉排序树、二叉平衡树、红黑树、B、B+树等都是将每个节点的值取出来并与查找值进行比较，效率比较低，而Hash表能够搭配哈希函数实现查找关键字key，可以直接确定查找值所在位置。所以我们可以总结出：

H（key）= 地址index

即Hash函数根据key计算出其应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表

Hash函数

哈希函数，也叫散列函数，这种函数可以将任何一种数据或者消息压缩成摘要（即散列值），使得其数据量变小且格式固定，在哈希表中，这个摘要即为数据或信息（统称为key）应该存放的地址（索引）。同时良好的哈希函数会尽量降低哈希碰撞（不同的key对应同一个散列值）的概率，使得在给定输入空间内，不同的输入产生不同哈希值的概率非常高，基于Hash函数的唯一性特征，我们可以将其用于地址的计算。

哈希函数的特点

1. 快速计算：哈希函数能够迅速计算出输入数据的哈希值，使得数据的检索、校验等操作能够高效进行。
2. 唯一性：虽然哈希函数无法保证不同输入一定产生不同的哈希值（即存在哈希碰撞的可能性），但在实际应用中，设计良好的哈希函数会尽量降低哈希碰撞的概率，使得在给定输入空间内，不同的输入产生不同哈希值的概率非常高。
3. 单向性：哈希函数是单向的，即从哈希值几乎不可能反推出原始输入数据。这一特性使得哈希函数在密码学、安全存储等领域有广泛应用，如密码存储时仅存储密码的哈希值而非明文密码。
4. 数据完整性校验：由于哈希值的唯一性和单向性，哈希函数常用于检测数据的完整性。通过比较数据的原始哈希值与存储或传输后的哈希值，可以判断数据在存储或传输过程中是否被篡改。
5. 索引与快速查找：在数据结构和算法中，哈希函数用于创建哈希表（散列表），通过哈希值作为索引来快速查找、插入和删除数据项，提高数据处理的效率。

常见的哈希函数构造方法

直接定制法

这种方法的哈希函数为关键字key的线性函数，类似于：

H（key）= C1 * key + C2

这种方法具有较大的局限性，当key值比较大且比较分散时，对存储系统要求较高（所需空间大，但内部碎片大而多）

问题 Q ：对应上面提到的线性的哈希函数，如果给定多组哈希值和与之对应的key值，那在很大程度上能够通过这些数据，反向拟合得到哈希函数的具体形式，并以此来根据哈希值推出key值，那这能否证明哈希函数不具有单向性呢?

解答 A ：哈希函数的单向性通常指的是，从哈希值逆向推导出原始数据（即key）在计算上是不可行的，或者说需要极大的计算资源以至于在实际应用中几乎不可能完成。对于我们给定的哈希函数，确实有可能能够通过以上方法得到哈希函数的表达式，但在一般的情况下，哈希函数被人为设置为很难通过大量数据能够精确拟合甚至部分根本无法拟合的形式，因此哈希函数的单向性是存在的。

数字分析法

这种方法首先从关键字集合中提取出数值特征（比如以身份证为例，同一省市的人的身份证前6位是相同的，只有后面12位数值不同，因此没有存储的必要），并根据数值特征设计对应的哈希函数，在身份证案例中设计如下：

H（Key）=（key）%100000

对key进行取余100000之后身份证（key）值前6位将被除去，其结果仅为后面的12位不同的值。这种方法也具有较大的局限性，设计对应的哈希函数必须要提前知道对应的关键字集合，且还需提取其数据特征。

平方取中法

这种方法适用于关键字中某些数值多次重复出现，比如114514，111445，这时可以使用对关键字整体平方后取中间几位数作为最终的存储地址（索引），可以使得原本相似的数据变得不再相似

使用上面提到的两个关键字举例：

114514^2 = 13,113,456,196

111445^2 = 12,419,988,025

即H（114514）=113456 H（111445）=419988

这种方法适合事先不知道数据并且数据长度较小的情况

折叠法

如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址。比如key=114514，将key分割为 11 45 14，并计算每段叠加和后得到最终存储地址

1+1=2 4+5=9 1+4=5

因此key=114514可以存储在地址（索引）为295的单元格内，即H（114514）=295

该方法适用于数字位数较多且事先不知道数据分布的情况

除留余数法

这种方法的哈希函数将key对一个数p进行取余，得到的结果即为存储地址（索引），类似计算机组成原理中的存储系统的直接映射，即：

H（key）=key MOD p（p<=m ，m为表长）

在这种方法中最关键的就是确定p的值。p一般为不大于m的质数 或是 不含20以下的质因子的合数，这样可以减少哈希冲突。比如key = 7，39，18，24，33，21时取表长m为9 p为7 那么存储如下

index 0 1 2 3 4 5 6 7 8

key 7 21（冲突后移） 24 39 18（冲突后移） 33冲突后移）

备注：在本例中使用线性探测的开放定址法解决哈希冲突问题(将在下方进行解释)。

随机数法

正如其名，使用Random函数获取关键字的随机函数值为它的摘要（索引地址）

H（key） =Random（key）

Hash冲突

Hash冲突即存在两个及以上个关键词对应了同一个摘要（散列值）而放入同一个桶中，使得利用哈希函数的值作为地址的想法无法实现（不能有多个数据存在同一地址下）

由此引入了解决Hash冲突的几种方法：

开放定址法

若存在某个关键词Keyj使得H（Keyj）与已经存在的某个关键词Keyi的哈希函数的值相等，即

H（keyi）=H（keyj）

那么将Keyj的散列值进行重新计算，公式为H（keyj）=（H（Keyi）+dj） MOD m（m为表长）

其中d有三种取法

1.线性探测（d[j] = d[j-1] + 1）

这种方法说白了就是在冲突的地方依次往后查找空位，有空的就填入，否则继续往后查找空位

2.平方探测（d[j] = d[j-1] +(-) j^2）

这种方法区别于上面那种的是每次都往前后两个方向进行寻找，每次寻找的跨度都是j的平方。有定理显示：如果散列表长度m是某个
4k+3
（k是正整数）形式的**
素数
**时，平方探测法就可以探查到整个散列表空间。（了解即可）

3.双探测再散列

链地址法

假若Keyj与原来存在的Keyi产生Hash冲突，那么在存储数据Keyi的单元格内加一个指针在Keyi数据后，指向冲突的数据Keyj，在链地址法下，我们将每个存储单元格叫做一个桶，如果某个单元格内有数据，则新来的数据可以补充到原数据末尾指针所指向的地址，就能够把原来只能存储一个数据的内存单元，变成了一个能够存很多数据的桶，并将这时的最初存储单元的内存地址叫做桶号。（例如下图中存储数据为0，1，2，3...10的内存地址都被叫做桶号）

公共溢出区法

这种方法设定了一个特殊区，专用于存储出现冲突的数据。适用于冲突较少的情况

再散列法

再散列法即如果发生冲突就再进行一次散列（再传入一次不同的哈希函数从而得到新的散列值）。因此需要提前准备若干个Hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个以此类推，直至不再发生冲突。

Hash表的增删查

Hash表的增添

按照哈希函数将key值存入对应的地址即可

Hash表的删除

首先链地址法是可以直接删除元素的，但是开放定址法是不行的，拿前面的双探测再散列来说，假如我们删除了元素1，将其位置置空，那 23就永远找不到了。正确做法应该是删除之后置入一个原来不存在的数据，比如-1

Hash表的查找

对于给定的key，计算Hash地址

index = H（key）

如果数组arr [ index ] == NULL 则查找不成功

如果数组arr [ index ] == key 则查找成功

否则 使用冲突解决方法求下一个地址，直到arr [ index ] == key或者 arr [ index ] ==NULL

特征哈希

概念

特征哈希也称为哈希技巧，是一种快速且空间利用率高的特征向量化的方法，可以将任意特征（关键词Key）转换为向量或矩阵中的索引。它通过对特征应用哈希函数并直接使用特征的哈希函数值（摘要）作为索引来工作。在下一节中将有更为详细的介绍。

机器学习基础

机器学习是人工智能领域的一个重要分支，其核心是让计算机通过数据学习并做出预测或决策。在机器学习中，特征工程是一个关键步骤，它涉及到如何选择、提取和转换原始数据中的特征，以便更好地适应学习算法。特征哈希作为一种特征向量化的方法，可以将任意特征（关键词Key）转换为向量或矩阵中的索引，从而实现快速且空间利用率高的特征向量化。

特征哈希的基本思想是使用哈希函数将特征映射到一个固定大小的向量空间中。具体来说，对于一个特征集合，我们可以定义一个哈希函数H，使得每个特征f都可以通过H(f)映射到一个整数索引i。然后，我们可以使用这个索引i来更新向量空间中的对应位置。例如，如果我们使用一个长度为N的向量v来表示特征向量，那么对于特征f，我们可以将v[H(f)]的值加1（或者使用其他更新规则）。

特征哈希的主要优点是其高效性和简单性。由于特征哈希不需要预先知道所有可能的特征，因此它可以处理大规模的特征集合，而不需要大量的存储空间。此外，特征哈希还可以通过调整哈希函数的参数来控制向量空间的大小，从而平衡存储和计算效率。

然而，特征哈希也存在一些缺点。由于哈希函数可能会导致不同的特征映射到相同的索引（即哈希冲突），因此特征哈希可能会丢失一些特征信息。此外，特征哈希也不适合处理具有复杂语义关系的特征，因为它无法保留特征之间的语义相似性。

在实际应用中，特征哈希通常与其他特征工程方法（如词袋模型、TF-IDF等）结合使用，以获得更好的效果。例如，在文本分类任务中，我们可以先使用词袋模型将文本转换为词频向量，然后使用特征哈希将词频向量映射到一个固定大小的向量空间中，最后使用机器学习算法进行分类。

机器学习特征哈希的实现

在本节中，我们将介绍如何使用C语言实现基于哈希表的机器学习特征哈希。我们将使用一个简单的哈希函数和链地址法来解决哈希冲突。具体实现步骤如下：

1. 定义哈希表结构体

typedef struct {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    int size;
    HashNode** table;
} HashTable;

2. 初始化哈希表

HashTable* createHashTable(int size) {
    HashTable* table = (HashTable*)malloc(sizeof(HashTable));
    table->size = size;
    table->table = (HashNode**)calloc(size, sizeof(HashNode*));
    return table;
}

3. 定义哈希函数

int hashFunction(int key, int size) {
    return key % size;
}

4. 实现插入操作

void insert(HashTable* table, int key, int value) {
    int index = hashFunction(key, table->size);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table->table[index];
    table->table[index] = newNode;
}

5. 实现查找操作

int search(HashTable* table, int key) {
    int index = hashFunction(key, table->size);
    HashNode* currentNode = table->table[index];
    while (currentNode != NULL) {
        if (currentNode->key == key) {
            return currentNode->value;
        }
        currentNode = currentNode->next;
    }
    return -1; // 如果未找到，返回-1
}

6. 实现删除操作

void delete(HashTable* table, int key) {
    int index = hashFunction(key, table->size);
    HashNode* currentNode = table->table[index];
    HashNode* prevNode = NULL;
    while (currentNode != NULL) {
        if (currentNode->key == key) {
            if (prevNode == NULL) {
                table->table[index] = currentNode->next;
            } else {
                prevNode->next = currentNode->next;
            }
            free(currentNode);
            return;
        }
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
}

7. 释放哈希表

void destroyHashTable(HashTable* table) {
    for (int i = 0; i < table->size; i++) {
        HashNode* currentNode = table->table[i];
        while (currentNode != NULL) {
            HashNode* nextNode = currentNode->next;
            free(currentNode);
            currentNode = nextNode;
        }
    }
    free(table->table);
    free(table);
}

通过以上步骤，我们可以实现一个基于哈希表的机器学习特征哈希。在实际应用中，我们可以通过调整哈希表的大小和哈希函数的参数来优化性能。此外，我们还可以使用更复杂的哈希函数和冲突解决方法来提高哈希表的效率和准确性。