江苏龙网

  1. 主页 > 生活百科 > >

C｜数据存储地址与字节偏移、数据索引( 二 )

数据存储


C｜数据存储地址与字节偏移、数据索引

文章插图
 
看if与switch的代码比较：
#include <stdio.h>bool IsLeapYear(int y)// 判断是否为闰年{ return((y%4==0&&y%100!=0)||y%400==0);}int DaysOfMonth(int month,int year)// 判断某月天数的函数{ switch(month){case 1:case 3:case 5:case 7:case 8:case 10:case 12:return 31;case 4:case 6:case 9:case 11:return 30;case 2:if(IsLeapYear(year))return 29;elsereturn 28; } return 0;}int DaysOfMonth2(int month,int year)// 判断某月天数的函数{if(month==2){if(IsLeapYear(year))return 29;elsereturn 28;}else if(month==4 || month == 6 || month == 9 || month == 11)return 30;elsereturn 31;}int main(){for(int i=0;i<12;i++)printf("%d ",DaysOfMonth2(i+1,2021));getchar();return 0;}switch汇编：
9:switch(month){004010C8moveax,dword ptr [ebp+8]004010CBmovdword ptr [ebp-4],eax004010CEmovecx,dword ptr [ebp-4]004010D1subecx,1004010D4movdword ptr [ebp-4],ecx004010D7cmpdword ptr [ebp-4],0Bh004010DBja$L538+23h (00401118)004010DDmovedx,dword ptr [ebp-4]004010E0jmpdword ptr [edx*4+40112Bh]10:case 1:11:case 3:12:case 5:13:case 7:14:case 8:15:case 10:16:case 12:return 31;004010E7moveax,1Fh004010ECjmp$L538+25h (0040111a)17:case 4:18:case 6:19:case 9:20:case 11:return 30;004010EEmoveax,1Eh004010F3jmp$L538+25h (0040111a)21:case 2:if(IsLeapYear(year))004010F5moveax,dword ptr [ebp+0Ch]004010F8pusheax004010F9call@ILT+5(IsLeapYear) (0040100a)004010FEaddesp,400401101andeax,0FFh00401106testeax,eax00401108je$L538+1Ch (00401111)22:return 29;0040110Amoveax,1Dh0040110Fjmp$L538+25h (0040111a)23:else24:return 28;00401111moveax,1Ch00401116jmp$L538+25h (0040111a)25:}26:return 0;00401118xoreax,eax27:}else if 汇编：
30:if(month==2)004011A8cmpdword ptr [ebp+8],2004011ACjneDaysOfMonth2+41h (004011d1)31:{32:if(IsLeapYear(year))004011AEmoveax,dword ptr [ebp+0Ch]004011B1pusheax004011B2call@ILT+5(IsLeapYear) (0040100a)004011B7addesp,4004011BAandeax,0FFh004011BFtesteax,eax004011C1jeDaysOfMonth2+3Ah (004011ca)33:return 29;004011C3moveax,1Dh004011C8jmpDaysOfMonth2+65h (004011f5)34:else35:return 28;004011CAmoveax,1Ch004011CFjmpDaysOfMonth2+65h (004011f5)36:}37:else if(month==4 || month == 6 || month == 9 || month == 11)004011D1cmpdword ptr [ebp+8],4004011D5jeDaysOfMonth2+59h (004011e9)004011D7cmpdword ptr [ebp+8],6004011DBjeDaysOfMonth2+59h (004011e9)004011DDcmpdword ptr [ebp+8],9004011E1jeDaysOfMonth2+59h (004011e9)004011E3cmpdword ptr [ebp+8],0Bh004011E7jneDaysOfMonth2+60h (004011f0)38:return 30;004011E9moveax,1Eh004011EEjmpDaysOfMonth2+65h (004011f5)39:else40:return 31;004011F0moveax,1Fh41:42:}4 hash表的最好情况可以实现到数据的直接映射哈希表是维护字典的一种非常实用的方法 。他们利用了这样一个事实，即一旦有了索引(index)，在数组中查找一个元素需要常数时间 。散列函数是一种将键（key）映射到整数的数学函数 。我们将使用散列函数的值作为数组的索引（将元素的键值映射为下标），并将元素存储在该位置 。
使用这样一种称为散列(hash)的策略可以非常有效地实现映射(map)，在这种策略中，键(key)被转换为一个整数，该整数决定了实现(implementation)应该在哪里查找结果 。
hasing算法的一个常见实现是分配一个动态的bucket数组，每个bucket都包含一个指向该bucket的键的链表 。只要条目数与存储桶数的比率不超过0.7左右，get和put方法的平均运行时间为O(1) 。
下标与地址相关，让关键字也让地址相关，这就是hash，但key与下标或索引相比，包含的信息更多 。
常用的hash函数种类：
4.1 除留余数法
最简单的哈希算法是将数据除以某一个常数后取余数来当索引 。
h(key) = key mod b
// 哈希法的存储与查找，核心在于如何将数据的存储位置映射为数组的下标#if 0#include <IOStream>using namespace std;/*下面这段代码是典型的用空间换时间的算法，数据与存储其所占空间的下标完全相同 。下面这段代码不具有任何的实用性，但充分说明了这种思路 。*/int search(int h[], int key);void store(int h[], int data);int main(){int data[1000]={0};int m, n;for (int i = 0; i < 6; i++){cin>>n;store(data, n);}cin>>m;int result = search(data, m);if (result)cout<<"在数组中找到." <<endl;elsecout<<"没有此数据!"<<endl;return 0;}int search(int d[], int key){return d[key];}void store(int d[], int n){d[n]=n;}#else//下面是采用哈希法存储数据并实现查找的示例 。//实现哈希函数用“除法取余法”，解决冲突为“开放地址法” 。#include <iostream>using namespace std;intsearchHash(int h[], int len, int key);void insertHash(int h[], int len, int data);int main(){const int hashLength = 13;//哈希表长度int hashTable[hashLength]={0};int m, n;//创建hashfor (int i = 0; i < 6; i++){cout<<"请输入第"<<i<<"个值（共6个）：";cin>>n;insertHash(hashTable, hashLength, n);}cout<<"请输入需要查找的值：";cin>>m;int result = searchHash(hashTable,hashLength, m);if (result != -1)cout<<"已经在数组中找到，位置为：" << result<<endl;elsecout<<"没有此原始"<<endl;getchar();return 0;}int searchHash(int h[], int len, int key){int hashAddress = key % len;// 哈希函数// 指定hashAdrress对应值存在但不是关键值，则用开放寻址法解决while (h[hashAddress] != 0 && h[hashAddress] != key){hashAddress = (++hashAddress) % len;}// 查找到了开放单元，表示查找失败if (h[hashAddress] == 0)return -1;return hashAddress;}void insertHash(int h[], int len, int data) // 数据插入Hash表{int hashAddress = data % len;// 哈希函数// 如果key存在，则说明已经被别人占用，此时必须解决冲突while (h[hashAddress] != 0){// 用开放寻址法找到hashAddress = (++hashAddress) % len;}// 将data存入字典中h[hashAddress] = data;}#endif


推荐阅读


上一篇：高并发web系统性能优化

下一篇：ZooKeeper集群部署流程