哈希表基础知识

哈希表(Hash table，也叫散列表)，是根据关键字值(key)直接进行访问的数据结构，它通过把关键字值映射到表中一个位置(数组下标)来直接访问，以加快查找关 键字值的速度。这个映射函数叫做哈希(散列)函数，存放记录的数组叫做哈希 (散列)表。

eg1-最简单的哈希-字符哈希

使用数组下标，统计字符串中各个字符出现的次数。

//ASC2码从0-127，故使用数组下标做映射，最大范围至128
#include<stdio.h>
#include<string>
int main(){
    int char_map[128] = {0};
    std::string str = "abcdefgaaxxy";// 统计字符串中各个字符的数量
    for(int i = 0; i < str.length(); i++){
        char_map[str[i]]++;
    }
    for(int i = 0; i< 128;i++){
        if(char_map[i] > 0){
            printf("[%c][%d] : %d\n",i,i,char_map[i])
        }
    }
    return 0;
}
// char_map['a']++即char_map[97]++

eg2-哈希表排序整数

使用哈希映射的方法对固定数据范围的非负整数数组进行排序。

#include<stdio.h>
int main(){
    int random[10] = {999, 1, 444, 7, 20, 9, 1, 3, 7, 7};
    int hash_map[1000] = {0};
    for(int i = 0; i < 10; i++){
        hash_map[random[i]] ++;
    }
    for(int i = 0; i < 1000; i++){
        for(int j = 0; j < hash_map[i]; j++){
            printf("%d\n",i);
        }
    }//时间复杂度O(表长+n) n为元素个数
    return 0;
}

问题1：任意元素的映射

1.当遇到负数或非常大的整数，如何进行哈希(映射)? 如:-5、99999999、...
2.当遇到字符串，如何进行哈希(映射)? 如:abcdefg、XYZ、...
3.当遇其他到无法直接映射的数据类型，如浮点数、数组、对象等等 ，如何进行哈希(映射)?
如:1.2345、[1, 2, 3]、...

解决

利用哈希函数，将关键字值(key)(大整数、字符串、浮点数等)转换为 整数再对表长取余，从而关键字值被转换为哈希表的表长范围内的整数 ，从而使用数组下标进行访问。

问题2:发生冲突

哈希函数可能将不同的数据映射到同一个数组下标上，即发生了冲突，我们 如何解决?

拉链法解决冲突，构造哈希表

将所有哈希函数结果相同的结点连接在同一个 单链表中。
若选定的哈希表长度为m，则可将哈希表定义为一 个长度为m的指针数组t[0..m-1]，指针数组中的每个指针指向哈希函数结果相同的单链表。
插入value:
将元素value插入哈希表，若元素value的哈希函数 值为hash_key，将value对应的节点以头插法的方式插入到t[hash_key]为头指针的单链表中。
查找value:
若元素value的哈希函数值为hash_key，遍历以 t[hash_key]为头指针的单链表，查找链表各个节点的值域是否为value。

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL){};
};

int hash_func(int key ,int table_len){
    return key % table_len; // 整数哈希函数，直接取余
}
void insert(ListNode * hash_table[], ListNode *node, int table_len){
    int hash_key = hash_func(node->val, table_len);
    node->next = hash_table[hash_key];//使用头插法插入节点
    hash_table[hash_key] = node;
}
bool search(ListNode *hash_table[], int value, int table_len){
    int hash_key = hash_func(value, table_len);
    ListNode *head = hash_table[hash_key];
    while(head){
        if(head->val == value){
            return true;
        }
         head = head->next;
    }
    return false;
}

测试

int main(){
    const int TABLE_LEN = 11;
    ListNode *hash_table[TABLE_LEN] = {0};
    std::vector<ListNode *> hash_node_vec;
    int test[8] = {1, 1, 4, 9, 20, 30, 150, 500};
    for(int i = 0; i < 8; i++){
        hash_node_vec.push_back(new ListNode(test[i]));
    }
    for(int i = 0; i < hash_node_vec.size(); i++){
        insert(hash_table, hash_node_vec[i],TABLE_LEN)
    }
    printf("Hash table:\n");
    for(int i =0; i < TABLE_LEN; i++){
        printf("[%d]",i);
        ListNode *head = hash_table[i];
        while(head){
            printf("->%d",head->val);
            head = head->next;
        }
        printf("\n");
    }
    printf("\n");
    printf("Test  search:\n");
    for(int i = 0 ; i < 10; i++){
        if(search(hash_table, i , TABLE_LEN)){
            printf("%d is in the hash table\n");
        }
        else{
            printf("%d is not in the hash table\n");
        }
    }
    return 0;
}

哈希map与STL map