hash - 如何将输入映射到具有相同输出和均匀分布保证的输出？

Question

我有一组可变大小String的输入(在我的情况下为N)，我需要映射到固定大小M的一组输出(在我的情况下为数组的索引)。所以，我基本上需要一个像这样的函数:

fn map(input: String) -> usize;

我需要保证2件事情:

对于任何输入的X，我必须始终返回相同的输出Y。例如:每次将字符串"hello"传递给函数时，返回的值必须始终相同，例如1。

返回值的分布必须是均匀的，即对于无限数量的输入，相同返回值的平均值必须相同。例如，如果我要返回的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]
    }
}

Link to Playground

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

是否有这种功能的快速实现，以确保两点都得到保证？

Answer 1

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

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

有一个计数器m，最初为0。

有一个HashMap映射String到usize。

每当您想对结果进行get时，请在HashMap中查找给定的字符串:

如果字符串已经存在，则返回关联的值。

如果字符串不存在:

向HashMap添加一个新条目，该条目将给定的字符串映射到m的当前值。

将m加1.。

如果为m==M，则将m重置为0。