哈希表

Question

想实现一个功能，为快速查找这个url是否已存在，构造一个哈希表。将不同的url字符串，计算出一个哈希值，并将这个哈希值映射到内存中的一段连续空间以二进制表示，如果为true则url存在，如果为false则将它对应的位置设为true，要求这个哈希值不能过长不超过（20位）

Answer 1

你是要自己开发一个HashTable还是咋？Java自带HashSet可以进行快速查找；
此外String自带hash()函数能自动生成哈希值。

Answer 2

不存在“多存一次”，对象都是引用的。自己开发反而很难达到Java自带的所能提供的性能。HashSet<String> hs = new HashSet<String>();
hs.add("http://xxxooo.com/xxoo"); // 增加
if (hs.contains("http://xxxx.com/ooo")) // 检测

Answer 3

你看，每次都要先add进去，如果采用内存映射呢，就只需要遍历一次集合，不用add进去了。

Answer 4

add进去，本身就是建立内存映射的过程。除了映射数组所需的索引空间外，不需要额外空间。你自己实现，绝对不会比这个有本质优势的。你看看HashSet的源码就知道，原理就是那些原理，数据结构早就学过了。求出String的Hash值（比如54321），然后MOD运算到映射数组上（比如数组实际上只有100大小），数组存入String的内存地址（Java中称之为引用）。最后还要解决Hash值冲突问题，一般会通过链表来解决；当然也可以使用二次Hash或下一地址来解决。

Answer 5

不解决碰撞问题是不可能的，因为你没法保证hash值绝对不重复。20个元素的量？用：HashSet set = new HashSet(20*2);

Answer 6

主要难度其实是在Hash算法设计上，要求选择差异性较大的Hash算法，否则算出来结果相似度高这个检索效果就很撮了。建议楼主参考下这里：
http://blog.csdn.net/eaglex/article/details/6310727提供了9种针对字符串的Hash算法，而且带源码。

Answer 7

这几种hash算法都测试过，其实他的碰撞概率还是很大的，
        private int getHashCode(string url)
        {
            int mapCode = -1;            if (null != url && "" != url)
            {
                for (int i = 0; i < url.Length; ++i)
                {
                    mapCode += url[i];
                    mapCode += (mapCode << 16);
                    mapCode ^= (mapCode >> 10);
                }
                mapCode += (mapCode << 6);
                mapCode ^= (mapCode >> 13);
                mapCode += (mapCode << 16);
                if (mapCode < 0)
                {
                    mapCode = Math.Abs(mapCode);
                }
                mapCode = mapCode % m_bitArraySize;
            }
            return mapCode;
        }以上的hashcode的碰撞稍微少一点，希望楼撒谎能够不吝赐教啊