1

我有一组String可变大小的输入（在我的情况下为 s）N，我需要将其映射到一组固定大小的输出（在我的情况下为数组的索引）M。所以，我基本上需要一个类似的功能：

fn map(input: String) -> usize;

我需要保证两件事：

  1. 对于任何输入X，我必须始终返回相同的输出Y。例如：每次我将字符串传递"hello"给我的函数时，返回的值必须始终相同，例如1.
  2. 返回值的分布必须是均匀的，即对于无限个输入，相同返回值的平均值必须相同。例如，如果我有M = 4不同的值要返回，并且我有N = 100不同的输入，则映射到每个输出的输入数在理想情况下必须等于25.

我想出了以下代码：

use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

fn main() {
    let bucket = Bucket::new(5);
    let inputs = ["hello", "world", "house", "hi"];

    for input in &inputs {
        let output = bucket.get(input);
        assert_eq!(output, bucket.get(input));
        println!("{} -> {}", input, output);
    }
}

pub struct Bucket {
    values: Vec<usize>,
}

impl Bucket {
    pub fn new(size: usize) -> Self {
        let values = (0..size).collect();
        Bucket { values }
    }

    pub fn get<T: Hash>(&self, id: &T) -> usize {
        let mut hasher = DefaultHasher::new();
        Hash::hash(id, &mut hasher);
        let index = (hasher.finish() % self.values.len() as u64) as usize;
        self.values[index]
    }
}

链接到游乐场

我认为上面的代码保证了第一点（对于相同的输入总是相同的输出），但不一定是第二点（分布的均匀性）。

是否有这样一个功能的快速实现，以便保证两个点？

4

1 回答 1

1

我认为您的实施是正确的，第一点是正确的。

关于第二点：这取决于做什么DefaultHasher。在实践中它可能已经足够好了，但是还有另一种技术可以满足您的要求：

  • 有一个计数器m，最初为 0。
  • 有一个HashMap映射String到usize.
  • 每当您想要get结果时，请在以下内容中查找给定的字符串HashMap：
    • 如果字符串已经存在，则返回关联的值。
    • 如果字符串不存在：
    • 向 中添加一个新条目，HashMap将给定的字符串映射到 的当前值m。
    • 递增m1。
    • 如果m==M，则将 m 重置为 0。
于 2019-11-27T20:53:52.597 回答