哈希表基础知识

哈希表(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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏V站

PHP常见函数和过滤函数的深入探究

32 位系统最大带符号的 integer 范围是 -2147483648 到 2147483647。举例,在这样的系统上, intval(‘1000000000...

31590
来自专栏杨建荣的学习笔记

关于oracle中的sql数据类型(r3笔记第59天)

数据类型对于每一种编程语言而言都是数据存储的基础,对于编程语言的实现功能而言也是一个标尺,有些编程语言可能数据类型很丰富,比如java,c,在数据计算方面的支持...

29740
来自专栏数据结构与算法

BZOJ4355: Play with sequence(吉司机线段树)

这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??

21720
来自专栏Ryan Miao

MongoDB-基础-条件操作符

1.一些解释 less than         :  比..少  lt greater than      :  比..多  gt equals       ...

31360
来自专栏数据结构与算法

洛谷P2633 Count on a tree

题目描述 给定一棵N个节点的树,每个点有一个权值,对于M个询问(u,v,k),你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastan...

29360
来自专栏个人随笔

sql sever基本查询语句

查询(*可代表全部)(<>代表不等于于) select 列名 from 表名(,隔开) where 查询条件 order by 排序的列名 +连接的数据类型必须...

28250
来自专栏恰童鞋骚年

Hadoop学习笔记—11.MapReduce中的排序和分组

  从上图中可以清楚地看出,在Step1.4也就是第四步中,需要对不同分区中的数据进行排序和分组,默认情况下,是按照key进行排序和分组。

13420
来自专栏书山有路勤为径

二分查找

已知一个排序数组A,如A= [-1,2,5,20,90,100,207,800] 另外一个乱序数组B,如B =[50,90,3,-1,207,80] 求B中...

9840
来自专栏NetCore

解读C#中的正则表达式

 多少年来,许多的编程语言和工具都包含对正则表达式的支持,.NET基础类库中包含有一个名字空间和一系列可以充分发挥规则表达式威力的类,而且它们也都与未...

25370
来自专栏程序员互动联盟

【答疑解惑】++前缀和后缀的区别

网友们的问题: ? 我的解答: ? 这个知识点在C、C++和Java中都是一样的,++前缀就进行自增然后再用自增后的值,++后缀则是先用这个值,然后再进行自增。...

32360

扫码关注云+社区

领取腾讯云代金券