标签: hash-function

出于性能原因,我需要将一组由字符串标识的对象拆分为组.对象可以通过数字或字符串以前缀(限定)形式标识,其中点分隔标识符的各个部分:

12
323
12343
2345233
123123131
ns1:my.label.one
ns1:my.label.two
ns1:my.label.three
ns1:system.text.one
ns2:edit.box.grey
ns2:edit.box.black
ns2:edit.box.mixed

数字标识符从1到数百万.文本标识符最有可能以相同的名称空间前缀(ns1 :)和相同的路径前缀(edit.box.)开头.

为此目的,最好的哈希函数是什么？如果我能根据对象标识符统计以某种方式预测存储桶的大小,那将是很好的.是否有一些基于某些统计信息构建良好哈希函数的好文章？

有数百万个这样的标识符,但目的是基于散列函数将它们分成1-2千组.

我已经查看了这个维基百科页面,但我仍然不明白.有人可以帮助我笨拙的头脑理解散列,散列表/散列映射和散列函数的概念吗？一些例子真的会有所帮助.

我现在制作了15个拼图解算器(用c ++编写),但不仅仅是15个拼图,我的程序还必须解决3x4拼图,8x8拼图等... - > X x Y拼图.我必须以某种方式保存有关访问状态的信息,我的第一个想法是制作树,例如:
拼图:

州1
1 2
3 0

州2
1 3
0 2

我留在树上:

root-> 1-> 2-> 3-> 0
            \ _
                \ - > 3-> 0-> 2

对于所有谜题,这也适用于拼图5x3,6x6等

这个想法有效,但是它浪费了大量内存,而且要添加节点,需要一些时间:/所以效率非常低.

