当前位置:网站首页>07_哈希
07_哈希
2022-07-02 12:00:00 【听*雨声】
哈希
什么是哈希:
哈希:hash;就是散列函数
1 哈希冲突的4种处理方法:
- 1.开放定址法:也叫线性探测法;
一次探测缺点就是数据会集中在一块,解决方法就是平方探测(二次探测),避免堆积
正数:代表向右探测
负数:代表向左探测
2.再散列函数(哈希)法:
3.链地址法:
只要数据有冲突就头插在同一个下标下公共溢出区法:
一个基本表,一个溢出表;将有冲突的数据放入溢出表。
缺点是当数据过大,基本表太小时,溢出表的规格将会很大
2 链式哈希
结构定义:
#define HASHSIZE 12
typedef struct Node
{
int data;
struct Node* next;
}Node, * PNode;
typedef struct Head
{
//struct Node *arr[HASHSIZE];//指针数组(存放指针的数组)
struct Node arr[HASHSIZE];//数组arr中存放Node本身
}Head, * PHead;
API实现
void Init_listhash(PHead ph)
{
//assert
for (int i = 0; i < HASHSIZE; i++)
{
//ph->arr[i].data;// 不使用
ph->arr[i].next = NULL;
}
}
bool Insert_hash(PHead ph, int key)//头插
{
int hash = key % HASHSIZE;
//创建新节点
struct Node* pnewnode = (Node*)malloc(sizeof(Node) * 1);
assert(pnewnode != NULL);
pnewnode->data = key;
//插入
pnewnode->next = ph->arr[hash].next;
ph->arr[hash].next = pnewnode;
return true;
}
bool Del_Hash(PHead ph, int key)
{
int hash = key % HASHSIZE;
struct Node* p = &ph->arr[hash];
for (p; p->next != NULL; p = p->next)
{
if (p->next->data == key)
{
//此时p->next 指向的这个节点就是我们要删除的那个节点
struct Node* q = p->next;
p->next = q->next;
free(q);
q = NULL;
return true;
}
}
return false;
}
struct Node* Search(PHead ph, int key)
{
int hash = key % HASHSIZE;
struct Node* p = ph->arr[hash].next;
for (p; p != NULL; p = p->next)
{
if (p->data == key)
{
return p;
}
}
return NULL;
}
void Show_Hash(PHead ph)
{
for (int i = 0; i < HASHSIZE; i++)
{
printf("%3d: ", i);
struct Node* p = ph->arr[i].next;
for (p; p != NULL; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
}
3 一致性哈希和虚拟节点
边栏推荐
- AtCoder Beginner Contest 254
- Slashgear shares 2021 life changing technology products, which are somewhat unexpected
- 数据库内容输出有问题怎么解决
- 传感器数据怎么写入电脑数据库
- 【NOI模拟赛】伊莉斯elis(贪心,模拟)
- 【apipost】使用教程
- How does CTO help the business?
- 实用调试技巧
- taobao. logistics. dummy. Send (no logistics delivery processing) interface, Taobao store delivery API interface, Taobao order delivery interface, Taobao R2 interface, Taobao oau2.0 interface
- 【无标题】LeetCode 2321. 拼接数组的最大分数
猜你喜欢
[noi Simulation Competition] scraping (dynamic planning)
[apipost] tutorial
Have you learned the wrong usage of foreach
MFC timer usage
LeetCode 2320. 统计放置房子的方式数
报错:npm WARN config global `--global`, `--local` are deprecated. Use `--location=global` instead.
富文本编辑器添加矢量公式(MathType for TinyMCE ,可视化添加)
C#代码审计实战+前置知识
MathML to latex
Fundamentals of software testing
随机推荐
MFC 定时器使用
Bit by bit of OpenCV calling USB camera
TiDB跨数据中心部署拓扑
2021-2022学年编译原理考试重点[华侨大学]
Introduction to C language -- array
學習使用php實現公曆農曆轉換的方法代碼
LeetCode 2310. 个位数字为 K 的整数之和
记一次报错解决经历依赖重复
TiDB 集群最小部署的拓扑架构
[QNX hypervisor 2.2 user manual]6.3 communication between guest and external
buuctf-pwn write-ups (7)
TiDB 软件和硬件环境建议配置
C语言中的printf函数和scanf函数
How does CTO help the business?
可视化搭建页面工具的前世今生
871. Minimum refueling times: simple priority queue (heap) greedy question
[noi simulation] Elis (greedy, simulation)
Socket and socket address
[untitled] leetcode 2321 Maximum score of concatenated array
关于网页中的文本选择以及统计选中文本长度