前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >哈希表基础知识

哈希表基础知识

作者头像
小飞侠xp
发布2018-08-29 11:08:15
5360
发布2018-08-29 11:08:15
举报
文章被收录于专栏:书山有路勤为径

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

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

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

代码语言:javascript
复制
//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-哈希表排序整数

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

代码语言:javascript
复制
#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。

代码语言:javascript
复制
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;
}
测试
代码语言:javascript
复制
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
代码语言:javascript
复制
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.05.09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • eg1-最简单的哈希-字符哈希
  • eg2-哈希表排序整数
  • 问题1:任意元素的映射
  • 解决
  • 问题2:发生冲突
  • 拉链法解决冲突,构造哈希表
  • 测试
  • 哈希map与STL map
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档