下一个想法是在stl的std :: map <>中保持访问状态,但我不知道如何制作好的哈希函数 - 从拼图状态制作快捷方式(beacouse我不必存储拼图状态,我只需要信息已被访问.你有任何想法,关于std :: map的关键,或其他想法保持信息已被状态访问？

是否有人编写了通用函数,以便hash可以自动为自定义数据类型生成函数(使用该deriving机制)？有几次,我写了以下类型的样板,

data LeafExpr = Var Name | Star deriving (Eq, Show)
instance Hashable LeafExpr where
    hash (Var name) = 476743 * hash name
    hash Star = 152857

这可以自动生成:基本思想是每当添加数据时,您乘以素数,例如使用列表,

hash (x:xs) = hash x + 193847 * hash xs

基本上,我想写的是

data LeafExpr = ... deriving (Hashable)

编辑1

感谢所有非常有帮助的回复,每个人.当我有时间时,我会尝试添加一个通用方法作为练习.现在(也许sclv指的是什么？),我意识到我可以编写稍好的代码,

instance Hashable LeafExpr where
    hash (Var name) = hash ("Leaf-Var", name)
    hash Star = hash "Leaf-Star"

编辑2

使用ghc,乘以随机素数比编辑1中的tupling好得多.与Data.HashTable的冲突从95%(非常糟糕)变为36%.代码在这里:[ http://pastebin.com/WD0Xp0T1 ] [ http://pastebin.com/Nd6cBy6G ].

问题描述: 我正在使用高度敏感的数据集,其中包含人员的电话号码信息作为其中一列.我需要应用(加密/散列函数)将它们转换为某些编码值并进行分析.它可以是单向散列 - 即,在使用加密数据处理后,我们不会将它们转换回原始电话号码.基本上,我正在寻找一个匿名者,它接收电话号码并将它们转换为一些随机值,我可以在其上进行处理.建议这个过程的最佳方法.欢迎使用有关最佳算法的建议.

更新:数据 集的大小我的数据集确实非常庞大,数百GB.

更新:敏感 敏感,我的意思是电话号码不应该是我们分析的一部分.所以,基本上我需要一个单向散列函数但没有冗余 - 每个电话号码应映射到唯一值 - 两个电话号码应该不映射到相同的值.

更新:实施？

感谢您的回答.我正在寻找精心实施.我正在通过python的hashlib库进行散列,它是否必须执行您建议的相同步骤？链接在这里

你能给我一些示例代码来实现这个过程,最好是在Python中吗？

为了生成散列函数,通过将k的余数除以m,将密钥k映射到m个时隙之一.也就是说,哈希函数是

h(k)= k mod m.

我已经在几个地方读到了m的好选择

1. 素数 - 我理解我们想要删除公因子,因此选择素数
2. 不太接近2的精确力量 - 为什么会这样？

查看大规模数据集挖掘一书,第1.3.2节概述了散列函数.没有计算机科学背景,这对我来说是一个新的东西; Ruby是我的第一语言,hash似乎相当于Dictionary<object, object>.我从未考虑过如何将这种数据结构组合在一起.

本书提到了哈希函数,作为实现这些字典数据结构的一种手段.本段:

首先,散列函数h将散列键值作为参数,并产生桶号作为结果.桶号是一个整数,通常在0到B-1的范围内,其中B是桶的数量.哈希键可以是任何类型.散列函数有一个直观的属性,它们可以"随机化"散列键

桶的确切含义是hash function什么？听起来像桶是array-like结构,而且每次都会产生相同的桶号的hash function某种算法/ array-like-structure搜索？这个隐喻桶里面有什么？

我一直都读到javascript对象/ ruby​​哈希/ etc不保证顺序.在实践中我发现键的顺序没有改变(实际上,我认为使用旧版本的Mozilla的Rhino解释器,JS对象命令DID改变了,但我不能确定......).

这是否意味着哈希(Ruby)/对象(JS)没有被这些解决hash functions？

hashing根据您使用计算机的级别,该词是否具有不同的含义？即看起来Ruby散列与C++散列不一样......

我正在尝试将哈希函数应用于 PySpark DataFrame（在 EMR 集群上运行）的列中的短字符串，并获取一个数值作为新列。例如，CRC3 就可以完成这项工作。我知道这个问题，但它是在 Scala 中，我需要一个 python 版本。

（顺便说一句，我知道 pyspark.sql.functions 中的 sha1 和 sha2，但我需要一个更快的哈希函数，它只返回一个数字，例如校验和（但冲突尽可能少）。）

我做了以下事情：

import zlib
crc32 = udf(zlib.crc32)
df2= df.withColumn("crc32", crc32(col("Col1")))
df2.show()

而且，我收到此错误：

    Py4JJavaError: An error occurred while calling o873.showString.
: org.apache.spark.SparkException: Job aborted due to stage failure: Task 0 in stage 37.0 failed 4 times, most recent failure: Lost task 0.3 in stage 37.0 (TID 45019, ip-172-31-58-134.ec2.internal, executor 181): org.apache.spark.api.python.PythonException: Traceback (most recent call last):
  File "/mnt1/yarn/usercache/zeppelin/appcache/application_1571175019959_0009/container_1571175019959_0009_01_000182/pyspark.zip/pyspark/worker.py", line 377, in main
    process()
  File …

我需要使用一个散列函数，该函数属于一个由k个独立散列函数组成的家族。C，C ++或python中任何库或工具包上的任何指针都可以生成一组k个独立的哈希函数，我可以从中选择一个函数。

背景：我正在尝试在此处实现此算法：http : //researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf用于“不同元素”问题。

我看过这个线程：生成k个成对独立的哈希函数，其中提到使用Murmur哈希来生成成对独立的哈希函数。我想知道k方向独立哈希函数是否有任何相似之处。如果没有可用的方法，那么我有可能构造这样的一组k方向独立的哈希函数。

提前致谢。

首先，大多数声称实现了 的地方bucket sort实际上都在实现counting sort。我的问题是关于Geek Viewpoint和Wikipediabucket sort上的实现。我不太了解/喜欢 Geek Viewpoint 上的哈希函数，也不太了解 Wikipedia 上的哈希函数。有人可以解释一种更简单的方法来为桶排序创建良好的哈希函数吗？普通人可以理解和记住的东西。