Perfect hash in Scala
I have some class C:
class C (...) { ... }
I want to use it to index an efficient map. The most efficient map is an Array. So I add a "global" "static" counter in companion object to give each object unique id:
object C {
var id_counter = 0
}
In primary constructor of C, with each creation of C I want to remember global counter value and increase it.
Question 1: How to do it?Now I can use id in C objects as perfect hash to index array. But array does not preserve type information like map would, that a given array is indexed by C's id.
Question 2: Is it possible to have it with type safety?
Update:
Type safety in question 2 concerns type of index of map, to avoid mixing two not rela开发者_如何学JAVAted ints. The value of course is (type) safe..Question 1 asks how to increment a variable in default contructor?
Ie: Where to put?id_counter += 1
Answer to your question 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
}
To edited question 1: The default constructor is just the body of the type, except the definitions of methods and other constructors.
I don't see the problem. I would probably make the counter private so code outside class
and object
C
cannot alter it. Incrementing a var
of type Int
is trivial:
idCounter += 1
Arrays are type-safe in Scala, since they are implemented directly by JVM arrays (starting in 2.8).
I suspect I've not really understood your questions...
Update:
Increment the counter in the constructor, presumably.
As for creating an actual perfect hash function, I don't think you're really on the right track. (You've just pushed the mapping from whatever your actual keys are into your own code.) You should read up on techniques for creating minimal and / or perfect hash functions.
Could you make the default constructor of C private, and provide a factory method in the companion object (which could easily handle updating the counter)?
精彩评论