• 2010-04-07

    [Code] 发现一个有趣的问题(已解决) - [Code]

    版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://www.blogbus.com/sgzxy-logs/61747827.html

         在做毕业设计的过程中,在思考一个Hash值的产生算法时,偶然抽象出这么一个有趣的问题。当然我数学很水,不知道这种问题是否只是某一数论问题的特例,早已有完美解答之类的……那么简单讨论下,请数学高手们解惑。

         问题:

         给出n个元素,为每个元素编一个唯一的索引(比如用整数)。其中任意两个元素组合后,将这两个元素的索引经过某种运算后,可以得到一个唯一的整数值,我们把该值称为Hash值,所有Hash值的集合被称为Hash集合。那么问题是,如何编索引,以及产生Hash值时采用何种运算,可以使n个元素得到Hash集合中数值的范围最小。(比如Hash集合是{ 3,6,9,10 },则数值范围是10-3=7)

         我的想法:

         这个问题在算法中的意义很明显,就是开辟一个最小的连续空间就能满足那n个元素两两组合的Hash值。

         一开始我按经验想到用1、2、4... 2^n这样的二进制编索引,用求和进行运算,但很快发现这样的空间远非最小。然后随便试了几下就发现斐波那契数列是很不错的索引方式。

         比如说n=5时,编出的索引是1、2、3、5、8,那么加法运算得到的Hash集合是{ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13 }。然而这其中12这个Hash值是被浪费了,而且可以容易发现,当n越大时,浪费的Hash值越多(这个浪费的数量也呈斐波那契数列之和的增值速度,可以简单归纳发现),因此也并不算是非常满意的解决方案。不过我的算法中n常常很小,因此这一方案也已足够。

         但问题是,这一方案是理论最优的吗?

         如果采用整数索引和加法运算,那么根据一个简单的贪心归纳过程,似乎发现斐波那契数列的方案就是最优。而索引总是离散值(阿列夫零的密度),似乎都可以被映射到整数,于是主要问题就在于加法运算是否最优。这个我还没有头绪,看看各位谁有高见……

         --------------------------我是半小时后的分割线-------------------------

         刚刚从床上爬起来,在我快要睡着的时候,突然发现这个所谓有趣的问题原来是如此的弱智,且听我道来:

         将n个元素用1..n整数进行索引,产生Hash值的运算为直接将两个数组成一个有序对(i,j),其中 i

         而这又是个多么弱智的问题啊,不过一个等差数列的运算而已。

         Hash_Value = ( 2*n - i ) / 2 * ( i - 1 ) + ( j - i )

         没看明白的话自己找找规律推一推就知道了……果然是有完美解啊,只是Hash值的运算代价高了一点点,不过只是一点点而已,嗯嗯。

         ------------------------------2010/11/6----------------------------------------------------

         又一次在项目中用到了这种hash方式(使用这种hash,在多线程算组合数量的问题时可以高效写入结果集而不用担心同步问题),把数组为0情况下的Hash值公式记一下,省得以后再推:

         Hash_Value = ( ( 2*n - 1 - i ) * i ) / 2 + ( j - i ) - 1

    分享到: