递归火山软件开发平台

标题: 想了好几天了。我认为数组的访问速度绝对优于哈希表 [打印本页]

作者: urenai 时间: 2024-6-25 00:12
标题: 想了好几天了。我认为数组的访问速度绝对优于哈希表
我才疏学浅，没什么知识储备。
我想不到有什么对象可以代替数组来完成。

通常我们使用哈希表都是:键/值。
那么如果表大到不可思议的时候，
哈希表还会快吗？

数组就不一样了，不管你有多大，只要你知道索引
他的访问速度就是无限接近0(1)的时间复杂度。
那么，如果我们创建一个多维数组来储存这个键（键值转字节）对应成员值的指针
这样就算你的表大到难受，他的访问速度始终可以保持在0（1）时间复杂度。

但问题是普通数组定义时必须填充成员。即使这个成员不用，为了用到的索引存在，就必须定义。

故:有没有一种类似数组的对象可以满足这个要求呢？

就是支持定义索引-成员

作者: urenai 时间: 2024-6-25 00:15
把这个技术研究透，什么知名的数据库都是弟弟。

作者: fengshangren 时间: 2024-6-25 06:42
不能这样比，本来就是视不同情况来使用，哈希的优势可以根据键来快速取到值，键可以是任何东西，但是数组有很多情况，你必须得一个一个枚举，这是他比较慢的情况

作者: 小蜗牛 时间: 2024-6-25 07:16
这种类型.都是空间换时间..如果你内存足够的话,你可以多次拆分...
最简单的:
哈希表数组[crc32 % 取数组成员数(哈希表数组)].置值(主键,值)

作者: 小小小小鸟 时间: 2024-6-25 07:18
需求决定你使用何种的数据结构~

作者: 小蜗牛 时间: 2024-6-25 07:19
分布式其实也差不多如此...你看百度..一台服务器肯定是储存不了那么多的数据的,就需要根据数据的特征储存到不同的服务器..当然..实际情况会比这个复杂很多..

作者: hcwanz 时间: 2024-6-25 07:43
本帖最后由 hcwanz 于 2024-6-25 07:48 编辑

无序哈希表就行了, 无所谓大小.
他是把键计算出一个独一无二的索引, 然后根据这个索引取数据, 无论哈希表多大, 他都只是进行这个计算

作者: 4463424 时间: 2024-6-25 09:29
这个的前提条件是，你得知道数组索引，
如果不知道索引且数据量很大的时候，那可不一定了！！！

作者: hmyroot 时间: 2024-6-25 12:53
本帖最后由 hmyroot 于 2024-6-25 12:55 编辑

在知道索引的情况下用数组最快，在不知道索引的情况下用表最快，Hash表其实就是计算每组数据的MD5值保存到表中，cha询的时候做匹配，这样比二进制数据比较快很多

作者: uuyyhhjj 时间: 2024-6-25 14:26
无序哈希表 unordered_map
优点，cha询快跟数组基本一样，缺点占用内存大

数组的缺点很明显，如果要检索其中一个成员，你必须遍历数组，数组只适合固定算法，不适合复杂cha询，比如数据库，用数组的效率等于每次cha询都要枚举数组全部成员，其实我看了半天都没看懂你想干什么

作者: urenai 时间: 2024-6-25 14:43

uuyyhhjj 发表于 2024-6-25 14:26
无序哈希表 unordered_map
优点，cha询快跟数组基本一样，缺点占用内存大

举例：键为 abcd；十进制字节：97，98，99，100
以多维数组的方式取值：

对象[97][98][99][100] = 值指针

这个想法强吗？

作者: cloud261 时间: 2024-6-25 17:56
为什么需要想好几天? 功能都不一样,没啥好比的
哈希表内部也是数组, 存放的是桶, 桶也是个数组, 读取的时候还要先给key算hash值求余数才去读取桶数组, 桶里可能还有多个k-v数组, 还得遍历判断是哪个值

而数组是连续内存,读取就一个指令, 没有额外的计算

作者: uuyyhhjj 时间: 2024-6-25 18:24

urenai 发表于 2024-6-25 14:43
举例：键为 abcd；十进制字节：97，98，99，100
以多维数组的方式取值：

问题来了，你怎么维护呢，固定算法你这样没问题，但实际上没法用的
就拿BT种子文件的B编码和json类型来说，你试试用结构体把数据装起来，再取出来，试试看吧

作者: weilai 时间: 2024-6-25 22:06
数组肯定快，这不用想也是数组快

作者: urenai 时间: 2024-6-26 00:25

cloud261 发表于 2024-6-25 17:56
为什么需要想好几天? 功能都不一样,没啥好比的
哈希表内部也是数组, 存放的是桶, 桶也是个数组, 读取的时 ...

只能说你真的了解哈希表。
我非常认同你。

我的假想只是建立在数组的高速访问。

作者: 穗玉天涯 时间: 2024-7-1 23:08
看起来哈希表就是数组管理员还是爱思考的熟练工

作者: accet 时间: 2024-7-1 23:51
我的C++写的游戏服务端用的就是数组.
即使这个位置没有使用也要弄出来放着.
所以很吃内存...

不过我C#的项目都是用字典.. 方便得多.

欢迎光临递归火山软件开发平台 (https://bbs.voldp.com/)