我正在研究一个哈希冲突会成为问题的系统.本质上,有一个系统引用散列表+树结构中的项.但是,有问题的系统首先将包含结构中路径的文本文件编译为包含散列值的二进制文件.这是出于性能原因而完成的.但是由于这种冲突非常糟糕,因为结构不能存储具有相同散列值的2个项目; 要求物品的部分没有足够的信息来知道它需要哪一个.
我最初的想法是2个哈希,要么使用2种不同的算法,要么使用相同的算法两次,使用2种盐会更具抗冲突性.对于不同的散列算法具有相同散列的两个项目是非常不可能的.
由于空间原因,我希望保持32位的哈希值,所以我想我可以切换到使用两个16位算法而不是一个32位算法.但这不会增加可能的哈希值范围......
我知道切换到两个32位哈希会更具抗冲突性,但我想知道切换到2个16位哈希是否至少比单个32位哈希有一些增益？我不是数学上最倾向的人,所以我甚至不知道如何开始检查答案,而不是强迫它...
系统的一些背景:
项目由人类命名,它们不是随机字符串,通常由没有空格的单词,字母和数字组成.它是一个嵌套的哈希结构,所以如果你有类似{a => {b => {c =>'blah'}}}的东西,你可以通过获得a/b/c的值获得值'blah',编译请求将是直接序列中的3个哈希值,哈希值为a,b,然后是c.
当给定级别发生碰撞时,只有一个问题.顶级项目与较低级别之间的碰撞很好.您可以{a => {a => {...}}},几乎可以保证不同级别的冲突(不是问题).
实际上,任何给定级别的哈希值都可能少于100个,并且在同一级别上没有任何值会重复.
为了测试我采用的哈希算法(忘了哪一个,但我没有发明它)我下载了整个CPAN Perl模块列表,将所有命名空间/模块拆分成唯一的单词,最后散列每个搜索冲突,我遇到0碰撞.这意味着该算法对CPAN命名空间列表中的每个唯一字具有不同的散列值(或者我做错了).这对我来说似乎足够好,但它仍然在我的大脑中唠叨.
我已经看过几个解决这个问题的线程.
我还查看了git filter-branch手册页.
更新
我已经改为2脚本系统:
#!/bin/bash
git filter-branch --index-filter '~/doit.sh' HEAD
和doit.sh
#!/bin/bash
git ls-files -s | \
sed "s-\t-&data/perl_modules/-" | \
GIT_INDEX_FILE="$GIT_INDEX_FILE.new" git update-index --index-info && \
mv "$GIT_INDEX_FILE.new" "$GIT_INDEX_FILE"
这避免了以前的错误,但现在得到了这个(用[...]替换了路径):
Rewrite c35e4ef0626fb2045f57fa5b605e7663b8d06196 (1/10977)mv: cannot stat `[...]/.git-rewrite/t/../index.new': No such file or directory
index filter failed: ~/doit.sh
我跑的时候
ls-files- s | sed ... | git update-index ...
我得到它应该生成的索引文件.当我更改doit.sh文件以输出sed的结果而不是将其传递给git update-index时,它似乎产生了正确的输出......似乎git update-index在下面运行时根本就不创建文件--index过滤器....
再次更新:
当我改变
mv"$ GIT_INDEX_FILE.new""$ GIT_INDEX_FILE"
至
mv"$ GIT_INDEX_FILE.new""$ GIT_INDEX_FILE"|| 真正
它失败了第一个MV,但所有其他(到目前为止)都在工作.
所有这些都在这个脚本中达到了高潮:
git filter-branch --index-filter \
'git ls-files …程序在C中使用std = c99,这是在64位机器上.
struct epochs {
volatile unsigned int epoch : 1;
volatile unsigned int pulse : 1;
volatile unsigned int active0 : 7;
volatile unsigned int active1 : 7;
volatile unsigned int counter0 : 24;
volatile unsigned int counter1 : 24;
};
当我检查sizeof(epochs)它给了我12.
我可以告诉gcc不要通过添加__attribute((packed))来填充它; 所以我可以解决它.但是,我真的想知道为什么要添加4个字节来填充这个64位结构？
这里的主要内容是这个结构需要64位,因为它在64位原子交换操作中一次更新,当然这对12字节值不起作用.
我有一个共享内存池,许多不同的线程可以从中请求分配.从这个请求分配将在每个线程中发生很多,但是线程的数量可能很小,通常只有1个线程在运行.我不确定以下哪种方法可以解决这个问题.
最终我可能需要实现两者并看看哪个产生更有利的结果......我也担心即使考虑#2也可能是过早的优化,因为我实际上并没有使用这个共享资源编写的代码.但问题是如此有趣,以至于它继续分散我对其他工作的注意力.
1)创建互斥锁并让线程在获取分配之前尝试锁定它,然后解锁它.
2)让每个线程注册一个请求槽,当需要分配时,它将请求放入槽中,然后阻塞(while(result == NULL){usleep()})等待请求槽有结果.单个线程连续迭代请求时隙,进行分配并将它们分配给请求时隙中的结果.
数字1是简单的解决方案,但如果时机正确,单个线程可能会占用锁定.第二个更复杂,但是当从资源中提取时,确保线程之间的公平性.但是它仍然会阻塞请求线程,如果有很多线程,迭代可以在没有进行任何实际分配的情况下刻录周期,直到找到要满足的请求.
注意:使用pthreads在Linux上使用C语言