散列2D，3D和nD矢量

散列由IEEE 32位浮點組成的2d和3d矢量的散列函數（快速，分佈好，碰撞少）是什麼？我假定一般的3d矢量，但是假設法線的算法（總是在[-1,1]中）也是受歡迎的。我也不害怕位操縱，因爲IEEE浮動也是IEEE浮動的。散列2D，3D和nD矢量

另一個更普遍的問題是哈希一個Nd浮點向量，其中N非常小（3-12）並且是恆定的，但在編譯時不知道。目前，我只是將這些花車作爲提示並將它們異或，這可能不是最好的解決方案。

...您是否測試過使用純XOR方法分配散列的程度？你可能會感到驚訝。 – 2011-05-08 16:33:27

@Matti似乎至少對於3D矢量的分佈並不是非常糟糕（在斯坦福大學兔子35k verts上對65537大小的哈希表進行測試）。我只是覺得有人可能有一個更專業的解決方案，因爲我前一段時間搜索了網絡，並沒有發現任何關於該主題的內容。 – 2011-05-08 17:31:48

65537聽起來像一個比你可能想要使用的數字更大（或是一個錯字） – 2013-09-13 03:12:36

哈希（X，Y，Z）=（x p1的XORŸP2 XORž P3）模N

其中P1，P2，P3大素數，在我們的案例分別爲73856093, 19349663,83492791。值n是哈希表大小。

在論文中，x，y和z是離散化座標;你大概也可以使用你的浮點數的二進制值。

2011-05-08 18:56:48 celion

+14

請注意，19349663不是素數（它是41和471943的乘積） – sehe 2013-09-05 13:20:15

我發現在二維情況下使用質數p1和p3會得到非常好的分佈。 – axel22 2016-03-06 21:36:01

當他們寫了'x p1 xor y p2 xor z p3'時，他們的意思是'（x * p1）xor（y * p2）xor（z * p3）'還是'x *（p1 xor y）*（p2 xor z）* p3'？ – emlai 2016-06-25 15:24:19

我有兩個建議。

假設尺寸升的網格單元和通過計算IX =地板（X/L），IY =地板量化X，ÿ和ž座標（ y/l）和iz = floor（z/l），其中ix，iy和iz是整數。現在使用在 Optimized Spatial Hashing for Collision Detection of Deformable Objects中定義的散列函數

如果你不做量化，它不會對接近度（局部性）敏感。

Locality Sensitive Hashing已被提及用於散列更高維向量。爲什麼不把它們用於3d或2d矢量呢？使用適用於Eucledian距離度量（這是我們需要的2d和3d向量）的LSH變體稱爲使用p穩定分佈的局部敏感散列。一個非常易讀的教程是here。

2014-05-05 23:20:59

回答