Hash表的定义

哈希表(Hash table，也叫散列表)，是根据关键字值(key)直接进行访问的数据结构，它通过把关键字值 映射到表中一个位置 (数组下标 )来直接访问，以加快查找 关键字值的速度。这个映射函数叫做 哈希(散列)函数，存放记录的数组 叫做哈希 ( )(散列)表。 给定表M，存在函数f(key)，对任意的关键字值key，代入函数后若能得到包含该 关键字的表中地址，称表M为哈希(Hash)表，函数f(key)为哈希(Hash) 函数。

拉链法解决冲突

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

要点总结1:结构体变量的初始化

理解初始化方法ListNode():   {}

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x,int y): val(x),next(NULL){}//通过这种方法创建出来的是指针
};

ListNode a = {3,2};//作用是将3赋值给上面(int x,int y)中的x，将2赋值给y

要点总结2:定义指针数组的两种形式

定义指针数组的时候，有两种形式。一种是使用指针的形式，这时需要使用两个指针符号，即**。另一种是数组的形式。

指针的形式

    const int TABLE_LEN = 11;

    ListNode **hash_table = (ListNode **)malloc(TABLE_LEN * sizeof(ListNode *));

//在上一行代码中，只是进行了堆分配内存，并没有初始化这些内存，初始化方法如下。如果不进行初始化，那么就埋下了一个隐患或者bug。

    for(int i=0;i<TABLE_LEN;i++){

        *(hash_table + i) = 0;//这里 = 0和= NULL的效果是相同的

    }

数组的形式定义指针数组，也就是说，使用另一种方法定义指针数组：

const int TABLE_LEN 11;

ListNode *hash_table[TABLE_LEN] = {0};

= {0}的作用相当于将数组中的每一个原素进行了初始化，或者赋予了初始值。

由以上分析可知，使用数组的形式定义指针数组更加方便和快捷。

代码

输出的结果

coding

#include<iostream>
#include<vector>
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;//整数h哈希函数，h直接取余
}//插入的是一个节点
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(int argc, const char * argv[]) {const int TABLE_LEN = 11;//这里不需要分配内存，因为在insert函数执行的时候进行了分配内存的操作//ListNode **hash_table = (ListNode **)malloc(TABLE_LEN * sizeof(ListNode *));ListNode **hash_table;for(int i=0;i<TABLE_LEN;i++){*(hash_table + i) = 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",i);}else{printf("%d is not in the hash table.\n",i);}}return 0;
}