c# - 散列对象集 C#

Question

我有很多订单，每个订单都包含已购买的Item 对象。

1 : {Item1, Item2, Item3, Item4, Item5}  
2 : {Item2, Item8, Item4, Item3, Item11, Item5} 
3 : { ... }

我的目标是确定每件商品一起购买的频率以及能够在 O(1) 中获得结果的频率。

我的想法是根据子集项目遍历订单 - 增加特定数组的元素。这将使我有可能在 O(1) 中提取所需的值。

例如。 Item3 和 Item4 被购买了 2 次。

int frequency = myArray[getHash(Ite​​m3+Item4)]

打印频率;

输出:2

问题:

开发一个 int getHash(...) 函数，它将能够散列项目的子集。

注意:{Item1, Item2} = {Item2, Item1}

非常感谢!欢迎任何更好的想法的帮助!

Answer 1

因为 {A,B} = {B,A}在继续之前，您首先需要对列表进行排序。排序的依据无关紧要，但您需要确保没有任何值在排序时被视为相等，除非它们在排序中可以互换。

接下来，任何简单的散列算法都应该有效。一种常用的技术是使用两个素数，我称它们为 c和 p .

int hash = c;
foreach(Item i in items) hash = hash * p + i.GetHashCode()
return hash;

p有时选择 31 是因为它不仅是质数，而且编译器将其解析为移位和减法，这比乘法快得多。 x * 31与(x << 5) - 1相同(假设我使用了正确的类次……我时不时搞砸了，哈哈。)