V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
tts
V2EX  ›  程序员

请教 Hash 选取问题

  •  
  •   tts · 2014-11-14 17:25:17 +08:00 · 2554 次点击
    这是一个创建于 3644 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有10万个不相同的字符串,平均串长是7,只有字母和数字。想把他们hash成整数作为数组下标。要保证单射,不能重复。请问用什么方法比较好?
    当然,希望映射的像集越小越好,节省空间。
    7 条回复    2014-11-15 21:31:49 +08:00
    binux
        1
    binux  
       2014-11-14 17:41:00 +08:00
    加一个冲突检测机制
    不然告诉我最大串长
    tts
        2
    tts  
    OP
       2014-11-14 18:24:04 +08:00 via iPhone
    加冲突检测怎么做?我不知道怎么映射到比如1到20万整数上。
    最大串长比如20呢?这是用来做什么的?
    binux
        3
    binux  
       2014-11-14 18:39:21 +08:00
    @tts http://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8#.E5.A4.84.E7.90.86.E7.A2.B0.E6.92.9E
    最大长度决定了你能不能找到单射函数,而不是平均长度
    hourui
        4
    hourui  
       2014-11-14 18:39:56 +08:00
    就 10w 级别, 为啥非要用 hash 呢?
    用 trie 树存就好了
    cover
        5
    cover  
       2014-11-14 18:44:47 +08:00
    是啊,单键映射是不可能的把,如果用数值hash的话。。否则要开多大的内存啊
    cover
        6
    cover  
       2014-11-14 18:46:29 +08:00
    hash算法 就用 php的hash算好好了 反正就是普通的字符串么http://www.laruence.com/2009/07/23/994.html
    tts
        7
    tts  
    OP
       2014-11-15 21:31:49 +08:00
    @hourui 有道理。 :)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   4262 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 05:28 · PVG 13:28 · LAX 21:28 · JFK 00:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.