代码之家 › 专栏 › 技术社区 › Åukasz Lew

scala中的完美哈希

perfect-hash scala-2.8 hash types scala

1

Åukasz Lew · 技术社区 · 16 年前

我有一些C类:

class C (...) { ... }

我想用它来索引一个有效的地图。最有效的映射是一个数组。因此,我在伴生对象中添加了一个“global”“static”计数器,以赋予每个对象唯一的ID:

object C {
  var id_counter = 0
}

在C的主构造函数中,每次创建C时,我都希望记住全局计数器值并增加它。
问题1: 怎么做?

现在我可以在C对象中使用ID作为索引数组的完美哈希。但数组并不像map那样保留类型信息,即给定数组是由c的id索引的。

问题2: 是否可以在类型安全的情况下使用?

更新:
问题2中的类型安全涉及地图索引的类型,以避免混合两个不相关的整数。当然,这个值是(类型)安全的。

问题1询问如何在默认控件中增加变量?
IE:放在哪里?

id_counter += 1

3 回复 | 直到 16 年前

1

Alexey Romanov 16 年前

回答问题2:

case class C_Id(val asInt: Int)

object C {
  private var list: ArrayBuffer[C] 
  // resizable array in scala.collection.mutable
  // you can also use ArrayList

  def apply(id: C_Id) = list(id.asInt) // only accepts an id of C
  ...
}

class C (...) {
  // in constructor:
  list += this
}

编辑问题1:默认构造函数只是类型的主体,方法和其他构造函数的定义除外。

2

1

Randall Schulz 16 年前

我看不出问题所在。我可能会把柜台设为私密的,所以在外面加密码 class 和 object C 无法更改。增加a var 类型 Int 微不足道:

idCounter += 1

数组在scala中是类型安全的,因为它们直接由JVM数组实现(从2.8开始)。

我怀疑我没有真正理解你的问题…

更新:

大概是在构造函数中增加计数器。

至于创建一个真正完美的散列函数,我认为您并没有走上正确的道路。(您刚刚将映射从实际的键推进到自己的代码中。)您应该了解创建最小和/或完美哈希函数的技术。

3

0

pdbartlett 16 年前

您是否可以将C的默认构造函数设为private,并在伴生对象中提供一个工厂方法(它可以很容易地处理更新计数器)?