7. 哈希表

1. 哈希表定义和简单应用

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

给定表M，存在 $f(key)$ , 对任意关键字值key，代入函数若能得到包含该关键字值的表中地址，就称表M为哈希表，函数 $f(key)$ 为哈希函数。

示例1：统计字符串中，各个字符数量

#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]]++;// char_map['a']++即char_map[97]++
    }
    for (int i = 0; i< 128; i++){
        if (char_map[i] > 0){
            printf("%c %d: %d\n", i, i, char_map[i]);
        }
    }
    return 0;
}
=============================================================
a 97: 3
b 98: 1
c 99: 1
d 100: 1
e 101: 1
f 102: 1
g 103: 1
x 120: 2
y 121: 1

示例2：哈希表排序整数

#include <stdio.h>
// **示例2：哈希表排序整数**
// 使用哈希表排序，数组的下标对正整数排序，这只适用正整数
//哈希表的长度，需要超过最大待排序数字
int main(){
    int random[10] = {99, 1, 444, 7, 90, 1, 4, 6, 888, 5};
    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)元素个数
    }
    return 0;
}

======================================================================
1
1
4
5
6
7
90
99
444
888

2. 任意元素的映射

当遇到负数或非常大的整数，如何哈希?
当遇到字符串如何哈希？
当遇到无法直接映射的数据类型，如浮点数和数组、对象等如何进行哈希?

利用哈希函数，将关键字值key(大整数、字符串、浮点数等)转换为整数在对表长取余，从而关键字值被转换为哈希表的表长范围内的整数。

#include <stdio.h>
#include <string>

int int_func(int key, int table_len){
    return key % table_len;
}

//字符串字符ascii相加得到整数再对表长取余
int string_func(std::string key, int table_len){
    int sum = 0;
    for (int i = 0; i < key.length(); i++){
        sum += key[i];
    }
    return sum % table_len;
}
//不同整数或字符串，用于哈希函数的选择，
//会映射到同一个下标出，产生冲突如4位置
//到底是abc出现2次还是bac出现两次还是各一次呢
int main(){
    const int TAB_LEN = 10;
    int hash_map[TAB_LEN] = {0};
    hash_map[int_func(9995, TAB_LEN)]++;
    hash_map[int_func(5, TAB_LEN)]++;
    hash_map[string_func("abc", TAB_LEN)]++;
    hash_map[string_func("bac", TAB_LEN)]++;
    for (int i = 0; i< TAB_LEN; i++){
        printf("hash_map[%d] = %d\n", i, hash_map[i]);
    }
    return 0;
}

=============================================================
hash_map[0] = 0
hash_map[1] = 0
hash_map[2] = 0
hash_map[3] = 0
hash_map[4] = 2
hash_map[5] = 2
hash_map[6] = 0
hash_map[7] = 0
hash_map[8] = 0
hash_map[9] = 0