在Rust哈希映射中分配/实例化字符串/向量的向量？

Question

我正在尝试用Rust从头实现一个玩具哈希映射，并且在实际初始化所需的存储桶时遇到了问题。我已经将这个过程运用在了其他基元类型如u8的桶数组中（如下面片段的注释所示）。

但我无法弄清如何告诉编译器为我分配一个持有其他向量的可变向量——在这种情况下是 ~str 。该代码可以编译，但在运行时会出现一个索引越界错误。

static DEFAULT_NUMBER_OF_BUCKETS: uint = 64;
static DEFAULT_VALUE_LENGTH: uint = 32; //unused

struct NaiveHashMap {
    hashmap_size: uint, //unused.
    string_capacity: uint, //unused.
    //contents: ~[ u8 ]
    contents: ~[ ~str ]
}

impl NaiveHashMap {

    fn new(hash_size: uint, string_size: uint) -> NaiveHashMap {
        NaiveHashMap {
            hashmap_size: hash_size, //unused
            string_capacity: string_size, //unused
            //contents: ~[ 0, ..DEFAULT_NUMBER_OF_BUCKETS ]
            contents: std::vec::with_capacity::<~str>(DEFAULT_NUMBER_OF_BUCKETS)
        }
    }

    fn get_hash(&self, key: &str) -> u32 {
        let hash: u32 = jenkins_hash(key);
        hash % self.hashmap_size.to_u32().unwrap()
    }

    //fn add(&mut self, key: &str, value: u8) {
    fn add(&mut self, key: &str, value: ~str) {
        let bucket = self.get_hash(key);
        self.contents[bucket] = value;
    }

    //fn get(self, key: &str) -> u8 {
    fn get(&self, key: &str) -> ~str {
        let bucket = self.get_hash(key);
        self.contents[bucket].clone()
    }

}

除了调用unsafe的from_buf分配或copy标准的Hashmap库外，我不确定该如何继续。

我意识到最好的实践是在类中传递以使其具有灵活性，但首选先解决这个问题。

编辑：修改了get()以避免捕获整个结构体。

- ispilledthejava

Answer 1

据我所知，您想构建一个给定长度的向量，并通过索引将某些内容写入其中。

在Rust中，除非为向量的每个元素指定默认值，否则无法安全地完成此操作。使用 ~[u8] 是可行的，因为您已经指定了默认值（零），并且 u8 是隐式可复制的。

[0, ..DEFAULT_NUMBER_OF_BUCKETS]

但是对于 ~str，您希望设置什么默认值呢？它是一个指针，在Rust中指针不能等于null，这本来应该是指针的最自然默认值。我认为 ~str 的下一个最自然的值是 ~""，也就是一个空字符串。您可以使用它来创建一个包含 N 个字符串的向量：

vec::from_elem(N, ~"")

这将创建一个空的箱式字符串向量。但这也意味着N个分配，不考虑情况下不应这样做。

然而，对于任意类型T，您不能这样做，因为通常任意类型T没有任何默认值。此外，任意类型T也可能无法克隆，这是from_elem()所要求的。但是您可以从T创建另一种具有默认值的类型。您可以使用Option进行此操作：

contents: ~[Option<T>]

为了克服非可克隆性问题，您可以使用带有闭包的from_fn()函数：

contents: vec::from_fn(N, |_| None)

顺便提一下，出现“索引超出范围”的错误的原因是因为您使用了with_capacity()函数。该函数创建了一个零长度但具有指定容量的向量。您可以使用push()方法将元素附加到向量的末尾，直到达到容量限制才会重新分配内存，但您不能访问“外部”添加的元素。

- Vladimir Matveev