我们需要一个模拟关联数组的脚本或类似于Shell Scripting的数据结构的Map,任何主体？
我正在使用C语言编写哈希表,我正在测试字符串的哈希函数.
我尝试过的第一个函数是添加ascii代码并使用modulo(%100)但是我在第一次数据测试时得到的结果很差:140个单词的40个冲突.
最终的输入数据将包含8 000个单词(它是一个文件中的dictionnary存储).哈希表声明为int table [10000]并包含txt文件中单词的位置.
第一个问题是哪个是散列字符串的最佳算法？以及如何确定哈希表的大小？
提前致谢 !
:-)
我想在C#中创建一个Dictionary查找表.我需要将一个3元组的值解析为一个字符串.我尝试使用数组作为键,但这不起作用,我不知道还能做什么.在这一点上,我正在考虑制作一本词典字典词典,但这看起来可能不是很漂亮,尽管我会在javascript中这样做.
哈希表可以实现O(1)似乎是常识,但这对我来说从来没有意义.有人可以解释一下吗？以下是两种情况:
答: 该值是一个小于哈希表大小的int.因此,该值是它自己的哈希值,因此没有哈希表.但如果有,那将是O(1)并且仍然是低效的.
B. 您必须计算值的哈希值.在这种情况下,查找数据大小的顺序为O(n).在你做O(n)工作之后,查找可能是O(1),但在我眼中仍然是O(n).
除非你有一个完美的哈希表或一个大的哈希表,否则每个桶可能有几个项目.因此,无论如何,它在某个时刻转变为一个小的线性搜索.
我认为哈希表很棒,但我没有得到O(1)的名称,除非它只是理论上的.
维基百科关于哈希表的文章始终引用常量查找时间并完全忽略哈希函数的成本.这真是一个公平的衡量标准吗？
编辑:总结我学到的东西:
这在技术上是正确的,因为哈希函数不需要使用密钥中的所有信息,因此可以是恒定时间,并且因为足够大的表可以将冲突降低到接近恒定的时间.
在实践中确实如此,因为随着时间的推移,只要选择散列函数和表大小来最小化冲突,即使这通常意味着不使用常量时间散列函数,它也只会有效.
二进制搜索树比哈希表有什么优势？
哈希表可以在Theta(1)时间查找任何元素,并且添加元素也同样容易....但我不确定反过来的优势.
MATLAB是否支持哈希表？
我正在研究Matlab中需要图像的缩放空间表示的问题.为此,我创建具有方差2-d高斯滤波器sigma*s^k用于k在一定范围内.,然后我使用每一个依次进行过滤图像.现在,我希望从k过滤后的图像中进行某种映射.
如果k总是一个整数,我只需创建一个3D数组,这样:
arr[k] = <image filtered with k-th guassian>
但是,k不一定是整数,所以我不能这样做.我想做的是保持一系列的ks:
arr[find(array_of_ks_ = k)] = <image filtered with k-th guassian>
一开始看起来似乎相当不错,除了我将使用大约20或30个值进行此次查找可能几千次k,并且我担心这会损害性能.
我想知道我是否会更好地使用某种哈希表来做这件事,这样我的查找时间就是O(1)而不是O(n).
现在,我知道我不应该过早优化,我可能根本没有这个问题,但请记住,这只是背景,并且可能存在这种情况,这确实是最佳解决方案,无论是否是我的问题的最佳解决方案.
我似乎无法找到解释如何在VBA中创建哈希表或关联数组的文档.它甚至可能吗？
你可以链接到一篇文章或更好地发布代码吗？
我在学位课程中听说,HashTable如果新的Key条目与另一个条目相撞,它会在"下一个可用"桶中放入一个新条目.
HashTable如果在使用碰撞密钥调用一个碰撞时发生这种碰撞,仍将如何返回正确的值？
我假设Keys是String类型,hashCode()返回默认由Java生成.
如果我实现自己的散列函数并将其用作查找表(即a HashMap或Dictionary)的一部分,那么处理冲突的策略是什么？
我甚至看过有关素数的注释!Google搜索中的信息不太明确.
最近我在一本非常着名的书" 算法导论 "中读到了关于哈希表的内容.我还没有在任何实际的应用程序中使用它们,但想要.但我不知道如何开始.
任何人都可以给我一些使用它的样本,例如,如何使用哈希表实现字典应用程序(如ABBYY Lingvo)？
最后我想知道PHP中哈希表和关联数组之间的区别是什么,我的意思是我应该使用哪种技术以及在哪些情况下？
如果我错了(请原谅)请纠正我,因为实际上我从哈希表开始,我只有基本(理论)知识.
非常感谢.
简而言之：
我已经实现了一个简单的（多键）哈希表，其中包含完全适合缓存行的存储桶（包含多个元素）。插入缓存行存储桶非常简单，也是主循环的关键部分。
我已经实现了三个版本，它们产生相同的结果并且行为应该相同。
谜
然而，尽管所有版本都具有完全相同的缓存行访问模式并产生相同的哈希表数据，但我发现性能差异惊人地大到了 3 倍。
与我的 CPU (i7-7700HQ)相比，最佳实现insert_ok速度慢了大约 3 倍。一个变体 insert_bad 是一种简单的修改，它在缓存行中添加了额外的不必要的线性搜索，以找到要写入的位置（它已经知道），并且不会遭受 3 倍的减速。insert_badinsert_altinsert_ok
与其他 CPU（AMD 5950X (Zen 3)、Intel i7-11800H (Tiger Lake)）相比，完全相同的可执行文件显示insert_ok速度快 1.6 倍。insert_badinsert_alt
# see https://github.com/cr-marcstevens/hashtable_mystery
$ ./test.sh
model name : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
==============================
CXX=g++ CXXFLAGS=-std=c++11 -O2 -march=native -falign-functions=64
tablesize: 117440512 elements: 67108864 loadfactor=0.571429
- test insert_ok : 11200ms
- test insert_bad: 3164ms
(outcome identical to insert_ok: true)
- test insert_alt: 3366ms
(outcome identical …